第3届信息学分区联赛提高组复赛试题

第三届分区联赛提高组复赛
1997年第三届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题
（高中组 竞赛用时：3小时）
一.在N*N的棋盘上(1<=N<=10)填入1,2,...N*N共N*N个数,使得任意两个相邻的数之和为素数.
例如,当N=2时,有
1
2
4
3
其相邻数的和为素数的有:1+2,1+4,4+3,2+3
当N=4时,一种可以填写的方案如下:
1
2
11
12
16
15
8
5
13
4
9
14
6
7
10
3
在这里我们约定:左上角的格子里必须放数字1
程序要求:
输入:N
输出:若有多种解,则需输出第一行,第一列之和均为最小的排列方案;若无解,则输出"NO!"
二.代数表达式的定义如下:
代数表达式:
项:
因子:
字母:
例如,下面式子是合法的代数表达式:
a;
a+b*(a+c);
a*a/(b+c);
下列式子是不合法的代数表达式:
ab;
a+b*(c+d); {因子中无字母d}
程序要求:
输入:输入一个字符串,以";"结束,(";"本身不是代数表达式中字符,仅作为结束符号)
输出:若表达式正确,则输出:"OK";
若表达式不正确,则输出"ERROR",及错误类型
错误类型约定:
1.式子中出现不允许的字符;
2.括号不配对;
3.其他错误
例如:输入a+(b);
输出:OK
例如:输入a+(b+c*a;
输出 error 2
三.骑士游历:
设有一个n*m的棋盘(2<=n<=50,2<=m<=50),如下图,在棋盘上任一点有一个中国象棋马,
马走的规则为:
1.马走日字 2.马只能向右走
即如下图所示:
任务1:当N,M 输入之后,找出一条从左下角到右上角的路径.
例如:输入 N=4,M=4
输出:路径的格式:(1,1)->(2,3)->(4,4)
若不存在路径,则输出"no"
任务2:当N,M 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目.
例如:(N=10,M=10),(1,5)(起点),(3,5)(终点)
输出:2(即由(1,5)到(3,5)共有2条路径)
输入格式:n,m,x1,y1,x2,y2(分别表示n,m,起点坐标,终点坐标)
输出格式:路径数目(若不存在从起点到终点的路径,输出0)