QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[0]

# 4325. Kraljice

Statistics

非官方翻译,来自 Qingyu

有一个 N×N 的棋盘,你想要在上面放置尽可能多的皇后,并遵守以下规则:

  • 一个位置可以放置皇后,当且仅当其没有被任何皇后覆盖,且能被恰好偶数个皇后所攻击到。

注意:皇后可以攻击所有与它在同一行、同一列或同一个对角线上的位置。

输入格式

输入只有一行,包含一个整数 N

输出格式

输出的第一行包含一个整数 K,表示所能放置的皇后数量的最大值。

接下来 K 行,每行两个整数 Ri,Si,描述这一步将皇后放置在格子 (Ri,Si) 上。

如果有多种合法的方案,你可以输出任意一种。

子任务

子任务 分值 额外限制
1 6 1N16
2 11 1N64
3 28 1N256
4 55 1N1024

样例数据

样例 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

样例 3 解释

problem_4325_1.png