codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1353C.md (1690B)


      1 Source: https://codeforces.com/problemset/problem/1353/C
      2 
      3 C. Board Moves
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 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:
     24 
     25 * $(i - 1, j - 1)$;
     26 * $(i - 1, j)$;
     27 * $(i - 1, j + 1)$;
     28 * $(i, j - 1)$;
     29 * $(i, j + 1)$;
     30 * $(i + 1, j - 1)$;
     31 * $(i + 1, j)$;
     32 * $(i + 1, j + 1)$;
     33 
     34 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.
     35 
     36 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).
     37 
     38 You have to answer $t$ independent test cases.
     39 
     40 Input
     41 
     42 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.
     43 
     44 The only line of the test case contains one integer $n$ ($1 \le n \lt 5 \cdot 10^5$) — the size of the board. It is guaranteed that $n$ is odd (not divisible by $2$).
     45 
     46 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$).
     47 
     48 Output
     49 
     50 For each test case print the answer — the minimum number of moves needed to get all the figures into one cell.
     51 
     52 Example
     53 
     54 Input
     55 
     56 ```
     57 3
     58 1
     59 5
     60 499993
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 0
     67 40
     68 41664916690999888
     69 ```