GESP-Python五级 题库
平均分配
题目描述
小 A 有2n 件物品,小 B 和小 C 想从小 A 手上买走这些物品。对于第 i件物品,小 B 会以bi 的价格购买,而小 C 会以 ci的价格购买。为了平均分配这 2n件物品,小 A 决定小 B 和小 C 各自只能买走恰好n 件物品。你能帮小 A 求出他卖出这 2n件物品所能获得的最大收入吗?
输入格式
第一行,一个正整数n 。
第二行, 2n个整数b1,b2,...,b2n 。
第三行,2n 个整数 c1,c2,...,c2n。
输出格式
一行,一个整数,表示答案。
输入样例 1
3
1 3 5 6 8 10
2 4 6 7 9 11
输出样例 1
36
输入样例 2
2
6 7 9 9
1 2 10 12
输出样例 2
35
数据范围
对于20 % 的测试点,保证1 ≤n≤8。
对于另外20 % 的测试点,保证 0≤bi≤1,0≤ci≤1 。
对于所有测试点,保证 1 ≤n≤105,0≤bi≤109,0 ≤ci≤109 。
n = int(input()) b = list(map(int, input().split())) c = list(map(int, input().split())) d = [c[i] - b[i] for i in range(2 * n)] print(sum(b) + sum(sorted(d)[n:]))
原根判断
题目描述
小 A 知道,对于质数p 而言,p 的原根g 是满足以下条件的正整数:
·1<g<p
·gp-1 mod p=1
·对于任意1≤i<p-1 均有 gi mod p≠1。
其中a mod p 表示a 除以 p的余数。
小 A 现在有一个整数a ,请你帮他判断 a是不是p 的原根。
输入格式
第一行,一个正整数 T,表示测试数据组数。
每组测试数据包含一行,两个正整数a ,p 。
输出格式
对于每组测试数据,输出一行,如果 a是 p的原根则输出 Yes ,否则输出 No 。
输入样例
输出样例
数据范围
对于 40% 的测试点,保证3≤p≤103 。
对于所有测试点,保证1≤T≤20 ,3≤p≤109,1<a<p ,p为质数。
def fpw(b, e, p):
if e == 0:
return 1
r = fpw(b, e >> 1, p)
return r * r * (b if e & 1 else 1) % p
def solve():
a, p = map(int, input().split())
phi, v = p - 1, p - 1
for i in range(2, int(phi ** 0.5) + 2):
if v % i == 0:
while v % i == 0:
v //= i
if fpw(a, phi // i, p) == 1:
print("No")
return
if v > 1:
if fpw(a, phi // v, p) == 1:
print("No")
return
print("Yes")
[solve() for _ in range(int(input()))]奇妙数字
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨认为一个数字 x 是奇妙数字当且仅当x=pa,其中 p 为任意质数且 a 为正整数。例如,8=23,所以 8 是奇妙数字,而 6 不是。
对于一个正整数 n ,小杨想要构建一个包含 m 个奇妙数字的集合x1,x2,...,xm,使其满足以下条件:
集合中不包含相同的数字。
x1∗x2∗...∗xm是 n的因子(即x1,x2,...,xm这 m 个数字的乘积是 n 的因子)。
小杨希望集合包含的奇妙数字尽可能多,请你帮他计算出满足条件的集合最多包含多少个奇妙数字。
输入格式
第一行包含一个正整数 n ,含义如题面所示。
输出格式
输出一个正整数,代表满足条件的集合最多包含的奇妙数字个数。
输入样例
128
输出样例
3
样例解释
关于本样例,符合题意的一个包含 3 个奇妙数字的集合是 2,4,8。首先,因为2=21,4=22,8=23,所以 2,4,8 均为奇妙数字。同时,2\*\*48=64 是 128 的因子。
由于无法找到符合题意且同时包含 4 个奇妙数字的集合,因此本样例的答案为 3。

对于全部数据,保证有2≤n≤1012。
def calc(x): ans = 0 tmp = 1 while x >= tmp: ans += 1 x -= tmp tmp += 1 return ans n = int(input()) ans = 0 i = 2 while i * i <= n: if n % i == 0: cnt = 0 while n % i == 0: cnt += 1 n //= i ans += calc(cnt) i += 1 if n != 1: ans += calc(1) print(ans)
武器强化
时间限制:2.0 s
内存限制:512.0 MB
题面描述
小杨有 n 种武器和 m 种强化材料。第 i 种强化材料会适配第pi种武器,小杨可以花费ci金币将该材料对应的适配武器修改为任意武器。
小杨最喜欢第 1 种武器,因此他希望适配该武器的强化材料种类数严格大于其他的武器,请你帮小杨计算为了满足该条件最少需要花费多少金币。
输入格式
第一行包含两个正整数n,m,含义如题面所示。
之后 m 行,每行包含两个正整数pi,ci,代表第 i 种强化材料的适配武器和修改花费。
输出格式
输出一个整数,代表能够使适配第 1 种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。
输入样例
输出样例
样例解释
花费 1,将第三种强化材料的适配武器由 3 改为 1。此时,武器 1 有 2 种强化材料适配,武器 2 和武器 3 都各有 1 种强化材料适配。满足适配第 1 种武器的强化材料种类数严格大于其他的武器。

对于全部数据,保证有1≤n,m≤1000,1≤pi≤n,1≤ci≤109。
def calc(aim, n, cnt, cs): cur_cnt = cnt[0] res = 0 tmp = [] for i in range(1, n): buy = max(len(cs[i]) - aim + 1, 0) for j in range(buy): res += cs[i][j] cur_cnt += buy for j in range(buy, len(cs[i])): tmp.append(cs[i][j]) tmp.sort() for i in range(aim - cur_cnt): res += tmp[i] return res n, m = map(int, input().split()) cnt = [0] * n cs = [[] for _ in range(n)] for _ in range(m): p, c = map(int, input().split()) cnt[p - 1] += 1 cs[p - 1].append(c) for i in range(n): cs[i].sort() ans = 1000000000000000000 for i in range(max(cnt[0], 1), m + 1): ans = min(ans, calc(i, n, cnt, cs)) print(ans)
小杨的武器
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有n种不同的武器,他对第i种武器的初始熟练度为c。
小杨会依次参加m场战斗,每场战斗小杨只能且必须选择一种武器使用,假设小杨使用了第i种武器参加了第j场战斗,战斗前该武器的熟练度为ci′,则战斗后小杨对该武器的熟练度会变为ci′+a。需要注意的是,aj可能是正数,0或负数,这意味着小杨参加战斗后对武器的熟练度可能会提高,也可能会不变,还有可能降低。
小杨想请你编写程序帮他计算出如何选择武器才能使得m场战斗后,自己对n种武器的熟练度的最大值尽可能大。
输入格式
第一行包含两个正整数n,m,含义如题面所示。
第二行包含n个正整数c1,c2,...,cn,代表小杨对武器的初始熟练度。
第三行包含m个正整数a1,a2,...,am,代表每场战斗后武器熟练度的变化值。
输出格式
输出一个整数,代表m场战斗后小杨对n种武器的熟练度的最大值最大是多少。
输入样例
输出样例
一种最优的选择方案为,第一场战斗小杨选择第一种武器,第二场战斗小杨选择第二种武器。

对于全部数据,保证有1≤n,m≤105,−104≤ci,ai≤104。
N = 100010 a = [0] * N c = [0] * N n, m = map(int, input().split()) mx = -10000 s = input().split() for i in range(1, n + 1): c[i] = int(s[i-1]) mx = max(mx, c[i]) s = input().split() for i in range(1, m + 1): a[i] = int(s[i-1]) for i in range(1, m + 1): if n == 1 or a[i] > 0: mx += a[i] print(mx)
我们想让武器熟练度最大值尽可能大,所以我们可以贪心考虑把原本的最大值,加上所有的正的熟练度,这样他就会变得最大。
流程:读入n和m,然后读入一个字符串,这个字符串就是c的信息,我们转成int类型,并找出其中的最大值mx,然后再读入一个字符串,这个字符串就是a的信息,我们把这个字符串转成int类型,判断a数组,如果当前熟练度增加值为正数,则累加到最大值mx上。
特别的,如果n==1,也就是只有一个武器,所以每次只能用这一个,这种情况下即使是负数,也要累加上。
挑战怪物
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨正在和一个怪物战斗,怪物的血量为h,只有当怪物的血量恰好为 0 时小杨才能够成功击败怪物。
小杨有两种攻击怪物的方式:
·物理攻击。假设当前为小杨第i次使用物理攻击,则会对怪物造成2i−1点伤害。
·魔法攻击。小杨选择任意一个质数x(x不能超过怪物当前血量),对怪物造成x点伤害。由于小杨并不擅长魔法,他只能使用至多一次魔法攻击。
小杨想知道自己能否击败怪物,如果能,小杨想知道自己最少需要多少次攻击。
输入格式
第一行包含一个正整数t,代表测试用例组数。
接下来是t组测试用例。对于每组测试用例,第一行包含一个正整数h,代表怪物血量。
输出格式
对于每组测试用例,如果小杨能够击败怪物,输出一个整数,代表小杨需要的最少攻击次数,如果不能击败怪物,输出 -1。
输入样例
输出样例
对于第一组测试用例,一种可能的最优方案为,小杨先对怪物使用魔法攻击,选择质数 5 造成 5 点伤害,之后对怪物使用第 1 次物理攻击,造成21−1=1 点伤害,怪物血量恰好为 0,小杨成功击败怪物。

对于全部数据,保证有1≤t≤10,1≤h≤105。
prime = [] is_prime = [False] * 100010 def Eratosthenes(n): is_prime[0] = is_prime[1] = False for i in range(2, n + 1): is_prime[i] = True for i in range(2, n + 1): if is_prime[i]: prime.append(i) if i * i > n: continue for j in range(i * i, n + 1, i): is_prime[j] = False Eratosthenes(100000) t = int(input()) for _ in range(t): tmp = 1 x = int(input()) ans = 0 while True: if is_prime[x]: ans += 1 break x -= tmp ans += 1 if x <= 0: if x < 0: ans = -1 break tmp *= 2 print(ans)
考虑到物理攻击一定是1,2,4,……2i−1,这样枚举的,所以魔法攻击放到什么位置其实没有影响。
所以我们考虑如果当前x是质数,直接减质数结束即可,如果不是质数的话,就使用物理攻击即可。
流程:先用质数筛求质数,然后输入t,输入x,我们需要维护当前的物理攻击的值tmp,也就是1 2 4 ……,如果当前的x是质数,则直接结束,如果不是质数,则x-=tmp。
然后进行判断,如果x==0,则结束输出答案,如果x<0,则是没有答案的情况,输出-1
黑白格
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一个n行m列的网格图,其中每个格子要么是白色,要么是黑色。
小杨想知道至少包含k个黑色格子的最小子矩形包含了多少个格子。
输入格式
第一行包含三个正整数n,m,k,含义如题面所示。
之后n行,每行一个长度为m的01串,代表网格图第i行格子的颜色,如果为0,则对应格子为白色,否则为黑色。
输出格式
输出一个整数,代表至少包含k个黑色格子的最小子矩形包含格子的数量,如果不存在则输出0。
输入样例
输出样例
样例解释
对于样例1,假设 (i,j) 代表第i行第j列,至少包含5个黑色格子的最小子矩形的四个顶点为 (2,4),(2,5),(4,4),(4,5),共包含6个格子。
数据范围

对于全部数据,保证有 1 ≤ n , m ≤ 100 , 1 ≤ k ≤ n × m
N = 110 w = [[0] * N for _ in range(N)] sum_w = [[0] * N for _ in range(N)] def main(): n, m, k = map(int, input().split()) for i in range(1, n+1): s = input() for j in range(1, m+1): w[i][j] = int(s[j-1]) sum_w[i][j] = sum_w[i][j-1] + w[i][j] ans = 0 for i in range(1, m+1): for j in range(i, m+1): num = [] now = 0 for l in range(1, n+1): tmp = sum_w[l][j] - sum_w[l][i-1] now += tmp num.append(now) if now >= k: if ans == 0: ans = (j-i+1) * l else: ans = min(ans, (j-i+1) * l) L, R = 1, l while L < R: mid = (L + R + 1) // 2 if now - num[mid-1] >= k: L = mid else: R = mid - 1 if now - num[L-1] >= k: if ans == 0: ans = (j-i+1) * (l-L) else: ans = min(ans, (j-i+1) * (l-L)) print(ans) if __name__ == "__main__": main()
1.二维数组存储对应格子颜色的值
2.使用前缀和的技巧来快速计算任意子矩形内的格子数量。这样一来,不需要重复遍历每个可能的子矩形来计算其中的黑色格子数,从而节省时间
3.通过检查每个可能的子矩形,计算其中的黑色格子数量。找到一个最小的子矩形,使得其中至少有k个黑色格子。
4.使用二分查找的技巧,在内部循环中快速定位满足条件的子矩形大小
5.最后,我们输出这个最小子矩形的面积。如果不存在满足条件的子矩形,则输出0
小杨的幸运数字
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨认为他的幸运数字应该恰好有两种不同的质因子,例如,12=2×2×3 的质因子有2,3,恰好为两种不同的质因子,因此12是幸运数字,而30=2×3×5 的质因子有2,3,5,不符合要求,不为幸运数字。
小杨现在有n个正整数,他想知道每个正整数是否是他的幸运数字。
输入格式
第一行包含一个正整数n,代表正整数个数。
之后n行,每行一个正整数。
输出格式
输出n行,对于每个正整数,如果是幸运数字,输出1,否则输出0。
输入样例
输出样例
样例解释
7的质因子有7,只有一种。
12的质因子有2,3 ,恰好有两种。
30的质因子有2,3,5,有三种。
数据范围

对于全部数据,保证有1≤n≤104,每个正整数ai满足 2≤ai≤106。
N = 10**5 + 10
a = [0] * N
def calc(x):
i = 2
mp = {}
while i * i <= x:
if x % i == 0:
mp[i]=1
while x % i == 0:
x //= i
i += 1
if x != 1:
mp[x]=1
return int(len(mp.items()))
def main():
n = int(input())
for i in range(1, n + 1):
a[i] = int(input())
x = calc(a[i])
if x == 2:
print("1")
else:
print("0")
if __name__ == "__main__":
main()1.计算输入数据的质因子的个数。具体实现中,可以从最小的质数开始试除,统计不重复的质因子个数。
2.当质因子个数为2时,返回1表示是幸运数字,否则返回0。
成绩排序
问题描述
有N名同学,每名同学有语文、数学、英语三科成绩。你需要按如下规则对所有同学的成绩从高到低排序:
1. 比较总分,高者靠前;
2. 如果总分相同,则比较语文和数学两科总分,高者靠前;
3. 如果仍相同,则比较语文和数学两科的最高分,高者靠前;
4. 如果仍相同,则二人并列。
你需要输出每位同学的排名,如遇x人并列,则他们排名相同,并留空后面的x-1个名次。例如,有3名同学并列第1,则后一名同学自动成为第4名。
输入描述
第一行一个整数N,表示同学的人数。
接下来N行,每行三个非负整数ci,mi,ei分别表示该名同学的语文、数学、英语成绩。
保证0≤ci,mi,ei≤150。
输出描述
输出N行,按输入同学的顺序,输出他们的排名。
注意:请不要按排名输出同学的序号,而是按同学的顺序输出他们各自的排名
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入
样例输出
数据规模
对于30的测试点,保证N≤100,且所有同学的总分各不相同。
对于所有测试点,保证2≤N≤104。
N = int(input()) students = [] for i in range(N): c, m, e = list(map(int, input().split())) students.append((c + m + e, c + m, max(c, m), i)) students.sort(reverse = True) rank = [None for i in range(N)] last_student = None for i, student in enumerate(students): if student[:-1] != last_student: last_student = student[:-1] curr_rank = i + 1 rank[student[-1]] = curr_rank for r in rank: print(r)
B-smooth数(python)
题面描述
小杨同学想寻找一种名为B-smooth数的正整数。
如果一个正整数的最大质因子不超过B,则该正整数为B-smooth数。
小杨同学想知道,对于给定的n和B,有多少个不超过n的B-smooth数。
输入格式
第一行包含两个正整数n,B,含义如题面所示。
输出格式
输出一个非负整数,表示不超过n的B-smooth数的数量。
样例输入
样例输出
样例解释
在不超过10的正整数中,3-smooth 数有{1,2,3,4,6,8,9},共7个。
数据范围

对于全部数据,保证有1≤n≤106,1≤B≤106。
n, B = map(int, input().split()) is_prime = [True] * (n + 1) primes = [] max_prime_factor = [0] * (n + 1) for i in range(2, n + 1): if is_prime[i]: primes.append(i) max_prime_factor[i] = i for p in primes: if i * p > n: break is_prime[i * p] = False max_prime_factor[i * p] = max(max_prime_factor[i], p) if i % p == 0: break cnt = 0 for i in range(1, n + 1): if max_prime_factor[i] <= B: cnt += 1 print(cnt)
小杨的幸运数
时间限制:5.0 s
内存限制:128.0 MB
问题描述
小杨认为,所有大于等于a的完全平方数都是他的超级幸运数。
小杨还认为,所有超级幸运数的倍数都是他的幸运数。自然地,小杨的所有超级幸运数也都是幸运数。
对于一个非幸运数,小杨规定,可以将它一直+1,直到它变成一个幸运数。我们把这个过程叫做幸运化。例如,如果a=4,那么4是最小的幸运数,而1不是,但我们可以连续对1做3次+1操作,使其变为4,所以我们可以说,1幸运化后的结果是4。
现在,小样给出N个数,请你首先判断它们是不是幸运数;接着,对于非幸运数,请你将它们幸运化。
输入描述
第一行 2 个正整数a,N。
接下来N行,每行一个正整数x,表示需要判断(幸运化)的数。
输出描述
输出N行,对于每个给定的x,如果它是幸运数,请输出lucky ,否则请输出将其幸运化后的结果。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
1虽然是完全平方数,但它小于a,因此它并不是超级幸运数,也不是幸运数。将其进行3次+1操作后,最终得到幸运数4。
4是幸运数,因此直接输出 lucky 。
5不是幸运数,将其进行3次+1操作后,最终得到幸运数8。
9是幸运数,因此直接输出 lucky 。
样例输入 2
样例输出 2
数据规模
对于30%的测试点,保证a,x≤100,N≤100 。
对于60%的测试点,保证a,x≤106。
对于所有测试点,保证a≤1000001;保证N≤2×105;保证1≤x≤1000001。
a, n = input().split()
a, n = int(a), int(n)
max_lucky = 1001 ** 2 + 10
is_lucky = [False for i in range(max_lucky + 1)]
next_lucky = [-1 for i in range(max_lucky + 1)]
for i in range(1, max_lucky):
if i >= a and int(i ** 0.5) ** 2 == i:
is_lucky[i] = True
for j in range(i + i, max_lucky, i):
is_lucky[j] = True
for i in range(max_lucky - 1, 0, -1):
if is_lucky[i]:
next_lucky[i] = i
else:
next_lucky[i] = next_lucky[i + 1]
for i in range(n):
x = int(input())
assert 1 <= x <= 10 ** 6 + 1
if next_lucky[x] == x:
print("lucky")
else:
print(next_lucky[x])烹饪问题
时间限制:1.0 s
内存限制:128.0 MB
问题描述
有N种食材,编号从0至N-1,其中第i种食材的美味度为ai。
不同食材之间的组合可能产生奇妙的化学反应。具体来说,如果两种食材的美味度分别为x和y,那么它们的契合度为x and y。
其中,and运算为按位与运算,需要先将两个运算数转换为二进制,然后在高位补足0,再逐位进行与运算。例如,12与6的二进制表示分别为 1100 和 0110 ,将它们逐位进行与运算,得到 0100 ,转换为十进制得到4,因此12 and 6=4。在 C++ 或 Python 中,可以直接使用 & 运算符表示与运算。
现在,请你找到契合度最高的两种食材,并输出它们的契合度。
输入描述
第一行一个整数N,表示食材的种数。
接下来一行N个用空格隔开的整数,依次为a0,…,aN-1,表示各种食材的美味度。
输出描述
输出一行一个整数,表示最高的契合度。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
可以编号为1,2的食材之间的契合度为2 and 3=2,是所有食材两两之间最高的契合度。
样例输入 2
样例输出 2
样例解释 1
可以编号为3,4的食材之间的契合度为10 and 13=8,是所有食材两两之间最高的契合度。
数据规模
对于40%的测试点,保证N≤1000;
对于所有测试点,保证N≤106,0≤ai≤2147483647。
n = int(input()) a = list(map(int, input().split())) a = [0] + a def sort_(l, r, k): while l <= r: while (l <= r) and (a[l] >> k & 1): l += 1 while (l <= r) and (not (a[r] >> k & 1)): r -= 1 if l <= r: a[l], a[r] = a[r], a[l] l += 1 r -= 1 return r ans = 0 for i in range(31, -1, -1): j = sort_(1, n, i) if j >= 2: ans |= 1 << i n = j print(ans)
因数分解
时间限制:1.0 s
内存限制:128.0 MB
问题描述
每个正整数都可以分解成素数的乘积,例如:6=2×3、20=22×5
现在,给定一个正整数N,请按要求输出它的因数分解式。
输入描述
输入第一行,包含一个正整数N。约定2≤N≤1012
输出描述
输出一行,为N的因数分解式。要求按质因数由小到大排列,乘号用星号*表示,且左右各空一格。当且仅当一个素数出现多次时,将它们合并为指数形式,用上箭头^表示,且左右不空格。
样例输入1
6
样例输出1
2 * 3
样例输入2
20
样例输出2
2^2 * 5
样例输入3
23
样例输出3
23
input_number = int(input())
original_number = input_number
factors = []
def isPrime(num):
for j in range(2, int(num**0.5)):
if num % j == 0:
return False
return True
if isPrime(input_number):
factors.append([input_number, 1])
else:
for i in range(2, input_number+1):
input_number = int(input_number)
if input_number % i == 0:
factors.append([i, 0])
while input_number % i == 0:
factors[-1][1] += 1
input_number //= i
if isPrime(input_number):
if input_number != 1:
factors.append([input_number, 1])
break
for i in range(len(factors)):
if i != 0:
print(" * ", end="")
if factors[i][1] == 1:
print(factors[i][0], end="")
else:
print(f"{factors[i][0]}^{factors[i][1]}", end="")
print("")巧夺大奖
时间限制:1.0 s
内存限制:128.0 MB
问题描述
小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则:
1、游戏分为n个时间段,参加者每个时间段可以选择一个小游戏。
2、游戏中共有n个小游戏可供选择。
3、每个小游戏有规定的时限和奖励。对于第i个小游戏,参加者必须在第Ti个时间段结束前完成才能得到奖励Ri。
小明发现,这些小游戏都很简单,不管选择哪个小游戏,他都能在一个时间段内完成。关键问题在于,如何安排每个时间段分别选择哪个小游戏,才能使得总奖励最高?
输入描述
输入第一行,包含一个正整数n。 既是游戏时间段的个数,也是小游戏的个数。约定1≤n≤500。
输入第二行,包含n个正整数。第i个正整数为Ti,即第i个小游戏的完成期限。约定1≤Ti≤n。
输入第三行,包含n个正整数。第i个正整数为Ri,即第i个小游戏的完成奖励。约定1≤Ri≤1000。
输出描述
输出一行,包含一个正整数C,为最高可获得的奖励。
样例输入1
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
样例输出1
230
样例解释1
7个时间段可分别安排完成第4、2、3、1、6、7、5个小游戏,其中第4、2、3、1、7个小游戏在期限内完成。因此,可以获得总计40+60+50+70+10=230的奖励。
total_segements = int(input())
limits = []
rewards = []
s_limits = input()
s_limits = s_limits.split(' ')
s_rewards = input()
s_rewards = s_rewards.split(" ")
for item in s_limits:
limits.append(int(item))
for item in s_rewards:
rewards.append(int(item))
games = []
for i in range(len(s_limits)):
# 结束时间,奖励值,是否可以选,是否选过
games.append([limits[i], rewards[i], False, False])
def check_chooseable(states, current):
for item in states:
if item[0] >= current:
item[2] = True
def get_current_max(states, current):
maximum = 0
chosen = None
for i in range(len(states)):
if states[i][2] and not states[i][3]:
if maximum < states[i][1]:
#print(states[i][1])
maximum = max(states[i][1], maximum)
chosen = i
if chosen is not None:
states[chosen][3] = True
return maximum
total = 0
#print(games)
for t in range(total_segements, 0, -1):
#print(t)
check_chooseable(games, t)
total += get_current_max(games, t)
#print(games)
print(total)有限不循环小数
时间限制:1.0 s
内存限制:512.0 MB
题目描述
若1/a可化为一个有限的,不循环的小数,则称a为终止数。
请你求出在L到R中终止数的数量。
输入格式
输入一行,包含两个整数L,R。
输出格式
输出一行,包含一个整数,表示L到R中终止数的数量。
输入样例
2 11
输出样例
5
样例解释
在[2,11]终止数有2、4、5、8、10。
数据范围
保证1≤L≤R≤106。
# L,R输入 l, r = map(int, input().split()) # 最终的答案,初始化为0 ans = 0 for i in range(l, r + 1): t = i # 不断除以2 while t > 0 and t % 2 == 0: t //= 2 # 不断除以5 while t > 0 and t % 5 == 0: t //= 5 # 如果不含其他因子,则这个数能够表示为不循环的小数 if t == 1: ans += 1 print(ans)
找数
时间限制:1.0 s
内存限制:512.0 MB
题目描述
给定一个包含n个互不相同的正整数的数组A与一个包含m个互不相同的正整数的数组B,请你帮忙计算有多少数在数组A与 数组B中均出现。
输入格式
第一行包含两个整数n,m。
第二行包含n个正整数a1,a2,...,an表示数组A。
第二行包含m个正整数b1,b2,...,bn表示数组B。
输出格式
输出一个整数,表示在数组A与 数组B中均出现的数的个数。
输入样例
3 5 4 2 3 3 1 5 4 6
输出样例
2
样例解释
样例 1 中,4、3在数组 与 中均出现。
数据范围
对于40%的数据,保证1≤n,m≤1000。
对于100%的数据,保证1≤n,m≤105,1≤ai,bi≤109。
# 接收a,b数组的大小以及数组内容 n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) a.sort() ans = 0 # 遍历b中的每一个数 for x in b: l, r = 0, n - 1 # 二分查找a中是否包含x while l < r: mid = (l + r) // 2 # 如果a[mid]<x,则x一定在mid+1之后 if a[mid] < x: l = mid + 1 else: r = mid if a[l] == x: ans += 1 print(ans)