程序设计比赛试题(编辑修改稿)

程序设计比赛试题(编辑修改稿)内容摘要：

、 1 2 3 4 1 2 3。 你任务是求出一个序列用上面的方法排序至少需要多少步。 【 要求 】 【 数据输入 】 输入文件有两行：第一行是一个整数 n，表示数列的长度。 第二行有 n个整数，表示待排序的数列，每个整数的绝对值不大于 32767。 【 数据输出 】 输出文件有一行是一个整数 s，表示完成排序所需的最少步数。 【 样例输入 】 4 3 2 1 4 【 样例输出 】 1 提 示： 只需要一步就可以完成排序： 3 2 1 4 1 2 3 4。 选址 Time limit: 10s Memory limit: 32768K Total Submit : 100 Accepted Submit : 13 【问题描述】 很久以前，在世界的某处有一个形状为凸多边形的小岛，岛上的居民们决定建一个祭坛，居民们认为祭坛的位置离岛的顶点处越远越好。 你的任务是求凸多边形内一点，使其与各顶点的距离中最短的距离最远，点在边上也可以。 这样的点可能有多个，你只需输出这些点与各顶 点的最短距离。 【 要求 】 【 数据输入 】 第一行是一个整数 N(3≤ N≤ 100)。 接下来 N 行按逆时针顺序给出每个顶点的坐标，每行包含 2 个实数，表示顶点的横坐标和纵坐标 (坐标绝对值小于 10000)。 【 数据输出 】 输出一个实数，表示凸多边形内一点与各顶点的距离中最短的距离的最大值。 【 样例输入 】 3 0 2 9 0 7 7 【 样例输出 】 过河 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 数列 Time limit: 1s Memory limit: 32768K Total Submit : 415 Accepted Submit : 226 【问题描述】 给定一个正整数 k(3≤ k≤ 15),把所有 k 的方幂及所有有限个互不相等的 k的方幂之和构成一个递增的序列，例如， 当 k=3 时，这个序列是： 1， 3， 4， 9， 10， 12， 13，„ （该序列实际上就是： 30， 31， 30+31， 32， 30+32， 31+32， 30+31+32，„） 请你求出这个序列的第 N 项的值（用 10 进制数表示）。 例如，对于 k=3， N=100，正确答案应该是 981。 【 要求 】 【 数据输入 】 输入包含多个测试数据。 每个测试数据只有 1 行，为 2 个正整数，用一个空格隔开： k N （ k、 N 的含义与上述的问题描述一致，且 3≤ k≤ 15， 10≤ N≤ 1000） 【 数据输出 】 对于每个测试数据输出一个正整数（在所有的测 试数据中，结果均不超过*109）。 【 样例输入 】 3 100 3 100 【 样例输出 】 981 981 2^k 进制数 Time limit: 1s Memory limit: 32768K Total Submit : 110 Accepted Submit : 28 【问题描述】 设 r 是个 2k 进制数，并满足以下条件： （ 1） r 至少是个 2 位的 2k 进制数。 （ 2）作为 2k 进制数，除最后一位外， r 的每一位严格小于它右边相邻的那一位。 （ 3）将 r 转换为 2 进制数 q 后 ，则 q 的总位数不超过 w。 在这里，正整数 k（ 1≤ k≤ 9）和 w（ kw≤ 30000）是事先给定的。 问：满足上述条件的不同的 r 共有多少个。 我们再从另一角度作些解释：设 S是长度为 w 的 01 字符串（即字符串 S 由 w 个“ 0”或“ 1”组成）， S 对应于上述条件（ 3）中的 q。 将 S从右起划分为若干个长度为 k 的段，每段对应一位 2k 进制的数，如果 S 至少可分成 2 段，则 S所对应的二进制数又可以转换为上述的 2k 进制数 r。 例：设 k=3， w=7。 则 r 是个八进制数（ 23=8）。 由于 w=7，长度为 7 的 01 字符串按 3位一段分，可 分为 3 段（即 1， 3， 3，左边第一段只有一个二进制位），则满足条件的八进制数有： 2 位数：高位为 1： 6个（即 12， 13， 14， 15， 16， 17），高位为 2： 5个，„，高位为6： 1 个（即 67）。 共 6+5+„ +1=21个。 3位数：高位只能是 1，第 2 位为 2： 5 个（即 123，124， 125， 126， 127），第 2 位为 3： 4。