Codeforces Round 958 (Div. 2) |
---|
Finished |
A multiset is a set of numbers in which there can be equal elements, and the order of the numbers does not matter. For example, $$$\{2,2,4\}$$$ is a multiset.
You have a multiset $$$S$$$. Initially, the multiset contains only one positive integer $$$n$$$. That is, $$$S=\{n\}$$$. Additionally, there is a given positive integer $$$k$$$.
In one operation, you can select any positive integer $$$u$$$ in $$$S$$$ and remove one copy of $$$u$$$ from $$$S$$$. Then, insert no more than $$$k$$$ positive integers into $$$S$$$ so that the sum of all inserted integers is equal to $$$u$$$.
Find the minimum number of operations to make $$$S$$$ contain $$$n$$$ ones.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.
The only line of each testcase contains two integers $$$n,k$$$ ($$$1\le n\le 1000,2\le k\le 1000$$$).
For each testcase, print one integer, which is the required answer.
41 55 26 316 4
0 4 3 5
For the first test case, initially $$$S=\{1\}$$$, already satisfying the requirement. Therefore, we need zero operations.
For the second test case, initially $$$S=\{5\}$$$. We can apply the following operations:
Using $$$4$$$ operations in total, we achieve the goal.
For the third test case, initially $$$S=\{6\}$$$. We can apply the following operations:
Using $$$3$$$ operations in total, we achieve the goal.
For the fourth test case, initially $$$S=\{16\}$$$. We can apply the following operations:
Using $$$5$$$ operations in total, we achieve the goal.
Name |
---|