eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

N Queens

N Queens

Ліміт часу 30 секунд
Ліміт використання пам'яті 64 MiB

There is well‐known task to place 8 chess queens on the original 8×8 chessboard in a way that no two of them attack each other. A queen attacks all cells that are in the same row, same column or same diagonal with it. One of the solutions is shown on the figure.

The generalised problem was posed by Franz Nauck in 1850 and asks in how many ways N queens can be placed on an N×N board so tht no two queens attack each other. It has been proven that for N>3 there always exists at least one solution. For example, for N=26 there are 22317699616364044 different solutions.

You are asked to solve a slightly different task – find any one solution (correct placement of N queens on an N×N board) for five given values of N and submit an output file for each solution:

Вхідні дані

One number - N (N ≤ 10^5). (see example)

Вихідні дані

In the output file with the specified name there must be N rows. For each i (1iN) the i‐th row of the output file must contain exactly one integer – the number of the column where the queen in the i‐th row is placed.

For example, if you would be asked to submit a solution for eight queens, then a valid output file content might be (corresponds to the picture above; rows are numbered from top to bottom, columns are numbered from left to right) - see example.

Приклад

Вхідні дані #1
26
Вихідні дані #1
20
3
16
6
17
5
11
4
15
7
22
1
21
23
10
26
24
18
12
8
19
25
9
14
2
13
Джерело BOI-2012