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