Задача №114652. База данных
Егор занимется проектированием распределённых баз данных. Сейчас он работает над базой данных, в которой будет храниться информация об участниках Открытой олимпиады школьников по программированию.
Данные об участниках олимпиады представляют собой таблицу размером \(a\) гигабайт, разбитую на \(a\) блоков, каждый из которых имеет размер \(1\) гигабайт. Для хранения этих данных Егор планирует приобрести \(n\) одинаковых серверов и объединить их в закольцованную сеть. Для этого он присвоит серверам уникальные номера от \(1\) до \(n\) и соединит кабелем серверы с номерами \(i\) и \(i + 1\) для каждого \(i\) от \(1\) до \(n - 1\), а также соединит серверы с номерами \(1\) и \(n\).
Алгоритм, при помощи которого Егор будет сохранять блоки на серверы, требует, чтобы каждый из \(a\) блоков был сохранён ровно на \(b\) последовательных серверах, то есть на таких серверах, что каждый следующий сервер соединён с предыдущим сервером кабелем. Например, при \(n = 5\) и \(b = 3\) блок может быть сохранён на серверах \([2, 3, 4]\) или \([5, 1, 2]\), но не может быть сохранён на серверах \([1, 3, 4]\).
Егор ещё не выбрал, какие серверы ему купить. Разумеется, цена серверов зависит от размеров их дисков, а требуемые размеры дисков зависят от того, сколько блоков будет храниться на сервере, поэтому Егора интересует, какого минимального количества сохранённых блоков на сервере с максимальным количеством блоков можно добиться при оптимальной стратегии хранения данных.
В первой строке задано целое число \(n\) (\(3 \leq n \leq 2 \cdot 10^9\)) — количество серверов, на которых планирует сохранять данные Егор.
Во второй строке задано целое число \(a\) (\(1 \leq a \leq 2 \cdot 10^9\)) — количество блоков, на которые разбиты данные.
В третьей строке задано целое число \(b\) (\(1 \leq b \leq n\)) — количество последовательных серверов, на которых должен быть сохранён каждый блок.
Выведите одно целое число — минимально возможное количество блоков на сервере с наибольшим количеством блоков.
В первом примере Егору нужно сохранить четыре блока на трёх серверах. Первый и второй блок можно сохранить на серверах с номерами \(1\) и \(2\), третий блок можно сохранить на серверах с номерами \(2\) и \(3\), а четвёртый блок сохранить на серверах с номерами \(3\) и \(1\). Таким образом, на серверах с номерами \(1\) и \(2\) будет сохранено по три блока, а на сервере с номером \(3\) будет сохранено два блока.
Во втором примере каждый из \(10\) блоков необходимо сохранить на всех серверах.
В третьем примере можно сохранить первые \(4\) блока на серверах с номерами \(1\) и \(2\), а оставшиеся \(4\) блока на серверах с номерами \(3\) и \(4\).
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
| Дополнительные ограничения | |||
| Группа | Баллы | \(n, a, b\) | Комментарий |
| 0 | 0 | – | Тесты из условия. |
| 1 | 20 | \(n, a, b \leq 10\) | |
| 2 | 25 | \(n, a, b \leq 1000\) | |
| 3 | 25 | \(n, a, b \leq 10^6\) | |
| 4 | 30 | – |
3 4 2
3
5 10 5
10
4 8 2
4
10 5 7
4