Half Queen Cover

题意翻译

给定一个 $n\times n$（$1≤n≤10^5$） 的棋盘，将第 $i$ 行第 $j$ 列的坐标记作 $(i,j)$。 至少需要多少个国际象棋中的皇后，才能使棋盘上每个格子都被攻击到？输出它们的坐标。 注：一个点$(c,d)$ 能够被处于 $(a,b)$ 的皇后攻击到，当且仅当 $a=c$ 或 $b=d$ 或 $a-b=c-d$。

题目描述

You are given a board with $ n $ rows and $ n $ columns, numbered from $ 1 $ to $ n $ . The intersection of the $ a $ -th row and $ b $ -th column is denoted by $ (a, b) $ . 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. 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.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the size of the board.

输出格式

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 $ a_i $ , $ b_i $ ( $ 1 \le a_i, b_i \le n $ ) — the position of the $ i $ -th half-queen. If there are multiple solutions, print any.

输入输出样例

输入样例 #1

1

输出样例 #1

1
1 1

输入样例 #2

2

输出样例 #2

1
1 1

输入样例 #3

3

输出样例 #3

2
1 1
1 2

说明

Example $ 1 $ : one half-queen is enough. Note: a half-queen on $ (1, 1) $ attacks $ (1, 1) $ . Example $ 2 $ : one half-queen is enough too. $ (1, 2) $ or $ (2, 1) $ would be wrong solutions, because a half-queen on $ (1, 2) $ does not attack the cell $ (2, 1) $ and vice versa. $ (2, 2) $ is also a valid solution. Example $ 3 $ : it is impossible to cover the board with one half queen. There are multiple solutions for $ 2 $ half-queens; you can print any of them.