The Good Array

1000ms

262144K

Description:

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:

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:

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.

Sample Input:

Sample Output:

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$$$.

Informação

Provedor Codeforces

Código CF1839A