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

2017年

试题中使用的生成数列 R 定义如下：整数 0 ≤ R1 < 201701 在输入中给出。对于

i > 1，

Ri = (Ri−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, R1，表示屋顶

的宽度和生成数列的首项。从左向右数第 i (1 ≤ i ≤ n)

个瓦片的高度 ai = Ri mod 10

输出 一个整数，表示暴雨后屋顶积水方格的总数

样例输入 10, 1

样例输出 23

数据规模 1 ≤ n ≤ 100

4 任务调度 (15 分)

乌龟因为动作太慢，有 n 个任务已经超过截止日期

了。乌龟处理第 i 个任务需要 ai 单位时间。从 0 时刻

开始，乌龟可以选择某项任务，完成它，然后再开始另

一项任务，如此往复直到所有任务都被完成。

由于已经超过截止日期，乌龟会为此受到一定的惩

罚，惩罚值等于所有任务完成时刻之和。例如，有 2 个

任务分别需要 10 和 20 单位时间完成。如果先完成任

务 1，惩罚值为 10 + 30 = 40；如果先完成任务 2，惩

罚值为 20 + 30 = 50。

乌龟希望你求出惩罚值最小的完成任务的顺序。

输入 两个整数 n, R1，表示任务的数量和生成数

列的首项。处理任务 i (1 ≤ i ≤ n) 的时间 ai = (Ri

mod 100) + 1。

输出 一个整数，表示完成所有任务的最小惩罚值

样例输入 10, 2

样例输出 1641

数据规模

1 ≤ n ≤ 1000

5 基因组分析 (20 分)

乌龟得到了他的基因组，一个只包含“ATCG”四

种字母的字符串。乌龟想起科学家说，基因组中很多片

段都多次重复出现，而且这种重复是很有意义的，于是

他想计算一下自己基因组里片段的重复情况。

给定一个基因组，其中一个长度为 k 的子串称为一

个“k-片段”。乌龟希望你计算出基因组中不同的 k-片

段数量。例如，基因组 “TACAC” 的 2-片段有 “TA”,

“AC”, “CA”, “AC”，其中不同的片段数量有 3 个。

输入 整数 n, k, R1，表示基因组的长度、片段的

长度和数列生成的首项。基因组第 i (1

≤ i

≤ n) 个字

符在 Ri mod 4 的值为 0, 1, 2, 3 时分别为

A, T, C, G

输出 一个整数，表示不同的 k-片段的数量

样例输入 20, 2, 37

样例输出 10

数据规模 30% 的数据满足 n ≤ 100; 100% 的数据

满足 1 ≤ n ≤ 105, 1 ≤ k ≤ 10

6 加强版密码锁 (20 分)

乌龟偶然获得了一个宝箱，宝箱上又有一把密码锁。

密码锁由 n 个拨盘组成，每个拨盘初始时有一个 0 到

99 之间的整数。向上拨使数字 x 变为 (x+ 1) mod 100，

向下拨使数字 x 变为 (x + 99) mod 100。

因为密码锁年久失修，拨盘拨动的次数越多越费力。

如果一个拨盘被拨动 k 次，需要花费 k2 单位时间。

密码锁只有在所有的拨盘上的数字形成一个从左到

右严格递增的数列时才会解开。乌龟再次请你帮忙，求

解解开密码锁的最少时间。

输入 两个整数 n, R1，表示拨盘的数量和数列生

成的首项。从左向右数第 i (1 ≤ i ≤ n) 个拨盘的初始

数字为 Ri mod 100

输出 一个整数，表示解开密码锁的最少时间

样例输入 10, 4

样例输出 3338

数据规模

30% 的数据满足 n ≤ 3，所有数据满足

1 ≤ n ≤ 100

代码： “梦想杯”2017年江苏省信息与未来小学生夏令营IT小能手PK之程序设计试题-C++文档类资源-CSDN文库