A13079. Candies Division
编程题
普及/提高-
知识点
题目描述
Santa has $n$ candies and he wants to gift them to $k$ kids. He wants to divide as many candies as possible between all $k$ kids. Santa can't divide one candy into parts but he is allowed to not use some candies at all.
Suppose the kid who recieves the minimum number of candies has $a$ candies and the kid who recieves the maximum number of candies has $b$ candies. Then Santa will be satisfied, if the both conditions are met at the same time:
- $b - a \le 1$ (it means $b = a$ or $b = a + 1$ );
- the number of kids who has $a+1$ candies (note that $a+1$ not necessarily equals $b$ ) does not exceed $\lfloor\frac{k}{2}\rfloor$ (less than or equal to $\lfloor\frac{k}{2}\rfloor$ ).
$\lfloor\frac{k}{2}\rfloor$ is $k$ divided by $2$ and rounded down to the nearest integer. For example, if $k=5$ then $\lfloor\frac{k}{2}\rfloor=\lfloor\frac{5}{2}\rfloor=2$ .
Your task is to find the maximum number of candies Santa can give to kids so that he will be satisfied.
You have to answer $t$ independent test cases.
Suppose the kid who recieves the minimum number of candies has $a$ candies and the kid who recieves the maximum number of candies has $b$ candies. Then Santa will be satisfied, if the both conditions are met at the same time:
- $b - a \le 1$ (it means $b = a$ or $b = a + 1$ );
- the number of kids who has $a+1$ candies (note that $a+1$ not necessarily equals $b$ ) does not exceed $\lfloor\frac{k}{2}\rfloor$ (less than or equal to $\lfloor\frac{k}{2}\rfloor$ ).
$\lfloor\frac{k}{2}\rfloor$ is $k$ divided by $2$ and rounded down to the nearest integer. For example, if $k=5$ then $\lfloor\frac{k}{2}\rfloor=\lfloor\frac{5}{2}\rfloor=2$ .
Your task is to find the maximum number of candies Santa can give to kids so that he will be satisfied.
You have to answer $t$ independent test cases.
输入格式
The first line of the input contains one integer $t$ ( $1 \le t \le 5 \cdot 10^4$ ) — the number of test cases.
The next $t$ lines describe test cases. The $i$ -th test case contains two integers $n$ and $k$ ( $1 \le n, k \le 10^9$ ) — the number of candies and the number of kids.
The next $t$ lines describe test cases. The $i$ -th test case contains two integers $n$ and $k$ ( $1 \le n, k \le 10^9$ ) — the number of candies and the number of kids.
输出格式
For each test case print the answer on it — the maximum number of candies Santa can give to kids so that he will be satisfied.
输入输出样例
输入 #1
5 5 2 19 4 12 7 6 2 100000 50010
输出 #1
5 18 10 6 75015
说明/提示
In the first test case, Santa can give $3$ and $2$ candies to kids. There $a=2, b=3,a+1=3$ .
In the second test case, Santa can give $5, 5, 4$ and $4$ candies. There $a=4,b=5,a+1=5$ . The answer cannot be greater because then the number of kids with $5$ candies will be $3$ .
In the third test case, Santa can distribute candies in the following way: $[1, 2, 2, 1, 1, 2, 1]$ . There $a=1,b=2,a+1=2$ . He cannot distribute two remaining candies in a way to be satisfied.
In the fourth test case, Santa can distribute candies in the following way: $[3, 3]$ . There $a=3, b=3, a+1=4$ . Santa distributed all $6$ candies.
In the second test case, Santa can give $5, 5, 4$ and $4$ candies. There $a=4,b=5,a+1=5$ . The answer cannot be greater because then the number of kids with $5$ candies will be $3$ .
In the third test case, Santa can distribute candies in the following way: $[1, 2, 2, 1, 1, 2, 1]$ . There $a=1,b=2,a+1=2$ . He cannot distribute two remaining candies in a way to be satisfied.
In the fourth test case, Santa can distribute candies in the following way: $[3, 3]$ . There $a=3, b=3, a+1=4$ . Santa distributed all $6$ candies.