发布时间 : 星期五 文章acm编程比赛入门题目集更新完毕开始阅读468ab7859e3143323868936a
【样例输出】 4.893
过河
Time limit: 1s Memory limit: 32768K Total Submit : 518 Accepted Submit : 65
【问题描述】
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，??，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
【要求】
【数据输入】输入的第一行有一个正整数L（1 <= L <= 109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
【数据输出】输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。
【样例输入】 10 2 3 5 2 3 5 6 7
【样例输出】 2
数字游戏
Time limit: 1s Memory limit: 32768K Total Submit : 323 Accepted Submit : 89
【问题描述】
小W发明了一个游戏，他在黑板上写出了一行数字a1,a2,?.an，然后给你m个回合的机会，每回合你可以从中选择一个数擦去它，接着剩下来的每个数字ai都要递减一个值bi。如此
重复m个回合，所有你擦去的数字之和就是你所得到的分数。 小W和他的好朋友小Y玩了这个游戏，可是他发现，对于每个给出的an和bn序列，小Y的得分总是比他高，所以他就很不服气。于是他想让你帮他算算，对于每个an和bn序列，可以得到的最大得分是多少。这样他就知道有没有可能超过小Y的得分。
【要求】 【数据输入】
第一行，一个整数n（1<=n<=200），表示数字的个数。 第二行，一个整数m（1<=m<=n），表示回合数。
接下来一行有n个不超过10000的正整数，a1,a2?an，表示原始数字，最后一行有n个不超过500的正整数，b1,b2?.bn，表示每回合每个数字递减的值
【数据输出】一个整数，表示最大可能的得分
【样例输入】 3 3
10 20 30 4 5 6
【样例输出】 47
速配游戏
Time limit: 5s Memory limit: 32768K
Total Submit : 295 Accepted Submit : 209
【问题描述】
有这么一个速配电视节目。N位男士和N位女士要在摄像机前选出他们合适的伴侣。每位女士按照其对每位男士作为配偶的偏爱程度给每位男士排名次，每位男士也按照其对每位女士作为配偶的偏爱程度给每位女士排名次。这些名次不允许并列。然后每位男士将向心仪的对象求婚，经过\残酷\的竞争之后各自找到适合的伴侣。 最开始的时候每位男士都还没有被任何一位女士拒绝。求婚环节会经过很多轮进行，每一轮： (1) 每位男士向还没有拒绝过自己的女士中选出自己认为最理想的一个，并向她求婚
(2) 每位女士在所有这一轮中向她求婚的男士中选出自己认为最理想的一个，并不答应，也不拒绝。她把其余向她求婚的男士都婉言拒绝掉。经过了若干轮求婚之后，在某一轮，幸运的事情发生了：所有的女士都恰好有一个求婚者，所有的男士都找到一个心仪的对象。主持人将继续指出这个配对方式的神奇之处：没有任意的两个配对，比方说男士A和女士a配对,男士B和女士b配对，使得在A心目中b较a更理想，而且在b心目中A较B更理想（这样A和b就会\私奔\）。因此，主持人总结说，这个配对是非常合理的。（他知道，这种情况是一定会发生的。）
主持人在节目之前已经知道男士和女士之间的偏爱情况，他想预先知道最后的匹配结果是怎么样的，你能帮帮他吗？
【要求】 【数据输入】第一行包括一个数字N（1<=N<=1000）以下N*2行，每行有N个数字。第i+1行（1<=i<=N）表示编号为i的男士对女士们的排序（从最喜欢的到最不喜欢的）。第N+j+1行（1<=j<=N）表示编号为j的女士对男士们的排序（同样从最喜欢的到最不喜欢的）。
【数据输出】N行，每行包括一个数字。第i行的数字表示与编号为i的男士匹配的女士的编号。
【样例输入】 3 1 2 3 2 3 1 2 1 3 3 2 1 2 3 1 2 3 1
【样例输出】 3 2 1
3n+1数链问题
Time limit: 1s Memory limit: 32768K
Total Submit : 471 Accepted Submit : 325
【问题描述】
在计算机科学上，有很多类问题是无法解决的，我们称之为不可解决问题。然而，在很多情况我们并不知道哪一类问题可以解决，那一类问题不可解决。现在我们就有这样一个问题，问题如下：
1. 输入一个正整数n； 2. 把n显示出来； 3. 如果n=1则结束；
4. 如果n是奇数则n变为 ，否则n变为n/2； 5. 转入第2步。
例如对于输入的正整数22，应该有如下数列被显示出来：
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
我们推测：对于任意一个正整数，经过以上算法最终会推到1。尽管这个算法很简单，但我们仍然无法确定我们的推断是否正确。不过好在我们有计算机，我们验证了对于小于1,000,000的正整数都满足以上推断。对于给定的正整数n，我们把显示出来的数的个数定义
为n的链长，例如22的链长为16。
你的任务是编写一个程序，对于任意一对正整数i和j，给出i、j之间的最长链长，当然这个最长链长是由i、j之间的其中一个正整数产生的。我们这里的i、j之间即包括i也包括j。
【要求】
【数据输入】输入文件只有一行，即为正整数i和j，i和j之间以一个空格隔开。 0 < i ≤ j < 10,000。
【数据输出】文件只能有一行，即为i、j之间的最长链长。
【样例输入】 1 10
【样例输出】 20
数制转换
Time limit: 1s Memory limit: 32768K
Total Submit : 479 Accepted Submit : 190
【问题描述】
有一种数制的基数是3，权值可以取-1,0,1，并分别用符号-,0,1表示，如这种数制的101表示十进制数的10，即1*(3^2)+0*(3^1)+1*(3^0)=10，又如这种数制的-0 表示十进制数的-3，即-1*(3^1)+0*(3^0)=-3。编程要求把给定的有符号整数转换为新数制的数，该数的前面不能有多余的0，如10的新数制表示是101，则不要输出成0101。
【要求】
【数据输入】文件有一行或多行，每行有一个整数N (-2,147,483,647≤N≤2,147,483,647)，整数内不会有其他分隔符。
【数据输出】对输入文件的每一行输出一行，该行是输入行的整数的新数制表示，不能有多余空行，每行之前不能有前导空格。
【样例输入】 10 -3
【样例输出】 101 -0 数列