题目简述
题目要求在一个 \(m\times m\) 的棋盘上放置 \(n\) 个棋子，使得满足以下规则：对于任意的两个棋子 \(i\) 和 \(j\) ，有 \(|r_i-r_j|+|c_i-c_j|\geq|i-j|\)。
思路简述
\(m\) 的最小值为 \(\frac{n}{2}+1\)。
接下来我们详细解释一下为什么这样的放置方式能够满足规则。
思路讲解
首先我们观察到，棋子的坐标差的绝对值最大为 \(m-1\)。那么为了满足规则 \(|r_i-r_j|+|c_i-c_j|\geq|i-j|\)，我们可以将棋子按照 \(i\) 的顺序依次放在第 \(i\) 行和第 \(1\) 列。这样就能保证对于任意的两个棋子 \(i\) 和 \(j\)，有 \(|r_i-r_j|+|c_i-c_j|\geq|i-j|\)。
假设有两个棋子 \(i\) 和 \(j (i<j)\)，它们的坐标分别是 \((r_i,c_i)\) 和 \((r_j,c_j)\)。由于棋子按照 \(i\) 的顺序依次放置，所以 \(r_i\leq r_j\)，那么根据放置方式可知，那么根据放置方式可知，\(r_i=i\) 且 \(r_j=j\)。因此有 \(|r_i-r_j|=|i-j|\)，同理 $ |c_i-c_j|\geq0$。所以对于任意的两个棋子 \(i\) 和 \(j\)，有 \(|r_i-r_j|+|c_i-c_j|\geq|i-j|\) 成立。
代码实现
#include<iostream>
using namespace std;
int n,m;
int main() {
cin >> n;
m=n/2+1;
cout<<m<<endl;
for(int i=1;i<=m;i++)
cout<<i<<" "<<1<<endl;
for(int i=2;i<=n-m+1;i++)
cout<<m<<" "<<i<<endl;
return 0;
}