“梦想杯”2017 年江苏省信息与未来小学生夏令营 IT 小能手 PK 之程序设计试题

江苏省信息与未来小学生夏令营 IT 小能手 PK 之程序设计试题"/>

“梦想杯”2017 年江苏省信息与未来小学生夏令营 IT 小能手 PK 之程序设计试题

2017年

试题中使用的生成数列 R 定义如下：整数 0 ≤ R 1 < 201701 在输入中给出。对于 i > 1 ， R i = ( R i − 1 × 6807 + 2831) mod 201701 。 1 龟兔赛跑 (15 分 ) 兔子又来找乌龟赛跑啦！同样的错误兔子不会犯两 次，所以兔子提出赛跑的时候，乌龟就觉得这场比赛很 不公平。于是兔子进一步放宽了条件，表示他可以在比 赛开始以后先睡 t 分钟再开始追乌龟。 乌龟这下没办法确定比赛到底公平不公平了，所以 请你来帮忙。假设乌龟每分钟可以跑 x 米，兔子每分 钟跑 y 米 ( x < y ) 。他希望你计算最大的整数赛跑距离 ( 米 ) ，满足乌龟能在兔子先睡 t 分钟的前提下，比兔子 更早或同时到达终点。 输入 三个整数 x , y , t 输出 一个整数，表示要求的最长赛跑距离 样例输入 11, 21, 7 样例输出 161 数据规模 1 ≤ x < y ≤ 100 , t ≤ 1000 2 密码锁 (15 分 ) 乌龟给自己的贵重物品上 了密码锁。密码锁上有 5 个数 字拨盘。每个数字拨盘每次向 上拨使数字增加 1 (9 向上拨得 到 0) ，向下拨使数字减少 1 (0 向下拨得到 9) 。 拨盘上的数字组成一个 5 位数。只要拨盘上的数字变为素数，密码锁就会被解 开。素数 ( 又称质数 ) 是只能被 1 和它自身整除的大于 1 的自然数。因为乌龟动作实在太慢，他希望你帮他计 算如何开锁，使得拨动的总次数最少。 输入 一个 5 位数，表示拨盘的初始数字 输出 一个 5 位素数，表示开启密码锁使用的素数 ( 拨动次数最少 ) 。如有多组解，输出满足条件的最大数 样例输入 01210 样例输出 01319

 

3 房屋积水 (15 分 ) 乌龟家的屋顶是凹凸不平的，所以每次雨后都会积 水。为了知道屋顶是否会在暴雨后塌掉，他把屋顶的形 状给了你，希望你帮他计算暴雨后屋顶的积水总量。 乌龟的屋顶由顺次排在同一水平线上的 n 个宽度 为 1 、高度为整数 ( 分别给出 ) 的瓦片组成。例如给定 n = 5 ，瓦片的高度分别为 4, 2, 3, 5, 1 ，屋顶可以画在 下图所示的网格中，灰色格子为瓦片。 暴雨过后，如果一个方格向左右两 侧延伸都能到达瓦片占据的方格，它就 会积水。所以图中波浪线格子在暴雨后 会积水，屋顶的积水方格总数为 3 。 输入 两个整数 n , R 1 ，表示屋顶 的宽度和生成数列的首项。从左向右数第 i ( 1 ≤ i ≤ n ) 个瓦片的高度 a i = R i mod 10 输出 一个整数，表示暴雨后屋顶积水方格的总数 样例输入 10, 1 样例输出 23 数据规模 1 ≤ n ≤ 100 4 任务调度 (15 分 ) 乌龟因为动作太慢，有 n 个任务已经超过截止日期 了。乌龟处理第 i 个任务需要 a i 单位时间。从 0 时刻 开始，乌龟可以选择某项任务，完成它，然后再开始另 一项任务，如此往复直到所有任务都被完成。 由于已经超过截止日期，乌龟会为此受到一定的惩 罚，惩罚值等于所有任务完成时刻之和。例如，有 2 个 任务分别需要 10 和 20 单位时间完成。如果先完成任 务 1 ，惩罚值为 10 + 30 = 40 ；如果先完成任务 2 ，惩 罚值为 20 + 30 = 50 。 乌龟希望你求出惩罚值最小的完成任务的顺序。 输入 两个整数 n , R 1 ，表示任务的数量和生成数 列的首项。处理任务 i ( 1 ≤ i ≤ n ) 的时间 a i = ( R i mod 100) + 1 。 输出 一个整数，表示完成所有任务的最小惩罚值 样例输入 10, 2 样例输出 1641 数据规模 1 ≤ n ≤ 1000 5 基因组分析 (20 分 ) 乌龟得到了他的基因组，一个只包含“ ATCG ”四 种字母的字符串。乌龟想起科学家说，基因组中很多片 段都多次重复出现，而且这种重复是很有意义的，于是 他想计算一下自己基因组里片段的重复情况。 给定一个基因组，其中一个长度为 k 的子串称为一 个“ k - 片段”。乌龟希望你计算出基因组中不同的 k - 片 段数量。例如，基因组 “TACAC” 的 2 - 片段有 “TA”, “AC”, “CA”, “AC” ，其中不同的片段数量有 3 个。 输入 整数 n , k , R 1 ，表示基因组的长度、片段的 长度和数列生成的首项。基因组第 i ( 1 ≤ i ≤ n ) 个字 符在 R i mod 4 的值为 0, 1, 2, 3 时分别为 A, T, C, G 输出 一个整数，表示不同的 k - 片段的数量 样例输入 20, 2, 37 样例输出 10 数据规模 30% 的数据满足 n ≤ 100 ; 100% 的数据 满足 1 ≤ n ≤ 10 5 , 1 ≤ k ≤ 10 6 加强版密码锁 (20 分 ) 乌龟偶然获得了一个宝箱，宝箱上又有一把密码锁。 密码锁由 n 个拨盘组成，每个拨盘初始时有一个 0 到 99 之间的整数。向上拨使数字 x 变为 ( x + 1) mod 100 ， 向下拨使数字 x 变为 ( x + 99) mod 100 。 因为密码锁年久失修，拨盘拨动的次数越多越费力。 如果一个拨盘被拨动 k 次，需要花费 k 2 单位时间。 密码锁只有在所有的拨盘上的数字形成一个从左到 右严格递增的数列时才会解开。乌龟再次请你帮忙，求 解解开密码锁的最少时间。 输 入 两个整数 n , R 1 ，表示拨盘的数量和数列生 成的首项。从左向右数第 i ( 1 ≤ i ≤ n ) 个拨盘的初始 数字为 R i mod 100 输出 一个整数，表示解开密码锁的最少时间 样例输入 10, 4 样例输出 3338 数据规模 30 % 的数据满足 n ≤ 3 ，所有数据满足 1 ≤ n ≤ 100 代码： “梦想杯”2017年江苏省信息与未来小学生夏令营IT小能手PK之程序设计试题-C++文档类资源-CSDN文库