B. 相邻方块 · AC 题库

AtCoder Regular Contest-- 224

相邻方块

Adjacent Tiles

AtCoder

⌀ 630

原题

← AC →

相邻方块AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

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?

在平面上放置 $N$ 个大小相同的正方形方块，且它们互不重叠。那么，不同方块之间最多能有多少对完整共边？AI (CI翻译)

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.

这里，不同方块 $(a,b)$ 完整共边，当且仅当 $a$ 的某一条边与 $b$ 的某一条边完全重合。AI (CI翻译)

$T$ test cases are given; solve each of them.

给定 $T$ 组测试数据，请分别求解。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$1 \le T \le 2 \times 10^5$
$1 \le N \le 10^{18}$
All input values are integers.

$1 \le T \le 2 \times 10^5$
$1 \le N \le 10^{18}$
所有输入值均为整数。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format, where $\mathrm{case}_i$ denotes the $i$ -th test case:

输入从标准输入给出，格式如下，其中 $\mathrm{case}_i$ 表示第 $i$ 组测试数据：AI (CI翻译)

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

AI (CI翻译)

Each test case is given in the following format:

每组测试数据的格式如下：AI (CI翻译)

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output $T$ lines. The $i$ -th line should contain the answer for the $i$ -th test case.

输出 $T$ 行。第 $i$ 行应包含第 $i$ 组测试数据的答案。AI (CI翻译)

样例

Input #1

6
1
2
3
4
100000000000000000
1000000000000000000

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. ![image](https://img.atcoder.jp/arc224/8aea669e2ca752ca51efd2115ba06edc.png)

题目信息

题号

arc224_b

所属比赛

AtCoder Regular Contest-- 224

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。