[Solution] Half Queen Cover solution codeforces

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.

Half Queen Cover solution codeforcesThe blue cells are under attack.
What is the minimum number of half-queens that can be placed on that board so as to ensure that each square is attacked by at least one half-queen?Construct an optimal solution.

Input

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.

Examples
input

Copy
1
output

Copy
1
1 1
input

Copy
2

[Solution] Half Queen Cover solution codeforces

output

Copy
1
1 1
input

Copy
3
output

Copy
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.

 

For Solution

Click here

Leave a Comment