第七届全国青少年信息学（计算机）奥林匹克分区联赛提高组复赛题测试表
__________赛区 __________学校 __________班 邮编__________
第一题： 一元三次方程求解 共20分
序号 a b c d 输出 分值 得分
1 1 -2 -1 2 -1.00 1.00 2.00 5
2 1 -4.65 2.25 1.4 -0.35 1.00 4.00 5
3 1 10 -1 -10 -10.00 -1.00 1.00 5
4 1 -1.8 -8.59 -0.84 -2.10 -.010 4.00 5
第二题： 数的划分 共20分
序号 n k 输出 分值 得分
1 7 2 3 2
2 20 4 64 3
3 100 5 38225 4
4 200 5 583464 5
5 200 6 4132096 6
第三题： 统计单词个数 共30分
序号 输入文件名 输出 分值 得分
1 INPUT3.DAT 8 4
2 13 5
3 193 6
4 125 7
5 65 8
第四题： Car的旅行路线 共30分
序号 输入 输出 分值 得分
1 INPUT41.DAT 0.00 4
2 INPUT42.DAT 214.14 5
3 INPUT43.DAT 310.00 5
4 INPUT44.DAT 1885.03 8
5 INPUT45.DAT 1924.23 8 2001年全国青少年信息学（计算机）奥林匹克分区联赛复赛试题
（初中组 竞赛用时：3小时）
题一：数的计数 (20分)
[问题描述]
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n≤1000)，然后对此自然数按照如下方法进行处理
l·不作任何处理:
z·茬它的左边加上一个自然数，但该自然数不能超过原数的一半;
3·加上数后，继续按此规则进行处理，直到不能再而 自然数为止。
[样例] 输入：6
满足条件的数为 6 (此部分不必输出)
6
26
126
36
136
输出：6
题二：最大公约数与最小公倍数问题 (20分)
[问题描述]
输入二个正整数x0,y0(2≤x0≤100000，2≤y0≤1000000)，求出满足下列条件的P、Q的个数。
条件:1.P、Q是正整数
二要求P、Q以xO为最大公约数，以yO为最小公倍数。
试求，满足条件的所有可能的两个正整数的个数。
[样例]
输入：x0=3 y0=60
输出：4
说明：(不用输出)此时的 P Q 分别为，
3 60
15 12
12 15
60 3
所以，满足条件的所有可能的两个正整数的个数共4种。
题三：求先序排列 (30分)
[问题描述]
给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。
[样例]
输入：BADC BDCA
输出：ABCD
题四：装箱问题 (30分)
[问题描述]
有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从m个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。
[样例]
输入：
24 一个整数，表示箱子容量
6 一个整数，表示有n个物品
8 接下来n行，分别表示这n个物品的各自体积。
3
12
7
9
7
输出：
0 一个整数，表示箱子剩余空间。 2001年全国青少年信息学（计算机）奥林匹克分区联赛复赛试题
（高中组 竞赛用时：3小时）
题一 一元三次方程求解（20分）问题描述
有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x)=0，若存在2个数x1和x2，且x1输入：1 -5 -4 20
输出：-2.00 2.00 5.00
题二 数的划分(20分)问题描述
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5; 1，5，1; 5，1，1;
问有多少种不同的分法。
输入：n，k (6输出：一个整数，即不同的分法。样例
输入： 7 3
输出：4 {四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;}
题三 统计单词个数(30分)问题描述
给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。
输入格式
去部输入数据放在文本文件input3.dat中，其格式如下：
第一行为一个正整数(0每组的第一行有二个正整数(p，k)
p表示字串的行数;
k表示分为k个部分。
接下来的p行，每行均有20个字符。
再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6)
接下来的s行，每行均有一个单词。
输出格式
结果输出至屏幕，每行一个整数，分别对应每组测试数据的相应结果。样例
输入：
1
1 3
thisisabookyouareaoh
4
is
a
ok
sab
输出： //说明：(不必输出)
7 // this/isabookyoua/reaoh
题四 Car的旅行路线(30分) 问题描述
又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。
图例
机场
高速铁路
飞机航线
注意：图中并没有
标出所有的铁路与航线。那么Car应如何安排到城市B的路线才能尽可能的节省花费呢 她发现这并不是一个简单的问题，于是她来向你请教。
任务
找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。
输入文件：键盘输入文件名
输 出：到屏幕(输出最小费用，小数点后保留1位。)
输入格式
第一行为一个正整数n(0<=n<=10)，表示有n组测试数据。
每组的第一行有四个正整数s，t，A，B。
S(0接下来有S行，其中第I行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，T I为第I个城市高速铁路单位里程的价格。
输出格式
共有n行，每行一个数据对应测试数据。 样例
输入
1
1 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
第七届全国青少年信息学（计算机）奥林匹克分区联赛普及组复赛题测试表
__________赛区 __________学校 __________班 邮编__________
第一题： 数的计数 共20分
序号 N 输出 分值 得分
1 1 1 4
2 10 14 4
3 50 786 4
4 100 9828 4
5 198 195830 4
第二题： 最大公约数与最小公倍数问题 共20分
序号 X0 Y0 输出 分值 得分
1 3 120 4 4
2 12 60 2 4
3 4 1024 2 4
4 12 4096 0 4
5 3 999 4 4
第三题： 求先序排列 共30分
序号 中序排列 后序排列 输出 分值 得分
1 BCA BCA ABC 6
2 DCBA DCBA ABCD 6
3 ACEB AEBC CABE 6
4 CBAFEGD CFGEADB BCDAEFG 6
5 DEABFCHG DEAFHGCB BAEDCFGH 6
第四题： 装箱问题 共30分
序号 输入 输出 分值 得分
1 见T41.IN 1 6
2 见T42.IN 19 6
3 见T43.IN 1 6
4 见T44.IN 1 6
5 见T45.IN 6 6
