QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 4325. Kraljice

统计

非官方翻译,来自 Qingyu

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

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

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

输入格式

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

输出格式

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

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

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

子任务

子任务 分值 额外限制
$1$ $6$ $1 \leq N \leq 16$
$2$ $11$ $1 \leq N \leq 64$
$3$ $28$ $1 \leq N \leq 256$
$4$ $55$ $1 \leq N \leq 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

样例 3 解释

problem_4325_1.png