返回信息流前几天做一个公司的笔试题,第三道300分的题没做出来,笔试结束后也没有搜到相关题和题解,求大佬们帮忙看一下做一下指点[ema1]。
----------------------------------------------------------------------------------
题目如下:
1.题目描述:
六一儿童节,光明小学组织玩游戏。所有10000名同学排成一列,从排头的第一位同学开始每个人手中有一张牌,上面写着一个素数,第一位同学是2,第二位同学是3,第三位同学是5......以此类推。游戏开始,主持人随机报一个数M,接下来所有位置相邻的同学可以抱团,如果抱团的所有人手中的牌上的数字之和等于主持人所报的数,即游戏成功。
2.输入描述:
第一行一个正整数 n (n<10),表示用例个数
接下来 n 行每行一个正整数(M<10^9),表示主持人报的数。
3.输出描述
如果游戏有可能成功,输出yes否则输出no
4.示例
输入
2
26
666
输出
yes
no
说明
26=3+5+7+9+11,所以牌子分别是3、5、7、11的同学抱团,则游戏成功。
----------------------------------------------------------------------------------
下面附上了开头(Python3):
import sys
if __name__=="__main__":
# 读取第一行的n,表示用例个数
n = int(sys.stdin.readline().strip())
for i in range(n):
# 读取每一行的M,表示主持人报的数
M = int(sys.stdin.readline().strip())
----------------------------------------------------------------------------------
这是一条镜像帖。来源:北邮人论坛 / acm-icpc / #100932同步于 2022/11/14
该镜像源已超过 30 天没有更新,可能在源站已被删除。
ACM_ICPC机器人发帖
【算法题求助】笔试中遇到的一个算法题,求大佬指点
gomdori
2022/11/14镜像同步16 回复
订阅后,新回复会通过你的通知中心匿名送达。
9 条回复
bd
【 在 gomdori 的大作中提到: 】
: 前几天做一个公司的面试题,第三道300分的题没做出来,笔试结束后也没有搜到相关题和题解,求大佬们帮忙看一下做一下指点[ema1]。
: --------------------------------------------------------------------------------
: 题目如下:
: ............
【 在 gomdori 的大作中提到: 】
: 前几天做一个公司的面试题,第三道300分的题没做出来,笔试结束后也没有搜到相关题和题解,求大佬们帮忙看一下做一下指点。
```python
#coding=utf-8
import requests
r = requests.get('https://primes.utm.edu/lists/small/10000.txt')
primes = []
for line in r.text.split('\n'):
nums = line.split()
if len(nums) != 10:
continue
primes += map(int, nums)
assert len(primes) == 10000
T = int(raw_input())
for case_ in xrange(T):
n = int(raw_input())
l, r = 0, 0
tot = 0
while l < len(primes) and r < len(primes):
if tot < n:
tot += primes[r]
r += 1
elif tot > n:
tot -= primes[l]
l += 1
elif tot == n:
print 'yes'
break
else:
print 'no'
'''
^^^^^TEST^^^
2
26
666
----------
yes
no
$$$TEST$$$
'''
```