QOJ.ac
QOJ
Time Limit:
1 s
Memory Limit:
512 MB
Total points:
100
# 4325. Kraljice
统计
The problem was used in the following contest:
非官方翻译,来自 Qingyu。
有一个 N×N 的棋盘,你想要在上面放置尽可能多的皇后,并遵守以下规则:
- 一个位置可以放置皇后,当且仅当其没有被任何皇后覆盖,且能被恰好偶数个皇后所攻击到。
注意:皇后可以攻击所有与它在同一行、同一列或同一个对角线上的位置。
输入格式
输入只有一行,包含一个整数 N。
输出格式
输出的第一行包含一个整数 K,表示所能放置的皇后数量的最大值。
接下来 K 行,每行两个整数 Ri,Si,描述这一步将皇后放置在格子 (Ri,Si) 上。
如果有多种合法的方案,你可以输出任意一种。
子任务
子任务 | 分值 | 额外限制 |
---|---|---|
1 | 6 | 1≤N≤16 |
2 | 11 | 1≤N≤64 |
3 | 28 | 1≤N≤256 |
4 | 55 | 1≤N≤1024 |
样例数据
样例 1 输入
1
样例 1 输出
1
1 1
样例 2 输入
2
样例 2 输出
1
1 1
样例 3 输入
3
样例 3 输出
9
2 3
3 1
2 2
1 1
3 3
3 2
1 2
1 3
2 1