Preparing NOJ

数点

2000ms 262144K

Description:

在一个长和高都为n的等腰直角三角形点阵(如左图)中,你可以选择 $$$ m $$$ 个不重复的斜边上的点,假设选择了点 $$$ (x,n-x+1) $$$ ,则标记以 $$$ (1,1) $$$ 为左下角、 $$$ (x,n-x+1) $$$ 为右上角的矩形中的所有点(包括边框上的点),假如一个点被多次标记,只计算一次。请问选择m个不重复点最多能标记到多少个点。

Problem D

Input:

第 $$$ 1 $$$ 行,一个整数$$$t(1\le t\le 10^5)$$$,表示$$$t$$$组询问。

第 $$$ 2 $$$ 到 $$$ t+1 $$$ 行,每行两个整数$$$n$$$和$$$m(1\le m \le n \le 10^9)$$$,如题意。

Output:

对于每次询问,输出最多能标记的点数。

Sample Input:

7
3 1
3 2
3 3
4 2
5 2
12 3
100 20

Sample Output:

4
5
6
8
12
63
4856

Note:

图示为 $$$ n=5 $$$ , $$$ m=2 $$$ 的情况,选择 $$$ (2,4) $$$ 和 $$$ (4,2) $$$ 两点, $$$ (2,4) $$$ 标记了蓝色和紫色部分, $$$ (4,2) $$$ 标记了红色和紫色部分,其中紫色部分只计算一次,所以答案是 $$$ 12 $$$ 。

Info

NOJ

Provider NOJ

Code NOJ2439

Tags

Submitted 3

Passed 3

AC Rate 100%

Date 02/16/2020 00:55:19

Related

Nothing Yet