The Good Array
Contest: Codeforces Round 876 (Div. 2)
Difficulty rating: 800
Tags: greedy, implementation, math

You are given two integers $$$n$$$ and $$$k$$$.

An array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, consisting of zeroes and ones is good if for all integers $$$i$$$ from $$$1$$$ to $$$n$$$ both of the following conditions are satisfied:

- at least $$$\lceil \frac{i}{k} \rceil$$$ of the first $$$i$$$ elements of $$$a$$$ are equal to $$$1$$$,
- at least $$$\lceil \frac{i}{k} \rceil$$$ of the last $$$i$$$ elements of $$$a$$$ are equal to $$$1$$$.

Here, $$$\lceil \frac{i}{k} \rceil$$$ denotes the result of division of $$$i$$$ by $$$k$$$, rounded up. For example, $$$\lceil \frac{6}{3} \rceil = 2$$$, $$$\lceil \frac{11}{5} \rceil = \lceil 2.2 \rceil = 3$$$ and $$$\lceil \frac{7}{4} \rceil = \lceil 1.75 \rceil = 2$$$.

Find the minimum possible number of ones in a good array.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$2 \le n \le 100$$$, $$$1 \le k \le n$$$) — the length of array and parameter $$$k$$$ from the statement.

Output format:
For each test case output one integer — the minimum possible number of ones in a good array.

It can be shown that under the given constraints at least one good array always exists.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$n = 3$$$ and $$$k = 2$$$:

- Array $$$[ \, 1, 0, 1 \, ]$$$ is good and the number of ones in it is $$$2$$$.
- Arrays $$$[ \, 0, 0, 0 \, ]$$$, $$$[ \, 0, 1, 0 \, ]$$$ and $$$[ \, 0, 0, 1 \, ]$$$ are not good since for $$$i=1$$$ the first condition from the statement is not satisfied.
- Array $$$[ \, 1, 0, 0 \, ]$$$ is not good since for $$$i=1$$$ the second condition from the statement is not satisfied.
- All other arrays of length $$$3$$$ contain at least $$$2$$$ ones.

Thus, the answer is $$$2$$$.

In the second test case, $$$n = 5$$$ and $$$k = 2$$$:

- Array $$$[ \, 1, 1, 0, 0, 1 \, ]$$$ is not good since for $$$i=3$$$ the second condition is not satisfied.
- Array $$$[ \, 1, 0, 1, 0, 1 \, ]$$$ is good and the number of ones in it is $$$3$$$.
- It can be shown that there is no good array with less than $$$3$$$ ones, so the answer is $$$3$$$.

In the third test case, $$$n = 9$$$ and $$$k = 3$$$:

- Array $$$[ \, 1, 0, 1, 0, 0, 0, 1, 0, 1 \, ]$$$ is good and the number of ones in it is $$$4$$$.
- It can be shown that there is no good array with less than $$$4$$$ ones, so the answer is $$$4$$$.

In the fourth test case, $$$n = 7$$$ and $$$k = 1$$$. The only good array is $$$[ \, 1, 1, 1, 1, 1, 1, 1\, ]$$$, so the answer is $$$7$$$.

Example input:
7
3 2
5 2
9 3
7 1
10 4
9 5
8 8

Example output:
2
3
4
7
4
3
2

Editorial:
Let's find lower bound for answer. In any good array, there are at least $$$\lceil \frac{n - 1}{k} \rceil$$$ ones among the first $$$n - 1$$$ elements. Also, $$$a_n$$$ is always $$$1$$$, as $$$\lceil \frac{1}{k} \rceil = 1$$$.
So there are at least $$$\lceil \frac{n - 1}{k} \rceil + 1$$$ ones in any good array.
This lower bound can always be achieved by placing ones on position $$$n$$$ and on positions $$$1 + k \cdot x$$$ for all integers $$$x$$$ such that $$$0 \le x \le \lfloor \frac{n - 2}{k} \rfloor = \lceil \frac{n - 1}{k} \rceil - 1$$$.
The answer to the probelm is $$$\lceil \frac{n - 1}{k} \rceil + 1$$$.