/ C++党 / 题库 /

[noip1997]棋盘问题

[noip1997]棋盘问题

时间限制:1s 空间限制:1024KiB


题目来源

本题是1997年提高组的第一题(难度:提高+/省选-),希望你能把它做出来,加油!!!(题目经过了一定的改变,直接抄洛谷上的代码是过不了的哦!)^_^

题目描述

在N×N的棋盘上,填入1,2,…,N^2共N^2个数,使得任意两个相邻的数之和为素数,例如:当N=2时,有

1 2
4 3

其相邻数的和为素数的有:1+2=3,1+4=5,4+3=7,2+3=5
当N=4时,一种可以填写的方案如下:

1 2 11 12
16 15 8 5
13 4 9 14
6 7 10 3

在这里我们约定:左上角第1个格子里必须填数字1。

输入输出格式

输入格式:

一个整数N。

输出格式:

如果有多组解,请输出第I行和第I列之和最小的解,其中1<=I<=N,如果仍存在多组解的情况,请输出字典序最小的哪一组解,若没有解,直接输出“NO”(双引号不用输出)。

输入输出样例

Input #1

1

Output #1

NO

Input #2

2

Output #2

1 2
4 3

时间和空间限制

每个测试点时间1s,空间1024KiB。

数据范围约定

100%的数据保证1≤N≤5。

提供者

Vijos 梁忆炎

信息

难度
5
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
16
已通过
2
通过率
12%
上传者