NOIP历年复赛提高组试题.doc

全国信息学奥林匹克分区联赛（NOIP）复赛提高组试题
第一届全国信息学奥林匹克分区联赛（NOIP1995）复赛试题
（提高组 竞赛用时：3.5小时）
1、编码问题
设有一个数组A:ARRAY[0..N-1]OFINTEGER；
数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i≠j时）。
例如：N=6时，有：A=（4，3，0，5，1，2）
此时，数组A的编码定义如下：
A[0]的编码为0；
A[i]的编码为：在A[0]，A[1]，…，A[i-1]中比A[i]的值小的个数（i=1，2，…，N-1）
∴上面数组A的编码为：B=（0，0，0，3，1，2）
程序要求解决以下问题：
① 给出数组A后，求出其编码。
② 给出数组A的编码后，求出A中的原数据。

2、灯的排列问题
设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，……Nk（k表示不同颜色灯的个数）。
放灯时要遵守下列规则：
① 同一种颜色的灯不能分开；
② 不同颜色的灯之间至少要有一个空位置。
例如：N=8（格子数）；R=2（红灯数）；B=3（蓝灯数），放置的方法有：
R-B顺序

R
R

B
B
B

R
R

B
B
B

R
R

B
B
B

R
R

B
B
B

R
R

B
B
B

R
R

B
B
B

B-R顺序

B
B
B

R
R

B
B
B

R
R

B
B
B

R
R

B
B
B

R
R

B
B
B

R
R

B
B
B

R
R

放置的方法总数为12种。
数据输入的方式为：
N
P1（颜色，为一个字母） N1（灯的数量）
P2 N2
……
Q（结束标记，Q本身不是灯的颜色）
程序要求：求出一种顺序的放置（排列）方案及放置（排列）方案总数。

3、积木块上的数字
设有一个四层的积木块，1～4层积木块的数量依次为：5，6，7，8，如下图所示放置：

8
15
8
5
16
9
14

2
3
4
1
4
3
2
6

其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。
计算的方法是：第三层的某个数据A是由第四层相邻的两个数据B，C经过某种计算后产生的：
A
B
C

计算所用到的计算符为：+，-，，且无优先级之分（自左向右计算），运算符最多为2个。如：
3+45=35 54+3=23
可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的：
A=BC+B
也就是：8=23+2，15=34+3，……14=26+2
程序要求：
给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。
① 输入数据不存在出错的情况，同时也不会超过整数的范围。
② 计算时可允许出现以下情况：
A=B （即可理解为运算符的个数为零）
A=BB+B （即全部由B产生）

第二届全国信息学奥林匹克分区联赛（NOIP1996）复赛试题
（提高组 竞赛用时：3小时）
1、比赛安排
设有有2 n（n<=6）个球队进行单循环比赛，计划在2 n – 1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2 n – 1天内每个队都与不同的对手比赛。
例如n=2时的比赛安排：
队 1 2 3 4
比赛 1==2 3==4 一天
1==3 2==4 二天
1==4 2==3 三天

2、数制转换
设有一个字符串A$的结构为： A$=’m<n>p’，其中m为数字串（长度<=20），而n,p均为1或2位的数字串（其中所表达的内容在2-10之间）。
程序要求：从键盘上读入A$后（不用正确性检查），将A$中的数字串m(n进制)，以p进制的形式输出。
例如：A$=’48<10>8’，其意义为：将10进制数48，转换成8进制数输出。
输出结果为：48<10>=60<8>

3、挖地雷
在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。

V1 V 2 V3 V4 V5

例如：

【题目要求】
当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。
【输入格式】
N （表示地窖的个数）
Ｗ1 W2 W3，…… WN （表示每个地窖中埋藏的地雷数量）
A12 …… A1N
A23 …… A2N
……
AN-1 N
【输出格式】
K1--K2--……KV （挖地雷的顺序）
MAX （挖地雷的数量）
例如：

　　　 　⑩ ⑧ ④ ⑦ ⑥

其输入格式为：
5
10，8，4，7，6
1 1 1 0
0 0 0
1 1
1
输出为：
1 –3 -4 -5
max=27

4．砝码称重
设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），问可以称为多少种不同的重量。
输入方式：a1 a2 a3 a4 a5 a6
（分别表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）
输出方式：Total=N
（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）
如输入：1_1_0_0_0_0 （注：下划线表示空格）
则输出：TOTAL=3 （表示可以称出1g，2g，3g三种不同的重量。）

第三届全国信息学奥林匹克分区联赛（NOIP1997）复赛试题
（提高组 竞赛用时：3小时）
1、 棋盘上的素数
在N*N的棋盘上（1≤N≤10），填入1，2，…，N*N共N*N个数，使得任意两个相邻的数之和为素数。（30%）
其相邻数的和为素数的有：
1+2，1+4，4+3，2+3
例如：当N=2时，有：
1
2
4
3
当N=4时，一种可以填写的方案如下：
1
2
11
12
16
15
8
5
13
4
9
14
6
7
10
3
在这里我们约定：左上角的格子里必须填数字1。
【程序要求】
输入：N
输出：如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“NO！”。

2、 代数表达式正确性判定
代数表达式的定义如下：

a
c
b
字母

例如，下面的式子是合法的代数表达式：
a；
a+b*(a+c)；
a*a/(b+c)；
下面的式子是不合法的代数表达式：
Ab；
a+a*/(b+c)；
【程序要求】
输入：输入一个字符串，以“；”结束，“；”本身不是代数表达式中字符，仅作为结束）；
输出：若表达式正确，则输出“OK”；若表达式不正确，则输出“ERROR”，及错误类型。
错误类型约定：
1． 式子中出现不允许的字符；
2． 括号不配对；
3． 其它错误。
例如：输入：a+(b); 输出：OK
例如：输入：a+(b+c*a; 输出：ERROR 2

3、 骑士游历：
设有一个n*m的棋盘（2≤n≤50，2≤m≤50），如下图，在棋盘上左下角有一个中国象棋马。
（n,m）

马

(1,1)
马走的规则为：
1）马走日字；
2）马只能向右走
即如下图如示：

任务1：
当n,m输入之后，找出一条从左下角到右上角的路径。
例如，输入：n=4，m=4
(4,4)
(1,1)

输出：路径的格式：(1,1)→(2,3)→(4,4)。若不存在路径，则输出‘NO’
任务2：
当n，m给出之后，同时给出马起点的位置和终点的位置，试找出从起点到终点的所有路径的数目。
例如：n=10，m=10,
（1，5）（起点），（3，5）（终点）
10
9
8
7
6
5
4
3
2
1

1 2 3 4 5 6 7 8 9 10

输出：2 （即表示由（1，5）到（3，5）共有2条路径）
输入格式：n m x1 y1 x2 y2 (分别表示n,m,起点坐标，终点坐标)
输出格式：路径数目（若不存在从起点到终点的路径，则输出0）
第四届全国信息学奥林匹克分区联赛（NOIP1998）复赛试题
（提高组 竞赛用时：3小时）
1、火车上的人数
火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。从第3站起（包括第3站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有N个车站，始发站上车的人数为a，最后一站下车的人数是m（全部下车）。试问x站开出时车上的人数是多少？
输入：a，n，m和x
输出：从x站开出时车上的人数。

2、数的联接
设有n个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213
又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613
程序输入：n
n个数 （用空格相隔的n个整数）
程序输出：联接成的多位数

3、进位制
著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。 例如：
+
L
K
V
E
L
L
K
V
E
K
K
V
E
KL
V
V
E
KL
KK
E
E
KL
KK
KV

其含义为：
L+L=L，L+K=K，L+V=V，L+E=E
K+L=K，K+K=V，K+V=E，K+E=KL ……
E+E=KV

根据这些规则可推导出：L=0，K=1，V=2，E=3；同时可以确定该表表示的是4进制加法。
程序输入：n（n≤9）表示行数。以下n行，每行包括n个字符串，每个字串间用空格隔开。（字串仅有一个为‘+’号，其它都由大写字母组成）
程序输出：
① 各个字母表示什么数，格式如：L=0，K=1，……
② 加法运算是几进制的。
③ 若不可能组成加法表，则应输出“ERROR！”
第五届全国信息学奥林匹克分区联赛（NOIP1999）复赛试题
（提高组 竞赛用时：3小时）
1、 拦截导弹
【问题描述】某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
【输入样例】
389 207 155 300 299 170 158 65
【输出样例】
6 （最多能拦截的导弹数）
2 （要拦截所有导弹最少要配备的系统数）

2、回文数
【问题描述】若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。
又如：对于10进制数87：
STEP1：87+78 = 165 STEP2：165+561 = 726
STEP3：726+627 = 1353 STEP4：1353+3531 = 4884
在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。
写一个程序，给定一个N（2<=N<=10或N=16）进制数M，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”
【输入样例】
9 87
【输出样例】
STEP=6
3、旅行家的预算
【问题描述】一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
【输入样例】
275.6 11.9 27.4 2.8 2 (分别表示D1，C，D2，P和N)
油站号I
离出发点的距离Di
每升汽油价格Pi
1
102.0
2.9
2
220.0
2.2
【输出样例】
26.95 （该数据表示最小费用）

4、邮票面值设计
【问题描述】给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1～MAX之间的每一个邮资值都能得到。
例如，N=3，K=2，如果面值分别为1分、4分，则在1分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。
【输入样例】
3 2 （分别为N和K之值）
【输出样例】
1 3
MAX=7

第六届全国信息学奥林匹克分区联赛（NOIP2000）复赛试题
（提高组 竞赛用时：3小时）
1、进制转换
【问题描述】我们可以用这样的方式来表示一个十进制数： 将每个阿拉伯数字乘以一个以该数字所处位置的（值减1）为指数，以10为底数的幂之和的形式。例如：1２３可表示为 1*10２＋２*101＋３*100这样的形式。
与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置的（值-1）为指数，以２为底数的幂之和的形式。一般说来，任何一个正整数Ｒ或一个负整数-Ｒ都可以被选来作为一个数制系统的基数。如果是以Ｒ或-Ｒ为基数，则需要用到的数码为 0，1，．．．．Ｒ-1。例如，当Ｒ＝７时，所需用到的数码是0，1，２，３，４，５和６，这与其是Ｒ或-Ｒ无关。如果作为基数的数绝对值超过10，则为了表示这些数码，通常使用英文字母来表示那些大于９的数码。例如对1６进制数来说，用Ａ表示10，用Ｂ表示11，用Ｃ表示1２，用Ｄ表示1３，用Ｅ表示1４，用Ｆ表示1５。
在负进制数中是用-Ｒ 作为基数，例如-1５（十进制）相当于110001（-２进制），并且它可以被表示为２的幂级数的和数：
1100001＝1*(-２)5+1*(-２)4+0*(-２)3+0*(-２)2+0*(-２)1+1*(-２)0
【问题求解】设计一个程序，读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数，-Ｒ∈｛-２，-３，-４，．．．，-２0｝
【数据输入】输入的每行有两个输入数据。第一个是十进制数Ｎ（-32768＜＝Ｎ＜＝32767）； 第二个是负进制数的基数-Ｒ。
【数据输出】结果显示在屏幕上，相对于输入，应输出此负进制数及其基数，若此基数超过10，则参照1６进制的方式处理。
【输入样例】
30000　-２
-20000　-２
28000　-1６
-25000　-1６
【输出样例】
30000＝11011010101110000 （ｂａｓｅ　-２）
-20000＝1111011000100000　 （ｂａｓｅ　-２）
28000＝19180　　 　（ｂａｓｅ　-1６）
-25000＝7FB8　　 　（ｂａｓｅ　-1６）
2、乘积最大
【问题描述】今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312， 当N=3，K=1时会有以下两种分法：
1）3*12=36
2）31*2=62
这时，符合题目要求的结果是：31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
【数据输入】程序的输入共有两行：
第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）
第二行是一个长度为N的数字串。
【数据输出】结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。
【输入样例】
4 2
1231
【输出样例】
62

3、单词接龙
【问题描述】单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。
【数据输入】输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
【数据输出】只需输出以此字母开头的最长的“龙”的长度
【输入样例】
5
at
touch
cheat
choose
tact
a
【输出样例】
23 （连成的“龙”为atoucheatactactouchoose）
4、方格取数
【问题描述】设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：
向右
A 1 2 3 4 5 6 7 8
0
0
0
0
0
0
0
0
0
0
13
0
0
6
0
0
0
0
0
0
7
0
0
0
0
0
0
14
0
0
0
0
0
21
0
0
0
4
0
0
0
0
15
0
0
0
0
0
0
14
0
0
0
0
0
0
0
0
0
0
0
0
0
0

1
2
3
4
5
6
7
8

向
下
B

某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
【数据输入】输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
【数据输出】只需输出一个整数，表示2条路径上取得的最大的和。
【输入样例】
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
3 15
2 14
0 0
【输出样例】
67
第七届全国信息学奥林匹克分区联赛（NOIP2001）复赛试题
（提高组 竞赛用时：3小时）
1、一元三次方程求解
【问题描述】
有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数（a，b，c，d 均为实数），并约定该方程存在三个不同实根（根的范围在-100至100之间），且根与根之差的绝对值≥1。
要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后2位。
【提示】：
记方程f(x)=0，若存在2个数x1和x2，且x1<x2, f(x1)*f(x2)<0，则在（x1,x2）之间一定有一个根。
【样例】
输入
1 -5 -4 20
输出
-2.00 2.00 5.00

2、数的划分
【问题描述】
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序).
例如:n=7,k=3,下面三种分法被认为是相同的。
1，1，5； 1，5，1； 5，1，1；
问有多少种不同的分法。
输入：n,k (6<n≤200，2≤k≤6)
输出：一个整数，即不同的分法。
【输入输出样例】
输入：
7 3
输出：
4 { 4种分法为：1,1,5；1,2,4；1,3,3; 2,2,3 说明部分不必输出 }

3、统计单词个数
【问题描述】给出一个长度不超过200的由小写英文字母组成的字母串（约定：该字串以每行20个字母的方式输入，且保证每行一定为20个）。要求将此字母串分成k份（1<k≤40）， 且每份中包含的单词个数加起来总数最大（每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可以包含this和is ，选用this 之后就不能包含th）。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。
【输入格式】全部输入数据放在文本文件input3.dat中, 其格式如下：
第一行为一个正整数（0<n≤5）表示有n 组测试数据
每组的第一行有二个正整数：（p,k），p表示字串的行数；k表示分为k个部分。
接下来的 p行，每行均有20个字符。
再接下来有一个正整数s，表示字典中单词个数。（1≤s≤6）
接下来的s行，每行均有一个单词。
【输出格式】
结果输出至屏幕，每行一个整数，分别对应每组测试数据的相应结果。
【样例】
输入：1
1 3
t h i s i s a b o o k y o u a r e a o h
4
is
a
ok
sab
输出： //说明：（不必输出）
7 // this/ isabookyoua/reaoh

4、Car的旅行路线
【问题描述】
又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第i个城市中高速铁路的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。
Y
X
图例
机场
高速铁路
飞机航线
注意：图中并没有标出所有的铁路与航线。

那么Car 应如何安排到城市B的路线才能尽可能的节省花费呢？她发现这并不是一个简单的问题，于是她来向你请教。
【任务】
找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。
输入文件：键盘输入文件名
输 出：到屏幕（输出最小费用，小数点后保留2位。）
【输入格式】
第一行为一个正整数n（0≤n≤10），表示有n组测试数据。
每组的第一行有四个正整数s，t，A，B。
S (0<S≤100)表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，（1≤A，B≤S）。
接下来有S行，其中第i行均有7个正整数xi1 , yi1 , xi2 , yi2 , xi3 , yi3 , Ti , 这当中的 （xi1 , yi1 ），（xi2 , yi2 ），（xi3 , yi3 ）分别是第i 个城市中任意三个机场的坐标，Ti为第i个城市高速铁路单位里程的价格。
【输出格式】共有n行，每行一个数据对应测试数据。
【样 例]】
输入
1
3 10 1 3
1 1 1 3 3 1 30
2 5 7 4 5 2 1
8 6 8 8 11 6 3
输出：
47.55
4、修公路
【问题描述】
在一个平面的地图上有A，B两个城市，同时在该平面上划出若干个矩形区域（个数≤10），这些区域不重合，也不包含A，B。如下图所示。
x
y
A
S
B
R
P
T
Q

矩形的边平行于坐标轴。
现准备从A到B修建一条公路，当公路穿过某个区域时，可以直接通过某个区域的顶点，也可以穿过区域的边。如上图中的路径都是合法的：
平面上与每个矩形区域（包括边界）的公路单位造价不相同。在不同区域之间选用平面造价，在同一个区域内（包括边界）选用该区域的造价。
【问题所求】
选择一条路径，使能得到最小的修建费用。
【输入格式】
全部输入数据放在文本文件input4.dat中, 其格式如下：
第一行为一个正整数（0<n≤10）表示有n 组测试数据。每组的第一行分别有五个正整数：AX，AY，BX，BY及T；AX，AY表示A点坐标，BX，BY 表示B点坐标，T表示平面上的单位造价；
第二行一个正整数S，表示矩形的个数；
接下来有S行，每行均有5个正整数，分别表示一个矩形区域的左下角，右上角的坐标以及该区域的造价。
【输出格式】
n个表示最小造价的数（精确到小数点后2位）,每行一个数据。
【样例】
输入：
1
1 2 5 5 13
2
2 2 4 4 8
5 1 7 4 6
输出：
54．01

第八届全国信息学奥林匹克分区联赛（NOIP2002）复赛试题
（提高组 竞赛用时：3小时）
1、均分纸牌（存盘名 NOIPG1）
[问题描述]
有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。
移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如 N=4，4 堆纸牌数分别为：
①　9　②　8　③　17　④　6
移动3次可达到目的：
从 ③ 取 4 张牌放到 ④ （9 8 13 10） -> 从 ③ 取 3 张牌放到 ②（9 11 10 10）-> 从 ② 取 1 张牌放到①（10 10 10 10）。
[输 入]
键盘输入文件名。文件格式：
N（N 堆纸牌，1 <= N <= 100）
A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）
[输 出]
输出至屏幕。格式为：
所有堆均达到相等时的最少移动次数。
[输入输出样例]
a.in：
4
9 8 17 6
屏慕显示：
3
2、字串变换 （存盘名: NOIPG2）
[问题描述]:
已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:
　A1$ -> B1$
　A2$ -> B2$
规则的含义为：在 A＄中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ …。
例如：A$＝'abcd'　B$＝'xyz'
变换规则为：
‘abc’->‘xu’　‘ud’->‘y’　‘y’->‘yz’
则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：
　‘abcd’->‘xud’->‘xy’->‘xyz’
共进行了三次变换，使得 A$ 变换为B$。
[输入]:
键盘输人文件名。文件格式如下：
　A$ B$
　A1$ B1$ \
　A2$ B2$  |-> 变换规则
　... ... / 
所有字符串长度的上限为 20。
[输出]:
输出至屏幕。格式如下：
若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出"NO ANSWER!"
[输入输出样例]
b.in:
　abcd wyz
　abc xu
　ud y
　y yz

屏幕显示：
　3

3、自由落体（存盘名:NOIPG3）
[问题描述]:
在高为 H 的天花板上有 n 个小球，体积不计，位置分别为 0，1，2，…．n-1。在地面上有一个小车（长为 L，高为 K，距原点距离为 S1）。已知小球下落距离计算公式为 d＝1/2*g*(t^2)，其中 g=10，t 为下落时间。地面上的小车以速度 V 前进。
如下图：
小车与所有小球同时开始运动，当小球距小车的距离 <= 0.00001 时，即认为小球被小车接受（小球落到地面后不能被接受）。
请你计算出小车能接受到多少个小球。
[输入]：
键盘输人：
H，S1，V，L，K，n （l<=H，S1，V，L，K，n <=100000）
[输出]：
屏幕输出：
小车能接受到的小球个数。
[输入输出样例]
[输入]:
5.0 9.0 5.0 2.5 1.8 5
[输出]:
　1
4、矩形覆盖（存盘名NOIPG4）
[问题描述]:
在平面上有 n 个点（n <= 50），每个点用一对整数坐标表示。例如：当 n＝4 时，4个点的坐标分另为：p1（1，1），p2（2，2），p3（3，6），P4（0，7），见图一。

这些点可以用 k 个矩形（1<=k<=4）全部覆盖，矩形的边平行于坐标轴。当 k=2 时，可用如图二的两个矩形 sl，s2 覆盖，s1，s2 面积和为 4。问题是当 n 个点坐标和 k 给出后，怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为 0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开（边线与顶点也都不能重合）。
[输入]:
键盘输人文件名。文件格式为
　n k
　xl y1
　x2 y2
　... ...
　xn yn （0<=xi,yi<=500)
[输出]:
输出至屏幕。格式为：
一个整数，即满足条件的最小的矩形面积之和。
[输入输出样例]
d.in :
　4 2
　1 1
　2 2
　3 6
　0 7

屏幕显示：
4

第九届全国信息学奥林匹克分区联赛（NOIP2003）复赛试题
（提高组 竞赛用时：3小时）
1、神经网络
【问题背景】
人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。
【问题描述】
在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经
元之间至多有一条边相连，下图是一个神经元的例子：

神经元〔编号为1）
图中，X1—X3是信息输入渠道，Y1－Y2是信息输出渠道，C1表示神经元目前的状态，
Ui是阈值，可视为神经元的一个内在参数。
神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神
经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元
输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。

兰兰规定，Ci服从公式：（其中n是网络中所有神经元的数目）

公式中的Wji（可能为负值）表示连接j号神经元和 i号神经元的边的权值。当 Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒
它会向其他神经元传送信号，信号的强度为Ci。
如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。
现在，给定一个神经网络，及当前输入层神经元的状态（Ci），要求你的程序运算出最后网
络输出层的状态。
【输入格式】
输入文件第一行是两个整数n（1≤n≤20）和p。接下来n行，每行两个整数，第i＋1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wij，表示连接神经元i、j的边权值为Wij。
【输出格式】
输出文件包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状
态，两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态，并且按照编号由
小到大顺序输出！
若输出层的神经元最后状态均为 0，则输出 NULL。
【输入样例】
5 6
1 0
1 0
0