Мультимножество — это набор чисел, в котором могут быть равные элементы, и порядок чисел не имеет значения. Например, \(\{2,2,4\}\) — мультимножество.
У вас есть мультимножество \(S\). Изначально мультимножество содержит только одно положительное целое число \(n\). То есть, \(S=\{n\}\). Кроме того, задано положительное целое число \(k\).
За одну операцию вы можете выбрать любое положительное целое число \(u\) из \(S\) и удалить одно вхождение \(u\) из \(S\). Затем вставить не более \(k\) положительных целых чисел в \(S\), чтобы сумма всех вставленных чисел была равна \(u\).
Найдите минимальное количество операций, чтобы сделать \(S\) состоящим из \(n\) единиц.
Выходные данные
Для каждого набора входных данных выведите одно целое число, которое является требуемым ответом.
Примечание
Для первого набора входных данных изначально \(S=\{1\}\), что уже удовлетворяет требованию. Поэтому нам не нужно делать ни одной операции.
Для второго набора входных данных изначально \(S=\{5\}\). Мы можем применить следующие операции:
- Выберите \(u=5\), удалите \(u\) из \(S\) и вставьте \(2,3\) в \(S\). Теперь \(S=\{2,3\}\).
- Выберите \(u=2\), удалите \(u\) из \(S\) и вставьте \(1,1\) в \(S\). Теперь \(S=\{1,1,3\}\).
- Выберите \(u=3\), удалите \(u\) из \(S\) и вставьте \(1,2\) в \(S\). Теперь \(S=\{1,1,1,2\}\).
- Выберите \(u=2\), удалите \(u\) из \(S\) и вставьте \(1,1\) в \(S\). Теперь \(S=\{1,1,1,1,1\}\).
Используя \(4\) операции в общей сложности, мы достигаем цели.
Для третьего набора входных данных изначально \(S=\{6\}\). Мы можем применить следующие операции:
- Выберите \(u=6\), удалите \(u\) из \(S\) и вставьте \(1,2,3\) в \(S\). Теперь \(S=\{1,2,3\}\).
- Выберите \(u=2\), удалите \(u\) из \(S\) и вставьте \(1,1\) в \(S\). Теперь \(S=\{1,1,1,3\}\).
- Выберите \(u=3\), удалите \(u\) из \(S\) и вставьте \(1,1,1\) в \(S\). Теперь \(S=\{1,1,1,1,1,1\}\).
Используя \(3\) операции в общей сложности, мы достигаем цели.
Для четвертого набора входных данных изначально \(S=\{16\}\). Мы можем применить следующие операции:
- Выберите \(u=16\), удалите \(u\) из \(S\) и вставьте \(4,4,4,4\) в \(S\). Теперь \(S=\{4,4,4,4\}\).
- Повторите \(4\) раза: выберите \(u=4\), удалите \(u\) из \(S\) и вставьте \(1,1,1,1\) в \(S\).
Используя \(5\) операций в общей сложности, мы достигаем цели.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 5
5 2
6 3
16 4
|
0
4
3
5
|