#P10196. [2021年NK的NOI模拟]寻宝
[2021年NK的NOI模拟]寻宝
Problem A. 寻宝 (find.c/cpp)
你站在一个的棋盘上,其中第 行第列的格子坐标为 。
每一个格子里面有一个宝箱,其中 这个格子中的宝箱中藏着宝物,而其余的每一个宝箱都藏着一把开启另一个宝箱的钥匙。你在拿到钥匙后就已经知道了这个钥匙可以开启哪一个宝箱。 你现在站在,手里拿着一把钥匙。为了拿到宝物,你必须顺次开启若干个宝箱,最后回到 这个格子拿到宝物。
如果你现在站在,而你想到达 这个点,那么你走过的距离就是, 也就是曼哈顿距离。
现在你想知道,你最坏情况下需要走多远的距离才能拿到宝物。构造一组方案。
一句话题意:一个的网格,选出其中包含 的若干个点,使得所选点集上一条哈密顿回路的长度尽可能大,距离定义为曼哈顿距离。
Input
一行两个用空格隔开的正整数。
Output
第一行输出一个整数,表示最远距离。
接下来一行输出一个整数,表示最远情况下需要经过多少个点。
接下来 行,每一行输出 个坐标,其中第 个坐标为 ,描述一条路径。你需要保证 ,各点位于棋盘中,前 个点两两不同,且闭合路径的曼哈顿总长度等于 。
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
数据规模与约定: 对于 % 的数据,保证。 subtask 1:(10 分)。 subtask 2:(25 分)保证 是偶数。 subtask 3:(25 分)保证 是奇数。 subtask 4:(40 分)无特殊限制。