ACM编程比赛入门题目集(2)

连续邮资问题

【问题描述】

G国发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，使得可在1张信封上贴出从邮资1开始，增量为1的最大连续邮资区间。例如，当n=5和m=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。编程任务:对于给定的正整数m和n，计算出邮票面值的最佳设计。

【要求】

【数据输入】输入数据每一行给出2个正整数m和n的值（1<=n，m<=9），最后以0 0表示文件结束。

【数据输出】对于输以假定(ai, aj) = 1.

输出包含一个正整数，即为Andy家至少养猪的数目。

【样例输入】 3 3 1 5 1 7 2

【样例输出】 16

kitty猫的基因编码

【问题描述】

kitty 的基因编码如下定义：kitty的基因由一串长度2^k（k<=8)的01序列构成，为了方便研究，需要把,01序列转换为ABC编码。用T（s)来表示01序列s的ABC编码T(s)＝‘A'（当S全由'0'组成）T(s)＝‘B'（当s全由'1'组成）T(s)＝‘C'+T（s1)+T（s2)s1,s2为把s等分为2个长度相等的子串比如 T（'00')='A' T('00001111')='CAB'

【要求】

【数据输入】一行，长度为2^k，为kitty猫的01基因编码，有多个数据

【数据输出】一行，由ABC构成的ABC编码

【样例输出】 01001011

【样例输出】 CCCABACCBAB

取石子游戏

【问题描述】

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

【要求】

【数据输入】输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。

【数据输出】输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。

【样例输入】 2 1 8 4 4 7

【样例输出】 0 1 0

勇气的挑战

【问题描述】

给定n个点的坐标(x,y,z),且n<=50,从点1出发,怎么样才能走一条路径,访问每个点一次且仅一次,使走过的距离和最小?

【要求】

【数据输入】多组数据.第1行n,然后n行3个整数坐标

【数据输出】每组一行,代表最小权和

【样例输入】 3 0 0 0 1 1 0 1 -1 0

【样例输出】 3.4

统计同成绩学生人数

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1608 Accepted Submission(s): 877

【问题描述】

读入N名学生的成绩，将获得某一给定分数的学生人数输出。

【要求】

【数据输入】测试输入包含若干测试用例，每个测试用例的格式为 第1行：N

第2行：N名学生的成绩，相邻两数字用一个空格间隔。

第3行：给定分数

当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。

【数据输出】对每个测试用例，将获得给定分数的学生人数输出。

【样例输出】 3 80 60 90 60 2 85 66 0

5

60 75 90 55 75 75 0

【样例输出】 1 0 2