307408: CF1353C. Board Moves

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Board Moves

题意翻译

### 题目描述 有一个$n×n$的棋盘($n$为奇数),一开始每个格子中都含有一个数。现在你可以进行以下操作: 一步操作指选定任意格中的恰好一个数,并将其移动到周围的八个格子中之一。也就是说,如果原来格子的坐标是$(i,j)$,那么你可以将这个数移到$(i+1,j)$$(i-1,j)$$(i+1,j+1)$$(i,j+1)$$(i-1,j+1)$$(i+1,j-1)$$(i,j-1)$$(i-1,j-1)$这八个格子中。 当然,你不能把棋子移到棋盘外。允许在一次操作后一个格子里存在多个数。 你的任务是找出操作的最小次数,使得所有的数都在一个方格内。也就是说在$(n^2-1)$个格子内都没有数,而在$1$个格子内有所有的数。 ### 输入格式 **本题有多组测试数据**。 第一行一个整数$t(1<=t<=200)$,表示测试数据的组数; 接下来的$t$行,每行一个整数$n(1<=n<=5×10^5)$——棋盘的边长。保证$n$为奇数。 同时保证所有$t$个$n$的值的和不超过$5×10^5$。 ### 输出格式 输出共$t$行,每行包含一个整数,表示每一组测试数据的答案。

题目描述

You are given a board of size $ n \times n $ , where $ n $ is odd (not divisible by $ 2 $ ). Initially, each cell of the board contains one figure. In one move, you can select exactly one figure presented in some cell and move it to one of the cells sharing a side or a corner with the current cell, i.e. from the cell $ (i, j) $ you can move the figure to cells: - $ (i - 1, j - 1) $ ; - $ (i - 1, j) $ ; - $ (i - 1, j + 1) $ ; - $ (i, j - 1) $ ; - $ (i, j + 1) $ ; - $ (i + 1, j - 1) $ ; - $ (i + 1, j) $ ; - $ (i + 1, j + 1) $ ; Of course, you can not move figures to cells out of the board. It is allowed that after a move there will be several figures in one cell. Your task is to find the minimum number of moves needed to get all the figures into one cell (i.e. $ n^2-1 $ cells should contain $ 0 $ figures and one cell should contain $ n^2 $ figures). You have to answer $ t $ independent test cases.

输入输出格式

输入格式


The first line of the input contains one integer $ t $ ( $ 1 \le t \le 200 $ ) — the number of test cases. Then $ t $ test cases follow. The only line of the test case contains one integer $ n $ ( $ 1 \le n < 5 \cdot 10^5 $ ) — the size of the board. It is guaranteed that $ n $ is odd (not divisible by $ 2 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5 \cdot 10^5 $ ( $ \sum n \le 5 \cdot 10^5 $ ).

输出格式


For each test case print the answer — the minimum number of moves needed to get all the figures into one cell.

输入输出样例

输入样例 #1

3
1
5
499993

输出样例 #1

0
40
41664916690999888

Input

题意翻译

### 题目描述 有一个$n×n$的棋盘($n$为奇数),一开始每个格子中都含有一个数。现在你可以进行以下操作: 一步操作指选定任意格中的恰好一个数,并将其移动到周围的八个格子中之一。也就是说,如果原来格子的坐标是$(i,j)$,那么你可以将这个数移到$(i+1,j)$$(i-1,j)$$(i+1,j+1)$$(i,j+1)$$(i-1,j+1)$$(i+1,j-1)$$(i,j-1)$$(i-1,j-1)$这八个格子中。 当然,你不能把棋子移到棋盘外。允许在一次操作后一个格子里存在多个数。 你的任务是找出操作的最小次数,使得所有的数都在一个方格内。也就是说在$(n^2-1)$个格子内都没有数,而在$1$个格子内有所有的数。 ### 输入格式 **本题有多组测试数据**。 第一行一个整数$t(1<=t<=200)$,表示测试数据的组数; 接下来的$t$行,每行一个整数$n(1<=n<=5×10^5)$——棋盘的边长。保证$n$为奇数。 同时保证所有$t$个$n$的值的和不超过$5×10^5$。 ### 输出格式 输出共$t$行,每行包含一个整数,表示每一组测试数据的答案。

加入题单

算法标签: