/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
同じ大きさの正方形のタイル N 枚を、平面上に重ならないように配置します。
このとき、一辺を完全に共有している相異なるタイルのペアの個数は最大でいくつになりますか？
ただし、タイルのペア (a,b) が一辺を完全に共有するとは、 a のある辺と b のある辺が完全に一致することをいいます。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \le T \le 2 \times 10^5
- 1 \le N \le 10^{18}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 個目のテストケースを意味する。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N
出力
T 行出力せよ。i 行目には i 個目のテストケースの答えを出力せよ。
入力例 1
6 1 2 3 4 100000000000000000 1000000000000000000
出力例 1
0 1 2 4 199999999367544467 1999999998000000000
この入力には 6 個のテストケースが含まれています。
下図は、 N=1,2,3,4 の最適なタイルの配置の一例を示します。
- 1 個目のテストケースについて、 N=1 です。
- 一辺を完全に共有しているタイルのペアは存在しません。
- 2 個目のテストケースについて、 N=2 です。
- タイルのペア ({\rm a,b}) が一辺を完全に共有しています。
- 3 個目のテストケースについて、 N=3 です。
- タイルのペア ({\rm a,b}),({\rm b,c}) が一辺を完全に共有しています。
- 4 個目のテストケースについて、 N=4 です。
- タイルのペア ({\rm a,b}),({\rm a,c}),({\rm b,d}),({\rm c,d}) が一辺を完全に共有しています。
Score : 400 points
Problem Statement
Let us place N square tiles of the same size on a plane so that they do not overlap.
Then, what is the maximum possible number of pairs of different tiles that share one full side?
Here, a pair of different tiles (a,b) is said to share one full side if and only if some side of a and some side of b coincide completely.
T test cases are given; solve each of them.
Constraints
- 1 \le T \le 2 \times 10^5
- 1 \le N \le 10^{18}
- All input values are integers.
Input
The input is given from Standard Input in the following format, where \mathrm{case}_i denotes the i-th test case:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
6 1 2 3 4 100000000000000000 1000000000000000000
Sample Output 1
0 1 2 4 199999999367544467 1999999998000000000
This input contains six test cases.
The figure below shows an example of an optimal arrangement of tiles for N=1,2,3,4.
- For the first test case, N=1.
- There is no pair of different tiles sharing one full side.
- For the second test case, N=2.
- The pair of tiles ({\rm a,b}) shares one full side.
- For the third test case, N=3.
- The pairs of tiles ({\rm a,b}),({\rm b,c}) share one full side.
- For the fourth test case, N=4.
- The pairs of tiles ({\rm a,b}),({\rm a,c}),({\rm b,d}),({\rm c,d}) share one full side.