第二届国际信息学奥林匹克竞赛试题
第一题：
　　 在4×4的格子方阵中放了1至14共14个枚棋子，留下两个空格。图1是一种放置的例子，每步可将一枚棋子水平或垂直地移至相邻的空格，要求移成目标状态（图2所示，是唯一的）。
编写程序：
1.输入初始状态数据（空格用0表示，按自左至右逐格，自上至下逐行输入）。程序应能检查输入是否正确。
2.实现从初始状态到目标状态的转换。
3.输入结果，每一步都应在屏幕上显示：
（1）显示每一步的序号，最后的序号就是移动总步数；
（2）屏幕左方显示移动前的状态；
（3）屏幕右方显示移动后的状态。
4.要求能使移动步数最少。简析：算法： A* 算法
数据结构：数组
题型： III 型
难度： 8 分
编程时间：90 分钟
简述： 本题的难处在于第四个任务，很容易就溢出了，可以在溢出之前选取一些比较优的状态存下来，删去其余的状态后再继续搜索。

第二题：
值班警卫
某展览厅在任何时刻需要至少两名警卫值班。每一警卫的值班时间是一个连续的时间间隔[T1[i],T2[i]]，式中T1[i]和T2[i]分别表示第I个警卫值班的起始时间和结束时间。
给你一个值班时间表，你需要：
1.检查在时间间隔[0,endtime]中是否有至少两名警卫值班（用Yes/No回答）。如果上述条件不满足，需要：
2.找出警卫人数小于2的所有时间间隔（k,1分别为警卫值班小于2的起始时间，结束时间）以及在此间隔中的值班人数（0或1）。
3.求出至少需要增加多少名新警卫，才能使规定时间间隔中的每一时刻都至少有两
名警卫值班。注意：新增警卫的值班时间长度均为length,这是一个预先给定的数。
最后排出值班时刻表。
4.是否可能只改变原有值班人员值班的起始时间（不改动他们值班时间的长度，当
然也不增加新警卫），就做到每个时刻都至少有两名警卫值班？用Yes/No回答。
如是Yes，请列出被改变值班起始时间的人员序号及其新的起始与结束时间。
5.如果第4项要求是可能的，排出新的值班时刻表，要求改变值斑起始时间的警卫人数最少。对输入格式有如下规定，依次为（时间以分为单位，均取整数）：
endtime窘崾奔洌*
n揪廊耸*
T1[i] 镜贗个警卫值班起始时间；
T2[i] 镜趇个警卫值班结束时间；
上述两参数中：
length拘略鼍赖闹蛋嗍奔涑ざ取*

简析：
算法： 搜索算法
数据结构：数组
题型： III 型
难度： 7 分
编程时间：120 分钟
简述： 本题对数据量较大的测试数据光用搜索很难出结果，在没有好的方法
的时候就应该在搜索的过程中加入尽量多的判断条件来剪枝。