ACM程序设计与竞赛作业要点

程序设计与竞赛作业

1.采药

2.金字塔问题

3.毛毛虫问题

4.

5.字符串正反连接

6.去掉空格

7.成绩转换

8.金块问题

9.工资问题

10.“水仙花数”问题

11.大小写转换

12.取数游戏

13.整除问题

14.警察抓小偷

15!

16.汉诺塔问题

17.猴子吃桃问题(递归)

18.(I)

19.()

20.()

21.0

22,埃及分数

23.完数

24.2070

25.

26.不要622089

1问题B:采药

时间限制：1内存限制：128

提交:87解决:72

［提交］［状态］［讨论版］

题目描述

辰辰是个很有潜能、天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近

最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草

药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株

也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪

明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入

输入的第一行有两个整数T(1<T<1000)和M(1<M<100),T代表总共能够用来采药的时

间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间(包括1和100)

的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出

输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

样例输入

703

71100

691

12

样例输出

3

0

a(102][1002]={0};

1111;

("")；

(""11)；

(il=ll<l)处理第一行

{

(il>l)

a[k][il]l;

(2<)

{(""ID；

(

(il<tl)不可能采的情况；

a[k][il][l][il];

可以采的情况

(

a[k][il][l][il];采完总价值下降

值得采的情况;

)

)

,>

}

(""[m][t]);

)

心得：这是一个动态规划的题目，首先定义一个二维数组，根据草药的性价比，优先采取较

高的草药，如果时间不够，则降低性价比继续采取草药，直至时间结束，根据采集的草药计

算它的最大值，这题通过比较算出可能采的情况，和不能采的情况，如果能采，那再判断值

不值得采，得出最优解。

2问题A:金字塔问题

时间限制：1内存限制：128

提交:54解决:32

［提交］［状态］［讨论版］

题目描述

给一个金字塔，如上图所示，请你求出一个从塔顶到塔底的路径，要求路径经过的点的数字和最

小。

例如上图所示的金字塔的最小路径为：40

输入

输入第一行是一个整数n<1000;

接下来是n行，

第一行一个数；

第二行两个数；

OOO

第n行n个数；

数之间用空格分开。

数的链接方式如图所示。

输出

一个数，就是从塔顶到塔底的路径的最小距离O

样例输入

5

9

1215

1068

31895

19710416

样例输出

40

<>

0

(

a[100][100];定义一个二维数组；

("")；

(1<)

(1<)

(

(""[ilUD；

)

(1>=D

(1<)从最后一行开始处理；

(

(a[l][j]>a[l][l])

a[i]U][i]U][l][l]；

a[i][j][i]Ul[l]U]；求得每次路径最小值;

）

心得：这个题目主要运用了动态规划的思想，定义一个二维数组，把所输入的数据存入进

去，然后从它的第一行处理，比较相邻位置数的大小，取最小的路径和上一行对应的数相加,

取得最小路径，进行循环，直到求出数组中即所求的结果。

3问题B:毛毛虫问题

时间限制：1内存限制：128

提交:32解决：16

［提交］［状态］［讨论版］

题目描述

在她家门口水平种了一排苹果树，共有N棵。

突然发现在左起第P棵树上（从1开始计数）有一条毛毛虫。为了看到毛毛虫变蝴蝶的过程，在苹

果树旁观察了很久。虽然没有看到蝴蝶，但发现了一个规律：每过1分钟，毛毛虫会随机从一

棵树爬到相邻的一棵树上。

比如刚开始毛毛虫在第2棵树上，过1分钟后，毛毛虫可能会在第1棵树上或者第3棵树上。

如果刚开始时毛毛虫在第1棵树上，过1分钟以后，毛毛虫一定会在第2棵树上。

现在告诉你苹果树的数目N,以及毛毛刚开始所在的位置P,请问，在M分钟后，毛毛虫到达

第T棵树，一共有多少种行走方案数。

输入

输入四个整数NPMT。

输出

输出一个整数，就是行走的方案数。

样例输入

7444

样例输出

6

<>

0

a[100][100]={0}定义一个二维数组；

a[O][p]=1;毛毛虫刚开始在数组中的位置；

(1<)

(

(1<)

(

aMjHUUWHl]每一步的方案数；

I

)

("\nTm][t])分钟后到T棵树行走的方案数；

)

心得：这一题运用了动态规划的思想，毛毛虫的每一步都会影响下一步的结果，所以首先按

照普通情况找出规律及其其公式，进而算出方案数。首先定义一个二维数组，初始化毛毛虫

的起始位置，然后通过两个循环，求出毛毛虫走每一步的方案数，存在二维数组中，然后求

出第M分钟到T棵树行走的方案数。

4问题A:

时间限制：1内存限制：128

提交：61解决:23

[提交][状态][讨论版]

题目描述

p1,p2p3,'s(p1,p2,p3),1,...p1,p2p3.

,H(2,3,5)=2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,...

H5(2,3,5)=6.

输入

p1p2p3i.

输出

-(p1,p2,p3).10A18.

样例输入

2355

样例输出

(plp2p3)定义有参函数；

(

1；

(p2<)

2;

(p3<)

3；

}求pl23的最小值；

0

(

P123;

[10000];

(""123);

0;

[0]=1；

(1<)

{[i](pl*[a]2*[b]3*[c])调用函数;

([i]l*[a])

([i]2*[b])

([i]3*[c])

1求所有的能被pl23整除的数：

0;

心得：运用动态规划的思想，定义一个一维数组，把所有符合条件的数按顺序存进一维数组

中，这个编程运用了函数调用的方法求三个数的最小值，然后把这个最小值存进一维数组中，

每次存进一个数，下次都会用存进去的这个数求解下一个数，进行循环。

5问题B:字符串正反连接

时间限制：1内存限制：128

提交：68解决:42

［提交］［状态］［讨论版］

题目描述

所给字符串正序和反序连接，形成新串并输出

输入

任意字符串(长度<=50)

输出

字符串正序和反序连接所成的新字符串

样例输入

123

样例输出

123321

<>

<>

0

(

a［50］定义一个字符串；

((""))实现多行实例输入；

(

(a)把字符串的长度值赋给f;

(0<)

(

把字符串正序输出；

)

(1>=0)

(""［i］)把字符串反序输出;

}

)

心得：定义一个字符串，运用。函数获取字符串的长度值f.首先用循环，把这个字符串正

序输出，然后再用循环对这个字符串进行反序输出，这里主要考察了输入输出。

6问题C:去掉空格

时间限制：1内存限制：128

提交:27解决:4

［提交］［状态］［讨论版］

题目描述

读入一些字符串，将其中的空格去掉。

输入

输入为多行，每行为一个字符串，字符串只由字母、数字和空格组成，长度不超

过80。输入以“”结束。

输出

对于每行输入，输出转换后的字符串。

样例输入

123

样例输出

123

提示

用是不能读入一行有空格的字符串的，用吧。用“()”可以判断输入是否结束，如果此条件为

假(即0),则表示输入结束(对于本题)。

<>

<>

0

a[90]定义一个字符串；

((a))

(

(a)把字符串的长度值赚给f;

(0<)

{

(a[i]'')

(

(""[1])去掉空格;

1；

("”口])没有空格，直接输出；

)

("\n");

)

)

心得：这里也是主要考察输入输出问题，首先也是定义了一个字符串，用0函数获得字符串

的长度f,进行f次循环，判断这个字符串是否有空格？如果有把数组中的每个数往后进一

位，即去点空格，如果没有直接输出。

7问题D:成绩转换

时间限制：1内存限制：128

提交:78解决:30

［提交］［状态］［讨论版］

题目描述

输入一个百分制的成绩t,将其转换成对应的等级，具体转换规则如下：

90~100为A;

80-89为B;

70-79为C;

60-69为D;

0~59为E;

输入

输入数据有多组，每组占一行，由一个整数组成。

输出

对于每组输入数据，输出一行。如果输入数据不在0~100范围内，请输出一行:

“!，，

样例输入

56

67

100

123

样例输出

E

D

A

提示

<>

0

X；

((""))实现多行实例输入；

{

(x<60)

("E\n");

(x<70)

("D\n");

(x<80)

("C\n");

(x<90)

("B\n");

(x<=100)

("A\n");

("!\n");

}分数转换为等级；

0;

)

心得：这里主要运用了选择语句，用((""))语句实现多行实例输入，然后把所输入的分数通

过语句进行判断，转换成相应的等级，输出。

8问题A:金块问题

时间限制：1内存限制：128

提交：92解决:71

［提交］［状态］［讨论版］

题目描述

老板有一袋金块(共n块，n是2的幕(n>=2)),最优秀的雇员得到其中最重的一块，最差的雇员

得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金

块。

输入

输入共两行，

第一行输入金块的数量N<100000；

第二行N金块的重量，用空格间隔。

输出

两个数用空格分开，最重金块最轻金块

样例输入

5

37964

样例输出

93

<>

0

(

[100000];

((”"))实现多行实例输入；

(

(0<)

C'"[i])；

|0]把数组a[0]的值赋给和；

(1<)

(

(a[i]>)

['J；

｝求最最重的金块；

(1<)

｛

(a[i]<)

[i]；

｝求最轻的金块；

("\n");

)

0;

)

心得：这题主要运用分治算法的思想，把一个大问题分成一个个小的子问题去求解，这个题

目是典型的二分法问题，把这个题分成两个小问题，即求最重的和求最轻的金块，首先定义

了一个一维数组，把所有金块的质量存入其中，把数组的初始值赋给最重的和最轻的金块,

然后运用循环对数组中每个金块的质量与金块的初始值进行比较，求的最重和最轻的金块，

然后输出。

9问题B:工资问题

时间限制：1内存限制：128

提交：121解决：74

［提交］［状态］［讨论版］

题目描述

某单位给每个职工发工资（精确到元），为了保证不要临时兑换零钱，且取款的张数最少，取工

资前要统计出所有职工的工资所需各种币值（100,50,20,10,5,2,1元共7种）的张数,

请编程完成。

输入

输入一个工资数<10000元

输出

输出各个币种的张数，没有的用0代替，中间用空格分开

样例输入

173

样例输出

1110011

<>

0

“7］={100,50,20,10,5,2,1}把所有币值按从从大到小的顺序存到一位数组中;

s［7］={0}定义一个一位数组，元素值全为0；

""）；

（0<7）

（

U1；

s［jl；

*町；

｝求需要各个币值的个数；

(""［0］);

(1<7)

(""5)输出需要各个币值的个数；

0；

)

心得：这个题主要运用贪婪算法的方法，利用可行的策略，求出可行解的一个解元素

由所有解元素合成问题的一个可行解。要想取得的张数最少，可以先考虑币值最大的进行分

发，然后再取更小钞票的币值。依次取之。首先定义一个一维数组，把币值从大到小存进去,

运用一循环，把每次算的钱数的结果，依次对数组的币值进行取整。然后依次存入数组输出。

10问题C:“水仙花数”问题1

时间限制：1内存限制：128

提交：138解决：75

［提交］［状态］［讨论版］

题目描述

判断一个数是否为“水仙花数"，所谓"水仙花数”是指这样的一人数：其各位数字

的立方和等于该数本身。例如：371是一个"水仙花数"，371=3A3+7A3+1A3.

输入

一个三位数

输出

1或者0(1代表此数为水仙花数,0代表此数不是水仙花数)

样例输入

371

样例输出

1

<>

0

100求三位数的百位数字；

10求三位数的个位数字；

((x*100))/10求三位数的十位数字;

(*X**y**z*Z)

("”,0)判断这个三位数是否为水仙花数，是输出1,否输出2；

)

心得：首先，输入一个三位数，运用对这个数取整，取余，运用数学公式，分别算出它的百

位，十位，和个位的数字，然后判断这三个数字的平方和是否等于这个三位数，如果是，输

出1,如果不是输出0.

11问题E:大小写转换

时间限制：1000内存限制：65536

提交:182解决:116

［提交］［状态］［讨论版］

题目描述

读入一些字符串，将其中的小写字母转成大写字母(其他字符不变)。

输入

输入为多行，每行为一个字符串，字符串只由字母和数字组成，长度不超过80。

输入以“”结束。

输出

对于每行输入，输出转换后的字符串。

样例输入

2004

12345

样例输出

2004

12345

<>

<>

0

(

j；

[80]定义一个字符串；

((""))实现多行实例输入;

{

(0<80)

(

(([j]>=，a,)(U]<='z'))

U1UI-32;

)实现字母大小写转换；

心得：这个题目主要考察输入输出，还有大小写转换问题，首先还是定义一个字符串，用((”"))

语句实现多行实例输入，对这个字符串进行循环，如果这个字符串有大写的话，转化成小写

的，如果有小写的话，那么转化成大写的。

12问题B:取数游戏

时间限制：1内存限制：128

提交：46解决:39

［提交］［状态］［讨论版］

题目描述

有2个人轮流取2n个数中的n个数，所取数之和大者为胜，请

编写算法，让先取数者胜，模拟取数过程。

输入

输入两行，第一行一个整数N<100000；

第二行N个数，用空格分开。

输出

输出取胜人取数和。失败人取数的和，空格分开。

样例输入

6

123456

样例输出

129

<>

0

(

12(100000];

((""))实现多行实例输入；

(

12=0;

(0<)

(""[iD；

(0<2)

H[i]；

(1<2)

22[i]隔数取数求和12；

(1>2)

("\n"12);

("\n"21);

｝顺序输出取胜人取数和。失败人取数和；

0;

)

心得;这题主要运用贪心算法的思想，要想先取数人获胜，就得让这个人每一步都尽可能取

得最大的数，这样他取数的和才会总体大于后取数的那个人的取数和。首先定义一个一维数

组，把要取得数从小到大的顺序放在里面，然后一个人从第一个按照隔一个数取，求和1；

另一个人从第二个按照隔一个人取，求和2,比较1和2的最大值，输出。

13问题C:整除问题

时间限制：1内存限制：128

提交：70解决:44

［提交］［状态］［讨论版］

题目描述

编写算法对输入的一个整数，判断它能否被3,5,7整除，并输出以下信息之一:

能同时被3,5,7整除；

能被其中两个数(要指出哪两个)整除；

能被其中一个数(要指出那一个)整除；

不能被3,5,7任一个整除；

输入

输入一个整数<100000；

输出

如果都能整除输出""

如果都不能整除输出“"

如果能被3和5整除则输出“35”。中间有一个空格，

注意按由小到大输出。

样例输入

35

样例输出

57

<>

0

(

n;k;

("")；

((30)+(50)*2+(70)*4)判断整数是否能被2,3,5整除;

(k)

(

7("")；

6("57");

5("37");

4("4");

3("35");

2("5");

1("3");

0("");

｝用语句输出结果；

)

心得：这题主要考察输入输出问题，首先输入一个整数，运用语句((30)+(50)*2+(70)*4),判

断这个数能否被2,3,5整除，用语句输出所有可能发生的结果，然后输出题目中所要求输出

的结果，其中用语句起到了优化算法的作用。

14问题A警察抓小偷

时间限制：1内存限制：128

提交：115解决：88

［提交］［状态］［讨论版］

题目描述

警察局抓了,4名小偷嫌疑犯，其中只有一个人是小偷，审问中，a说：我不是小偷，b说：c是

小偷，c说：小偷肯定是d,d说：c在冤枉人。现在己经知道4个人中3人说的是真话，一人

说的是假话，问到底谁是小偷。

输入

输出

小偷是c

样例输入

样例输出

小偷是c

<>

0

(

X；

(1<=4)执行4次循环；

(((1)+(3)+(4)+(4))3)判断是否有三个人说真话的情况；

("",64);

)

心得：这个题目主要考察把文字信息转化为数字信息，即信息数字化，把A,B,C,D看

成1,2,3,4；x定义为小偷，然后把A,B,C,D四人所说的话变成数字语言，判断当

他们四个人有三个人说真话的情况，然后以把数字变成字母输出。

15问题B:n!

时间限制：1内存限制：128

提交：262解决:162

［提交］［状态］［讨论版］

题目描述

输入一个整数N,输出它的阶乘。

输入

输入一个整数<20;

输出

输出它的阶乘

样例输入

5

样例输出

120

提示

<>

0

(

(m)对函数进行声明；

(n)；

0;

(n)定义函数

(01)

(

1；

｝判断当n等于。和1这两种情况；

*(1)调用函数求值；

f；

)

心得：这里主要运用函数的递归调用，首先用对输入的数进行判断，看是否为1和0,如果

是，那么输出其阶乘等于1,如果不是那么调用函数*(1)进行求值，函数总共被调用了n次,

求得最后的结果，输出。

16汉诺塔问题

时间限制：1内存限制：128

提交:224解决：138

［提交］［状态］［讨论版］

题目描述

把N个盘子从A柱子借助B柱子移到C柱子，要求每次只能移动一个盘子，并且小盘

子不能放到大盘子上。问如何移动。

输入

输入盘子的个数N(<=10)

输出

输出移动的次数。

样例输入

3

样例输出

7

提示

<>

0

1;

(1)去除盘子的个数为1的情况;

(

(1<)

1求盘子移动的次数；

(

1;

0；

)

心得：这题主要考察循环与递归问题，先假设盘子的个数，取几个特殊值，找出移动盘子次

数的规律。这个编程首先判断盘子个数，如果是1,则输出1次，如果不是1,执行n次循

环，求得j,然后求出移动盘子的次数1,输出。

17问题D:猴子吃桃子问题(递归)

时间限制：1内存限制：128

提交:98解决:87

［提交］［状态］［讨论版］

题目描述

一只猴子摘了若干桃子，每天吃现有桃子的一半多一个，到第10天时就只有一个桃子

了，求原来有多少个桃。

输入

输出

输出原来的桃子数

样例输入

样例输出

提示

<>

0

(

1;

(9>0)执行9次循环；

(1)*2求每天桃子的个数；

("\n");

1；

)

心得：这个题目运用数学中倒推的方法求得，先求出第10天桃子的个数，然后再求出前一

天桃子的个数，直到求出第1天桃子的个数，找出其规律。设桃子的个数为x,则每天剩余

桃子的个数满足公式(1)*2,再用一个循环求出原来的桃子数。

18问题A:(I)

时间限制：1内存限制：128

提交:402解决：183

［提交］［状态］［讨论版］

题目描述

a+b.

9■!■■II•

9，

输入

aab,a,

输出

abab

样例输入

15

1020

样例输出

6

30

提示

<>

0

{

((""))实现多行实例输入；

(

求a和b的和；

心得：这个题主要考察了输入和输出问题，目的是计算整数a和b的和，首先用((”"))语句

实现多行实例输入，然后求出a和b的和，输出。

19()

时间限制：1内存限制：128

提交:310解决：179

［提交］［状态］［讨论版］

题目描述

a+b.

输入

N,Naab,a,

输出

abab,

样例输入

15

1020

样例输出

6

30

提示

［提交］［状态］［讨论版］

<>

0

(

()限制求和的次数；

{

("”)输入；

(”\n")求的和；

)

)

心得：这个题目主要考察了输入输出问题，题目要求第一行输入要输入要计算和的数量，用

()语句满足了题目的要求，即执行n次，然后就是输入a和b,接着求出和，输出。

20问题C:()

时间限制：1内存限制：128

提交:314解决:169

［提交］［状态］［讨论版］

题目描述

a+b.

输入

aab,.A00

输出

abab,

样例输入

15

1020

00

样例输出

6

30

<>

0

(

(("")!(00))/*实现多行实例输入，当都为0时结束*/

(

("\n")求的和；

}

)

心得：这个题目也是输入输出问题，目的也是求出a和1b的和，然后按要求输入输出，对于

输入：(("")!(00))运用这个语句实现多行实例输入，如果输入00,则结束，然后求得a和b

的和，输出。

21问题D:0

时间限制：1内存限制：128

提交:287解决：166

［提交］［状态］［讨论版］

题目描述

输入

aN,N.A0

输出

样例输入

4102340

5112855

0

样例输出

55

31

提示

<>

0

(

9

1;

(0)

{

(0);判断n是否为断0,是结束，不是执行下面语句；

0;

(0<)执行n次循环；

(

("")；

每次循环求和；

)

("\n");

}

)

心得：同样，这个题目也是主要考察了输入输出问题，计算一些整数的和，并按指定的格式

输出，首先输入一些整数判断是否都为0,如果是，则结束，如果不是则执行循环，把所有

输入的整数相加，然后输出。

22问题B:埃及分数

时间限制：1内存限制：128

提交:21解决：11

［提交］［状态］［讨论版］

题目描述

设计一个算法，把一个真分数表示为最少埃及分数之和的形式，所谓埃及分数，是

指分子为1的分数。

如7/8=1/2+1/3+1/24。

输入

输入两个整数，第一个表示分子，第二个数表示分母。

输出

输出埃及分数之和，按分母有小到大的顺序，中间用空格分开。

样例输入

78

样例输出

2324

提示

<>

0

(("”))实现多行实例输入：

(

(10)

("\n")如果这个数为1或分子为1,输出分母的值;

(1)

(

1；

*•

*c;

("")通过公式求出埃及分数。

(01)

(

("\n");

1；

)

)

)

0;

心得：首先通过语句实现多行实例输入，首先输入这是分数的的分子分母，判断这个数是否

为1或这个数的分子为1,如果是，直接输出分母的值；接下来用一循环，通过求公式依次

算出埃及数，然后输出，用每次计算的结果判断分子是否能整除分母或分子为一，如果是，

直接输出整除后结果。

23问题A:完数

时间限制：1内存限制：128

提交：192解决：70

［提交］［状态］［讨论版］

题目描述

完数的定义：如果一个大于1的正整数的所有因子之和等于它的本身，则称这个

数是完数，比如6,28都是完数：6=1+2+3；28=1+2+4+7+14o

本题的任务是判断两个正整数之间完数的个数。

输入

输入数据包含多行，第一行是一个正整数n,表示测试实例的个数，然后就是n

个测试实例，每个实例占一行，由两个正整数1和2组成,(1<12<10000)。

输出

对于每组测试数据，请输出1和2之间(包括1和2)存在的完数个数。

样例输入

2

25

57

样例输出

0

提示<>

0

12;

((""))实现多行实例输入；

(

(0<)执行n次循环；

(

("”12)输入两个整数；

0；

(1<2)执行21+1次循环;

(

0；

(1<)

(

(0)判断1和2之间的数是否能被k整除;

0

如果是完数，统计其个数；

)

("\n");

)

}

0;

)

心得：这个题主要考察了输入输出和循环问题，用语句实现多行输入，首先输入两个数，判

断这两个数之间的数(包括这两个数)是不是完数，如果是完数，则记录这两个数之间完数

的个数，然后输出。

24问题