Nauuo and Chess
题意翻译
在一个 m×m 的棋盘上放 n 颗棋子,第 i 颗棋子的坐标为 (ri,ci),需要满足 |ri−rj|+|ci−cj|≥|i−j|,求 m 的最小值以及任意一种摆放方案。依次输出m和每个棋子的(ri,ci)。
题目描述
Nauuo is a girl who loves playing chess.
One day she invented a game by herself which needs $ n $ chess pieces to play on a $ m\times m $ chessboard. The rows and columns are numbered from $ 1 $ to $ m $ . We denote a cell on the intersection of the $ r $ -th row and $ c $ -th column as $ (r,c) $ .
The game's goal is to place $ n $ chess pieces numbered from $ 1 $ to $ n $ on the chessboard, the $ i $ -th piece lies on $ (r_i,\,c_i) $ , while the following rule is satisfied: for all pairs of pieces $ i $ and $ j $ , $ |r_i-r_j|+|c_i-c_j|\ge|i-j| $ . Here $ |x| $ means the absolute value of $ x $ .
However, Nauuo discovered that sometimes she couldn't find a solution because the chessboard was too small.
She wants to find the smallest chessboard on which she can put $ n $ pieces according to the rules.
She also wonders how to place the pieces on such a chessboard. Can you help her?
输入输出格式
输入格式
The only line contains a single integer $ n $ ( $ 1\le n\le 1000 $ ) — the number of chess pieces for the game.
输出格式
The first line contains a single integer — the minimum value of $ m $ , where $ m $ is the length of sides of the suitable chessboard.
The $ i $ -th of the next $ n $ lines contains two integers $ r_i $ and $ c_i $ ( $ 1\le r_i,c_i\le m $ ) — the coordinates of the $ i $ -th chess piece.
If there are multiple answers, print any.
输入输出样例
输入样例 #1
2
输出样例 #1
2
1 1
1 2
输入样例 #2
4
输出样例 #2
3
1 1
1 3
3 1
3 3
说明
In the first example, you can't place the two pieces on a $ 1\times1 $ chessboard without breaking the rule. But you can place two pieces on a $ 2\times2 $ chessboard like this:
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1173B/19a9324ad1d9f76a12004b1e06e1a6fc8ea5363a.png)
In the second example, you can't place four pieces on a $ 2\times2 $ chessboard without breaking the rule. For example, if you place the pieces like this:
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1173B/dd0c838eb5fa429a4dd839467d147e6034fac9bb.png)
then $ |r_1-r_3|+|c_1-c_3|=|1-2|+|1-1|=1 $ , $ |1-3|=2 $ , $ 1<2 $ ; and $ |r_1-r_4|+|c_1-c_4|=|1-2|+|1-2|=2 $ , $ |1-4|=3 $ , $ 2<3 $ . It doesn't satisfy the rule.
However, on a $ 3\times3 $ chessboard, you can place four pieces like this:
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1173B/b7f6bf4dffb399263283db89988092d0fdbbac58.png)