admin管理员组文章数量:1565828
2024年7月17日发(作者：)
程序设计比赛试题
分解素因子
Time Limit:1000MS Memory Limit:65536K
Total Submit:14 Accepted:11
【问题描述】
假设x是一个正整数，它的值不超过65535(即1 个程序，将x分解为若干个素数的乘积。 【要求】 【数据输入】输入的第一行含一个正整数k (1<=k<=10)，表示测试例的 个数，后面紧接着k行，每行对应一个测试例，包含一个正整数x。 【数据输出】每个测试例对应一行输出，输出x的素数乘积表示式，式中 的素数从小到大排列，两个素数之间用“*”表示乘法。 【样例输入】 2 11 9828 【样例输出】 11 2*2*3*3*3*7*13 100 / 117 程序设计比赛试题 有趣的数列 Time Limit:1000MS Memory Limit:65536K Total Submit:2 Accepted:1 【问题描述】 数列F(n)和G(n)是由下列三个条件所确定的两个自然数列： (1) F(1) = 1； (2) G(n) = n*a - 1 - F(n)，a是一个大于4的整数； (3) F(n+1)是与2n个数:F(1),F(2),...,F(n);G(1),G(2),...,G(n)不同的最小自然 数。 给定a和n,你能求出满足以上条件的数列F(n)和G(n)吗？ 【要求】 【数据输入】测试数据有多行，每行包含两个数a和n，其中：4 < a <= 1000, 1 <= n <= 1000000; 当a = n = 0时，输入结束，此行无须处理。 【数据输出】为简便起见，只须输出数列F(n)和G(n)的第n项f(n), g(n)； 输出数据有一行，分别包含两个数f(n)和g(n)。 【样例输入】 5 1 5 3 0 0 101 / 117 程序设计比赛试题 【样例输出】 1 3 4 10 102 / 117 程序设计比赛试题 洗牌问题 Time Limit:1s Memory limit:32M Accepted Submit:301 Total Submit:644 【问题描述】 设2n张牌分别标记为1, 2, ..., n, n+1, ..., 2n，初始时这2n张牌按其标号 从小到大排列。经一次洗牌后，原来的排列顺序变成n+1, 1, n+2, 2, ..., 2n, n。即前n张牌被放到偶数位置2, 4, ..., 2n，而后n张牌被放到奇数位置 1, 3, ..., 2n-1。可以证明对于任何一个自然数n，经过若干次洗牌后可恢 复初始状态。现在你的的任务是计算对于给定的n的值(n≤10^5)，最少 需要经过多少次洗牌可恢复到初始状态。 【数据输入】输入数据由多组数据组成。每组数据仅有一个整数，表示n 的值。 【数据输出】对于每组数据，输出仅一行包含一个整数，即最少洗牌次数。 【样例输入】 10 【样例输出】 6 103 / 117 程序设计比赛试题 DNA序列密码问题 Time Limit:6s Memory limit:32M Accepted Submit:7 Total Submit:22 【问题描述】 一些生物的复杂结构可以用其DNA序列来表示。而DNA序列又可以表 示为带有标记的核苷酸字符串。最近，福州大学信息学院生物信息学研究 小组的一项工作表明，大多数蛋白质序列可以从核苷酸数据库记录中推导 出来。研究小组的科学家们用密码学方法将DNA序列变换为2维Cray 码后发现，任一DNA的Cray码序列S具有如下性质： 序列S:(x1,y1),(x2,y2),...,(xn,yn)是一个有限序列； 序列S中各项(xi,yi)均落在一个网格边长为1的300*3000平面网格N的 网格点上； 序列S中各项最多分布在网格N的3行中。 科学家们发现，若将序列S的每一项都看作平面上一个点，从序列的任意 一点出发，连接序列中每个点恰好一次，又回到出发点的最短平面回路T 的长度与该序列表示的DNA密码密切相关。为了有效地破译DNA密码， 科学家们希望设计出一个高效的计算程序，能对给定DNA的Cray码序列 S，快速计算出其最短回路T的长度。 编程任务 对于给定的DNA的Cray码序列S，计算出其最短回路T的长度。 数据输入本题只有一组数据。 Cray码序列S依其在网格N中的位置分为 3行： 104 / 117 程序设计比赛试题 (a1,ya),(a2,ya),...,(a_na,ya); (b1,yb),(b2,yb),...,(b_nb,yb); (c1,yc),(c2,yc),...,(c_nc,yc); 其中，0<=ya 0<=na,nb,nc<=1300 分别是各行中的点数。各行中点依其横坐标从小到 大排列。 0<=a1 【要求】 【数据输入】 输入数据第1行中的3个整数为na，nb和nc； 第2行中的3个整数为ya，yb和yc； 接下来的na行中每行1个整数，依次为a1,a2,…,a_na； 再接下来的nb行中每行1个整数，依次为b1,b2,…,b_nb； 最后的nc行中每行1个整数，依次为c1,c2,…,c_nc。 【数据输出】程序运行结束时，输出所找到的序列S的最短回路T的长度 值，精确到小数点后2位。 【样例输入】 2 1 2 1 2 3 5 7 6 105 / 117 程序设计比赛试题 5 7 【样例输出】 8.83 106 / 117 程序设计比赛试题 DNA序列密码问题 Time Limit:6s Memory limit:32M Accepted Submit:7 Total Submit:22 【问题描述】 一些生物的复杂结构可以用其DNA序列来表示。而DNA序列又可以表 示为带有标记的核苷酸字符串。最近，福州大学信息学院生物信息学研究 小组的一项工作表明，大多数蛋白质序列可以从核苷酸数据库记录中推导 出来。研究小组的科学家们用密码学方法将DNA序列变换为2维Cray 码后发现，任一DNA的Cray码序列S具有如下性质： 序列S:(x1,y1),(x2,y2),...,(xn,yn)是一个有限序列； 序列S中各项(xi,yi)均落在一个网格边长为1的300*3000平面网格N的 网格点上； 序列S中各项最多分布在网格N的3行中。 科学家们发现，若将序列S的每一项都看作平面上一个点，从序列的任意 一点出发，连接序列中每个点恰好一次，又回到出发点的最短平面回路T 的长度与该序列表示的DNA密码密切相关。为了有效地破译DNA密码， 科学家们希望设计出一个高效的计算程序，能对给定DNA的Cray码序列 S，快速计算出其最短回路T的长度。 编程任务 对于给定的DNA的Cray码序列S，计算出其最短回路T的长度。 【要求】 107 / 117 程序设计比赛试题 【数据输入】本题只有一组数据。 Cray码序列S依其在网格N中的位置 分为3行： (a1,ya),(a2,ya),...,(a_na,ya); (b1,yb),(b2,yb),...,(b_nb,yb); (c1,yc),(c2,yc),...,(c_nc,yc); 其中，0<=ya 0<=na,nb,nc<=1300 分别是各行中的点数。各行中点依其横坐标从小到 大排列。 0<=a1 输入数据第1行中的3个整数为na，nb和nc； 第2行中的3个整数为ya，yb和yc； 接下来的na行中每行1个整数，依次为a1,a2,…,a_na； 再接下来的nb行中每行1个整数，依次为b1,b2,…,b_nb； 最后的nc行中每行1个整数，依次为c1,c2,…,c_nc。 【数据输出】程序运行结束时，输出所找到的序列S的最短回路T的长度 值，精确到小数点后2位。 【样例输入】 2 1 2 1 2 3 5 7 6 108 / 117 程序设计比赛试题 5 7 【样例输出】 8.83 109 / 117 程序设计比赛试题 麦森数 Time Limit:5s Memory limit:32M Accepted Submit:114 Total Submit:585 【问题描述】 麦森数在数论中有着非常重要的地位，应用极广。形如2 ^ p – 1并且为 质数的数字即为麦森数。可以证明当2^p-1 为一质数的时候，p为质数。 你的任务是对于给出的整数，判断他能不能表示成2^p-1的形式，且p 为质数。 【要求】 【数据输入】输入包含多组测试数据。每行一组数据，包含一个不超过 10^10000的整数。 【数据输出】 对于每组数据，如果该数字可以表示成2^p-1的形式，且p为质数，输 出 “It may be a Mason number.” 否则，输出“It must not be a Mason number.” 【样例输入】 3 4 15 【样例输出】 110 / 117 程序设计比赛试题 It may be a Mason number. It must not be a Mason number. It must not be a Mason number. 111 / 117 程序设计比赛试题 飞机加油问题 Time Limit:2s Memory limit:32M Accepted Submit:136 Total Submit:934 【问题描述】 F国际航空公司在世界范围有n个国际机场。第i 个国际机场到中心机场 的距离为di, i=1，…，n。从国际机场j 到国际机场i 的飞行费用为c(i,j) = s + (dj - di)2 ，s 为地面加油费用。从任何国际机场飞往中心机场的飞机 可以在任一国际机场加油后继续飞行。飞机加油问题要求确定从距中心机 场最远的国际机场飞到中心机场的最少费用。 【编程任务】 对于给定的n个国际机场到中心机场的距离d1,d2,...,dn ,以与地面加油费 用s，编程计算从距中心机场最远的国际机场飞到中心机场的最少费用。 【要求】 【数据输入】第一行有2 个整数n (n<=400,000)和s，表示有n个国际 机场（不包括中心机场），地面加油费用s。接下来的1行中每行有n个整 数d1,d2,...,dn，表示给定的 n个国际机场到中心机场的距离。 【数据输出】将编程计算出的最小费用输出。 【样例输入】 5 10 1 3 6 7 10 112 / 117 程序设计比赛试题 【样例输出】 64 113 / 117 程序设计比赛试题 ElGamal数字签名 Time Limit:5s Memory limit:32M Accepted Submit:6 Total Submit:77 【问题描述】 在实际生活和工作中，许多事物的处理需要当事人的签名。尤其在现代通 信中，签名更是起到了认证、核准、有效和负责等功效。数字签名是现代 密码学的一个重要组成部分，自从Diffie和Hellman于1976年首次提出 数字签名以来，数字签名就在学术界和计算机网络界得到了迅猛的发展。 著名的公钥算法，椭圆曲线体制，在数字签名中都有一定的应用。ElGamal 就是一种原理简单，应用广泛的数字签名方法，它的成功很大程度上取决 于求解离散对数问题的困难。ElGamal的密钥和参数的产生过程如下： 它 先选定一个足够大的素数P， 然后在比P小的正数中选取一个随机数g 和随机数x， 并且计算出y=gx(mod P) 。然后，{y,g,P}作为公钥，而x 则作为保密认证的私钥。如果你想获取他人的私人信息，那么，你就必须 在已知 {y,g,P} 的情况下计算出x(当然，如果要获得明文，还必须攻破或 获取签名时使用的Hash函数)。本题的任务并不复杂，它只需要你对于已 知的三元组{y,g,P}，设法计算出签名验证的时候用户使用的私钥。 【要求】 【数据输入】本题有多组输入数据，你必须处理到EOF为止 输入数据有三个整数: P, g, y (2 <= P < 231) 【数据输出】输出仅仅一个数字x ,使得0 114 / 117 程序设计比赛试题 如果你认为不存在这样的x那么请输出 ERROR。 如果存在多个可能的密钥，请输出最小的一个。 【样例输入】 7 5 3 5 1 4 【样例输出】 5 ERROR 115 / 117 程序设计比赛试题 缺失的数据 Time Limit:1s Memory limit:32M Accepted Submit:196 Total Submit:512 【问题描述】 网络传输中由于受到链路层的最大传输单元(Maximum Transmission Unit，MTU)的限制，在很多情况下需要对原始的数据报进行分片，使得 每一分片可以顺利的传输。F公司的网络设备根据MTU的限制将每个原 始的数据划分成n片，用1~n这n个数字对每个分片进行编号，在目的 主机上将这些分片重新组合成原始的数据。可是在测试中发现一个问题： 经常出现缺失一个数据分片的情况。公司希望在将分片重新组合前就能知 道缺失的数据分片编号。 【要求】 【数据输入】有多组输入数据，你必须处理到EOF为止。 每组输入数据第一行就一个整数n(2<=n<=105), 表示数据分成了n片。 第二行有n-1个以空格隔开的整数，表示目的主机收到的数据分片的编号， 由于网络传输的一些因素，数据分片到达的顺序是随机的。 【数据输出】输出缺失的数据片编号。 【样例输入】 5 5 3 2 1 116 / 117 程序设计比赛试题 【样例输出】 4 117 / 117
版权声明：本文标题：程序设计比赛试题 内容由热心网友自发贡献，该文观点仅代表作者本人，
转载请联系作者并注明出处：https://www.elefans.com/dongtai/1721220022a866603.html，
本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论