2
02
2
年
徐州市中小学生程序设计大赛真题
1、
统计数字
题目描述
请计算在区间 n 到 m 的所有整数中,数字 x(0<=x<=9)共出现了多少次?
例如,数字 2,在 12 到 23 中 12、13、14、15、16、17、18、19、20、21、22、23,共出现了 6 次。
输入
输入一行,3 个整数 n、m 和 x,之间用一个空格分开,n<m
输出
输出一行,包含一个整数,表示 x 出现的次数
样例输入
8 15 2
样例输出
1
提示
n<=m<=1000000,0<=x<=9
2、
花坛游戏
题目描述
校园内有个圆形花坛,围绕花坛有 n个连续的格子,小刘 开始在第
1 个格子开始向前跳,第
i
次跳跃会越过 c
i
个格子落到一个新格子上。 (注意,花坛是圆形的,第 n 个格子与第 1个格子相连) 已知 小刘 一共跳了 m 次,问花坛的所有格子中有多少个格子没到达过。
输入
两行,第 1行有两个整数
n,m
.
第 2 行,用空格隔开的 m 个整数,第
i
个整数 c
i
表示跨过的格子数 2<=
n,m
<=1000,0<=c
i
<n
输出
一个整数,表示没有到达过格子总数。
样例输入
8 5
3 0 2 5 3
样例输出
3
提示
开始在第 1 个格子上 第 1 次跨 3 个格子,跳到第 5 个格子上。
第 2 次跨 0 个格子,跳到第 6 个格子上。
第 3 次跨 2 个格子,跳到第 1 个格子上。
第 4 次跨 5 个格子,跳到第 7 个格子上。
第 5 次跨 3 个格子,跳到第 3 个格子上。
其中第 2,4,8 格子没有到达过,共有 3 个。
3
、
两质整数
题目描述
“两质整数”指能表示成两个质数乘积的整数。
质数——又称为素数,一个大于 1 的自然数,除了 1 和本身外没有其它因子。
比如:15 就是“两质整数”,因为 15 可表示成 3 和 5 两个质数的乘积。
本题有 Q 组询问,每次询问 L,R 之间共有多少个“两质整数”。
输入
第一行,一个整数 Q.
后面 Q 行每行有两个用空格隔开的整数
Li,Ri
Li <= Ri ,表示询问区间
Li,Ri
中一共有多少个“两质整数”
输出
Q 行,每行一个整数,表示询问的答案。
样例输入
3
1 100
1 1000
1 10000
样例输出
34
299
2625
提示
4、
圆环染色
题目描述
有一个圆环,平均分成 n 份,标记为 1~ n 块。
用 m 种颜色对每块进行染色,要求相邻两块颜色不一样。
当 n = 3,m = 3 有六种合法的染色方案。
现将一个圆环分成 n 份,标号后用 m 种颜色对其染色,要求相邻两块颜色不一样,共有多少种不同的染色方案。
输入
读入整数n和m。(1<=n<=m<=1000)
输出
输出填色方案数。
样例输入
3 3
样例输出
6
5、
太空道路
题目描述
太空纪年 0 年,太空中建立了 n 个城市。
为也方便城市之间的联络,在一些城市之间修建了一些道路,保证任意两个城市之间都有可以通过这些道路连通。
但第
i
条道路连接两个城市 ai, bi,长度均为 1 光年,道路是双向的。
每条道路还有两时间参数ti1 , ti2,表示经过ti1年道路就要维修,维修时间为ti2年。
例如:有一条道路:3 5 3 4,表示这条道路连接城市 3 和城市5,这条路使用3年就要维修,维修时间为 4 年。
第一次维修从第 3 年年初开始,维修到第6 年底,第7 年年初可以使用。
某人在第 p 年年初在 1 号城市,想乘坐光速飞船到 n 号城市,需要花费的最短时间?注:光速飞船一年飞行距离为 1 光年,飞行过程中可以选择在某个城市停留k(整数)年。
狭义相对论:飞船光速行驶时,桥的时间尺度会变得非常快。。。
输入
第一行,两个用空格隔开的整数 n, m.
后面有 m 行,表示 m 条通路。
每行有四个参数, ai, bi, ti1 , ti2 最后一行,一个整数表示 p.
输出
一个整数,到达 n 城市最少需要多少年。
样例输入
4 4
1 2 2 1
2 3 3 2
3 4 4 1
1 4 1 4
11
样例输出
5
提示
n<=1000, m<=5000
t1+t2<=100
p<=10000000
2022年徐州市中小学生程序设计大赛真题,2022年江苏徐州市中小学生程序设计大赛真题