CCF-CSP 游戏

CCF-CSP 201712-2 游戏 题解

问题描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
试题编号:201712-2
试题名称:游戏
时间限制:1.0s
内存限制:256.0MB
问题描述
有n个小朋友围成一圈玩游戏,小朋友从1至n编号,2号小朋友坐在1号小朋友的顺时针方向,3号小朋友坐在2号小朋友的顺时针方向,……,1号小朋友坐在n号小朋友的顺时针方向。
游戏开始,从1号小朋友开始顺时针报数,接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数(即数的个位)为k,则该小朋友被淘汰出局,不再参加以后的报数。当游戏中只剩下一个小朋友时,该小朋友获胜。
例如,当n=5, k=2时:
1号小朋友报数1
2号小朋友报数2淘汰;
3号小朋友报数3
4号小朋友报数4淘汰;
5号小朋友报数5
1号小朋友报数6淘汰;
3号小朋友报数7
5号小朋友报数8淘汰;
3号小朋友获胜。
给定n和k,请问最后获胜的小朋友编号为多少?
输入格式
输入一行,包括两个整数n和k,意义如题目所述。
输出格式
输出一行,包含一个整数,表示获胜的小朋友编号。
样例输入
5 2
样例输出
3
样例输入
7 3
样例输出
4
数据规模和约定
对于所有评测用例,1 ≤ n ≤ 10001 ≤ k ≤ 9

题解1

  最容易想到的方法应该是用数组来标记是否已经出局。首先,初始化编号数组,然后开始报数,每次都检查是否已经出局,若已经出局则直接跳过,否则检查报数是否为k的倍数或其末位数(即数的个位)为k,如果是,则将该数组元素置为0,即标记为出局。一直报数,直到数组中非 0 元素只有1个才停止,最后输出这个非 0 元素的索引即为获胜小朋友的编号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n, k = map(int, input().split()) # 读取输入n, k
lst = list(range(1, n + 1)) # 编号列表
count = 0 # 报数计数
if k != 1:
while lst.count(0) != n - 1: # 一直报数,直到只剩下 1 个小朋友
for i in range(n):
if lst[i] == 0: # 该小朋友已出局,不再报数
continue
else:
count += 1 # 报数
s = str(count)
if count % k == 0 or int(s[len(s) - 1]) == k: # 报数为k的倍数或其末位数(即数的个位)为k
lst[i] = 0 # 标记为已出局
for i in range(1, n + 1):
if lst[i - 1] > 0: # 输出未出局的小朋友
print(i) # 输出结果
break
else: # 若 k 为1,则直接输出最后 1 个小朋友的编号
print(n)

题解2

  用队列模拟的方式来解题。首先,列表中存储 n 个小朋友的编号,每次取出第 1 个元素进行判断,如果报数不为k的倍数并且其末位数(即数的个位)也不为k,则又将其加入到列表的尾部,直到编号列表中没有元素都

1
2
3
4
5
6
7
8
9
10
11
n, k = map(int, input().split()) # 读取输入n, k
lst = list(range(1, n + 1)) # 编号列表
count, res = 1, 1
while lst:
res = lst[0] # 取出第1个元素
lst.remove(res) # 出队列,不能用pop(),因为pop是从列表尾部弹出元素
if not (count % k == 0 or count % 10 == k): # 报数不为k的倍数并且其末位数(即数的个位)也不为k
lst.append(res) # 入队列
count += 1 # 报数
print(res) # 输出结果

知识点补充

列表的增删操作
  • append 方法
1
2
3
4
>>> lst = [1, 2, 3]
>>> lst.append(4) # 在尾部增加元素
>>> lst
[1, 2, 3, 4]
  • insert 方法
1
2
3
>>> lst.insert(2, 5) # 在指定位置插入元素
>>> lst
[1, 2, 5, 3, 4]
  • extend 方法
1
2
3
>>> lst.extend([6, 7]) # 在列表末尾一次性追加另一个序列中的多个值
>>> lst
[1, 2, 5, 3, 4, 6, 7]
  • pop 方法
1
2
3
4
>>> lst.pop() # 移除列表尾部的元素
7
>>> lst
[1, 2, 5, 3, 4, 6]
  • remove 方法
1
2
3
>>> lst.remove(5) # 移除列表中的指定元素
>>> lst
[1, 2, 3, 4, 6]
  • clear 方法
1
2
3
>>> lst.clear() # 清空列表中的所有元素
>>> lst
[]
约瑟夫问题

  约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知 n 个人(以编号 1,2,3…n 分别表示)围坐在一张圆桌周围。从编号为 k 的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从 0~n-1,最后 [1] 结果+1即为原问题的解。

  本题的情景与约瑟夫问题类似,因此也可以利用约瑟夫环的递推公式来解题。约瑟夫环的标准数学(找规律)解法:

  • 将 k 固定,设解 ANS[n,k] = ans(n)
  • 具有 m 个数的 m 约瑟夫环中,删除一个数之后,相当于重新标号后的 m-1 约瑟夫环问题。
  • 设从 a(1) 开始的 m 约瑟夫环答案为 ans(m) = s ,在 m+1 约瑟夫环中,由于经历了重新标号,m 中的标号 a(i) 应该为 a((k+i)%(m+1)) ,所以答案下标也要从 s 移动到 (s+k)%(m+1)
  • 公式:ans(1) = 1, ans(m+1) = (ans(m)+k)%(m+1)

  只要知道公式,代码实现就十分简单了,如下:

1
2
3
4
5
6
n, k = map(int, input().split()) # 读取输入的 n 和 k
s = 0
for i in range(2, n + 1): # 公式计算
s = (s + k) % i
print(s + 1) # 输出结果

  由于题目中除了约瑟夫问题中要求的出局条件外,还要求报数的末位数(即数的个位)为k的也出局,所以上述代码只有部分测试样例能够通过,提交只能得30分。但是,约瑟夫问题确实值得了解与学习。

坚持原创技术分享,您的支持将鼓励我继续创作!