2006江苏队集训3实战训练1

1、金陵中学 2005-2006 年第二学期信息学竞赛实战训练(1)（请用实战的态度认真完成竞赛！）竞赛须知比赛常规实战训练为 4 小时 5 题，比赛中不得使本、等与比赛有关的工具。比赛结束前 5 分钟，请停止答题，最后检查程序是否无误。答题过程中请定期将写好的程序通过自行负责。系统提交至教师机，否则因死机带来的比赛提交比赛结束后 5 分钟内请通过系统完成提交您的解答。提交时请把源代码文件(.pas)和可执行文件(.exe)放入与你名字同名的文件夹中提交。例如：*.pas评测时不测试.exe 文件，但是 exe 文件将作为重要依据保存。评测环境比赛将采用全自动评测，编译器为 FPC2.0(Win3

2、2)/GCC342。FPC2.0 有良好的兼容性，不必担心程序出现意外情况。程序中严禁使用任何编译开关，严禁读写题目给定以外的文件。对于 Pascal 选手不得调用题目允许以外的库；对于 C+选手，严禁使用 STL 库。测试机为PentiumIII 550, 128M, WinXP。第 1 题 八数码源程序名 输入文件名输出文件名时间限制空间限制puzzle.?(pas| puzzle.in puzzle.out 3s/testcase32MBp)- 问题描述大家都熟悉得不能再熟悉的八数码问题：给定一个初始状态147258360每次可以把 0 和与它相邻的数字交换，问最少需要多少步，可以转换到

3、目标状态。- 输入数据三行三个整数，分别表示了目标状态。- 输出数据假如无法从初始状态到目标状态，输出一行Im要的步数。sible(不含引号)，否则输出最少需-140样例输入257368-2样例输出第 2 题 清扫仓库源程序名 输入文件名输出文件名时间限制空间限制clean.?(pas| clean.in clean.out 1s/testcase32MBp)- 问题描述的仓库已经有很多年没有清扫了，所以这次的计划是用河水来冲。仓库是一个 N*M的矩形，且每个格子里都堆满了尘土。相邻的格子之间都有门，要想让水冲进去，就必须打开这些门。这可不是一件容易的事情。因为有些格子里土堆得很高，因此打开门

4、就很费劲。推开一扇从 A 格子到 B 格子的门，需要的力度值为 B 房间里土堆的高度。写一个程序计算至少需要花费多少力气，才能使所有的格子都进水。- 输入数据第一行为 N 和 M(N, M = 40)，代表仓库的大小。以后 N 行，每行 N 个整数（每个数不超过 100），分别表示每个格子里土堆的厚度。- 输出数据你得到的结果。所有的格子必须都进水。水是从左上角的格子进去的。-3371样例输入4536245187样例输出-26第 3 题 数列源程序名 输入文件名输出文件名时间限制空间限制sequence.?(pas| sequence.in sequence.out 1s/testcase32

5、MBp)- 问题描述一个简单的数列问题：给定一个长度为 n 的数列，求这样的三个元素 ai, aj, ak 的个数，满足 ai ak，且 i j k。- 输入数据第一行是一个整数 n(n = 50000)。第二行 n 个整数 ai(0 = ai = 32767)。- 输出数据一个数，满足 ai ak (i j k)的个数。- 样例输入51 2 3 4 1- 样例输出6第 4 题 试题安排源程序名 输入文件名输出文件名时间限制空间限制arrange.?(pas| arrange.in arrange.out 1s/testcase32MBp)- 问题描述给省队选拔赛命题的时候，手下有 N 个命题

6、人，N 种不同类型的试题，其中每人命一题。因为每个命题人对不同题型的掌握程度不同，所以他们编出的试题难度也有不同（这用一个难度数值来表示）。为了尽可能地刁难大家，而且所有题的难度值总和最大。决定出一张 N 个题的试卷，- 输入数据第一行为 N(N = 100)，代表命题人的个数。以后 N 行，每行 N 个整数（每个数不超过 100），第 i 行 j 列的数表示第 i 个人出的第 j种题目的难度大小。- 输出数据一行，表示试卷难度的最大值。- 样例输入350 50 110 100 10100 10 10- 样例输出201第 5 题 良好的感觉源程序名 输入文件名输出文件名时间限制空间限制feelgood.?(pas| feelgood.in feelgood.out 3s/testcase32MBp)- 问题描述jyy 做了一个感觉分析器。每一天，人都有一个感受值 Ai，Ai 越大，表示人感觉越舒适。在一段时间i, j内，人的舒适程度定义为i, j中最不舒服的那一天的感受值 * i,j中每一天感受值的和。现在给出 jyy 在连续 N 天中的感受值，请问，在哪一段时间，jyy感觉最舒适？- 输入数据第一行为 N(N