Half Queen Cover solution codeforces – You are given a board with 𝑛n rows and 𝑛n columns, numbered from 11 to 𝑛n. The intersection of the 𝑎a-th row and 𝑏b-th column is denoted by (𝑎,𝑏)(a,b).
[Solution] Half Queen Cover solution codeforces
A half-queen attacks cells in the same row, same column, and on one diagonal. More formally, a half-queen on (𝑎,𝑏)(a,b) attacks the cell (𝑐,𝑑)(c,d) if 𝑎=𝑐a=c or 𝑏=𝑑b=d or 𝑎−𝑏=𝑐−𝑑a−b=c−d.
The blue cells are under attack.The first line contains a single integer 𝑛n (1≤𝑛≤1051≤n≤105) — the size of the board.
[Solution] Half Queen Cover solution codeforces
In the first line print a single integer 𝑘k — the minimum number of half-queens.
In each of the next 𝑘k lines print two integers 𝑎𝑖ai, 𝑏𝑖bi (1≤𝑎𝑖,𝑏𝑖≤𝑛1≤ai,bi≤n) — the position of the 𝑖i-th half-queen.
If there are multiple solutions, print any.
1
1 1 1
2
[Solution] Half Queen Cover solution codeforces
1 1 1
3
2 1 1 1 2
Half Queen Cover solution codeforces
Example 11: one half-queen is enough. Note: a half-queen on (1,1)(1,1) attacks (1,1)(1,1).
Example 22: one half-queen is enough too. (1,2)(1,2) or (2,1)(2,1) would be wrong solutions, because a half-queen on (1,2)(1,2) does not attack the cell (2,1)(2,1) and vice versa. (2,2)(2,2) is also a valid solution.
Example 33: it is impossible to cover the board with one half queen. There are multiple solutions for 22 half-queens; you can print any of them.