ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Timus Top Coders: First Challenge

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Queen 2

Time limit: 3.0 second
Memory limit: 64 MB


Paul V. Pawnstein, 45 years old. Famous grand master. World chess champion. Sure of his future. Sure of himself. Sure, that Moore's Law is not and will never be a thing of his concern: "I can hardly imagine it".
Ten years have passed. Mr. Pawnstein frowned and began the next game against the supercomputer Deep Navy - slowly moved a white pawn from e2 to e4. Multicolored lights immediately started to blink on the surface of the board, something cracked inside it, and some seconds later a cold female voice declared: "Black wins after 43 moves in case of the optimal strategy of white". Perplexed grand master stared at the board...
Another ten years have passed. Long-term work of Mr. Pawnstein has just crowned with invention of absolutely new N-dimensional chess. The grand master is entirely sure that computing power of future engineering will not be enough to create a good N-dimensional chess computer player, because even the calculations, which seem to be elementary, require huge time and memory costs. As an example Mr. Pawnstein gives us a classical problem which is known as "Queen II".


A board in N-dimensional chess is N-dimensional cube S*S*...*S cells in size. A cell in one of its corners (this corner is chosen at will) has coordinates (1, 1, ..., 1), and a cell in the opposite corner has coordinates (S, S, ..., S).
A rook in N-dimensional chess makes its move shifting by any non-zero number of cells along one of its coordinates. A bishop in N-dimensional chess makes its move shifting by any non-zero number of cells along all its coordinates at once, and these shifts must be equal to each other by their absolute values. A queen in N-dimensional chess can make its move both as a bishop and as a rook.
A queen is situated on empty chess-board in a cell with coordinates (C[1], C[2], ..., C[N]). You should calculate a number of different cells the queen can be situated in after two its moves.


The first line contains the integer numbers N (1 ≤ N ≤ 5) and S (2 ≤ S ≤ 100). The second line contains N integer numbers C[i] (1 ≤ C[i] ≤ S).


You should output the solution of "Queen II" problem.


3 3
1 2 3


Let us consider three-dimensional chess-board 3*3*3 cells in size. If a queen is initially located in the cell with coordinates (1, 2, 3) it can make its first move to the cells with coordinates (2, 2, 3), (3, 2, 3), (1, 1, 3), (1, 3, 3), (1, 2, 1) and (1, 2, 2) moving as a rook, and to the cells with coordinates (2, 3, 2) and (2, 1, 2) moving as a bishop.
Problem Author: Nikita Rybak, Dmitry Kovalioff, Ilya Grebnov
Problem Source: Timus Top Coders: First Challenge
To submit the solution for this problem go to the Problem set: 1425. Queen 2