#P10196. [2021年NK的NOI模拟]寻宝

    ID: 9311 传统题 1000ms 256MiB 尝试: 11 已通过: 1 难度: 8 上传者: 标签>图论动态规划CF2400构造数学搜索树形DP

[2021年NK的NOI模拟]寻宝

Problem A. 寻宝 (find.c/cpp)

你站在一个n×mn\times m的棋盘上,其中第xx 行第yy列的格子坐标为 (x,y)(x,y)。

每一个格子里面有一个宝箱,其中 (1,1)(1,1) 这个格子中的宝箱中藏着宝物,而其余的每一个宝箱都藏着一把开启另一个宝箱的钥匙。你在拿到钥匙后就已经知道了这个钥匙可以开启哪一个宝箱。 你现在站在(1,1)(1,1),手里拿着一把钥匙。为了拿到宝物,你必须顺次开启若干个宝箱,最后回到 (1,1)(1,1) 这个格子拿到宝物。

如果你现在站在(x1,y1)(x_{1},y_{1}),而你想到达(x2,y2)(x_{2},y_{2}) 这个点,那么你走过的距离就是∣x1−x2∣+∣y1−y2∣|x_{1}-x_{2}|+|y_{1}-y_{2}|, 也就是曼哈顿距离。

现在你想知道,你最坏情况下需要走多远的距离才能拿到宝物。构造一组方案。

一句话题意:一个n×mn\times m的网格,选出其中包含 (1,1)(1,1) 的若干个点,使得所选点集上一条哈密顿回路的长度尽可能大,距离定义为曼哈顿距离。

Input

一行两个用空格隔开的正整数n,mn,m。

Output

第一行输出一个整数ll,表示最远距离。

接下来一行输出一个整数kk,表示最远情况下需要经过多少个点。

接下来k+1k+1 行,每一行输出 11 个坐标,其中第ii 个坐标为 (xi,yi)(x_{i},y_{i}),描述一条路径。你需要保证 x1=y1=xk+1=yk+1=1x_1=y_1=x_{k+1}=y_{k+1}=1,各点位于棋盘中,前 kk 个点两两不同,且闭合路径的曼哈顿总长度等于 ll。

Examples

样例输入

3 3

样例输出

24
8
1 1
2 3
3 1
1 2
3 3
2 1
1 3
3 2
1 1

样例解释:

样例输入

1 1

样例输出

0
1
1 1
1 1

Notes

数据规模与约定: 对于 100100% 的数据,保证1≤n,m≤10001\le n,m\le 1000。 subtask 1:(10 分)n,m≤3n,m\le 3。 subtask 2:(25 分)保证n,mn,m 是偶数。 subtask 3:(25 分)保证n,mn,m 是奇数。 subtask 4:(40 分)无特殊限制。