在升序数组nums中寻找目标值target，下列程序可以填入的是（ ）

class Search(object):
def search(self, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
________________________________________
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1

500个病毒样本中，已知有一个是病毒检测呈阳性，用试纸测试阳性病毒以后，试纸在3天以后会变色，用试纸测试时间不计，三天以后要出结果，请问最少用多少个试纸能够找出

一名收银员，给顾客找零，找零的目标是给出确定金额的同时，使用尽可能少的硬币。有不同面额的硬币：1分，5分，10分，25分。如果需要给顾客准确的零钱77分，同时使

def coin_change(amount, coins):
result = []
for coin in sorted(coins, reverse=True):
while amount >= coin:
___________________
result.append(coin)
return result
coins = [1, 5, 10, 25]
amount = 63

下列程序是素数筛的程序，横线处应该填上（ ）。

def sieve(n):
if n < 2:
return []
prime = [True] * (n+1)
prime[0] = prime[1] = False
for i in range(2, int(math.sqrt(n)) + 1):
if prime[i]:
_______________________
prime[j] = False
return [p for p in range(2, n+1) if prime[p]]

下面程序是埃氏筛的一个实现，横线处应该填写（ ）。

n = 10**8
s = [0]*(n+1)
k=0
for i in range(2,n+1):
if s[i]==0:
k+=1
___________________________
s[j]=1

下列程序中，使用了二分查找算法，横线处应该填写的是（ ）。

def search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
__________________
if arr[mid] == x:
return mid
elif arr[mid] > x:
high = mid - 1
else:
low = mid + 1
return -1

正整数1024的所有约数的和为多少？（ ）

下面程序是对n！进行唯一分解，横线处应该填入的是（ ）。

def unique_fac(n):
print(n, '=', end='')
for i in range(2, n + 1):
_____________________________
print(' {}*'.format(i), end='')
n //= i
if n % i == 0 and i == n:
print(' {}'.format(i), end='')
break
unique_fac(math.factorial(5))

假设有⼀些物品，每个物品都有⾃⼰的重量，我们需要将这些物品装⼊箱⼦中，每个箱⼦也有⾃⼰的重量限制。贪⼼算法每次都选择重量最轻的物品放⼊当前最轻的箱⼦中，如果箱⼦可以装下，就放⼊；如果箱⼦不能装下，就尝试下⼀个箱⼦，直到找到可以放⼊的箱⼦。下列贪⼼算法程序中，横线处应该填⼊的是（ ）。

下列归并算法程序中，横线处应该填入的是（ ）。

def merge(left, right):
result = []
i, j = 0, 0
———————————————————————————————
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result

下列快速排序算法中，横线处应该填入的是（ ）。

def quick(arr):
if len(arr) <= 1:
return arr
____________________
left = [x for x in arr if x < p]
middle = [x for x in arr if x == p]
right = [x for x in arr if x > p]
return quick(left) + middle + quick(right)

下列二分枚举算法中，{}处应该填入的程序是（ ）。

def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
# {}处填入
return -1

下面代码是寻找水仙花数的程序，横线处应该填写的代码是（ ）。【水仙花数是指一个n位数（n≥3），其每位数字的n次幂之和等于它本身】

def is_narcissistic_num(num):
str_num = str(num)
num_digits = len(str_num)
————————————————————————————
return num == sum_of_powers
for i in range(100, 10000):
if is_narcissistic_num(i):
print(i, "是水仙花数")

对于正整数n，欧拉函数f(n)表示小于或等于n的正整数中与n互质的数的数目，例如f(8)=4。f(100)=（ ）。

下列程序输出的是（ ）。

def reverse(string):
if len(string) == 0:
return
temp = string[0]
reverse(string[1:])
print(temp, end='')
string = "chen a dai"
reverse(string)

(-1) mod 127和126 mod 127的结果是一样的。（ ）

一个数的反码，实际上是这个数对于一个模的同余数。（ ）

1997和615用欧几里得算法计算最大公约数的过程正确。（ ）

1997/615=3(余152)
615/152=4(余7)
152/7=21(余5)
7/5=1(余2)
5/2=2(余1)
2/1=2(余0)
得出最大公约数是1

欧几里得算法适用于实数。（ ）

每个大于1的整数可以唯一地写成质数的乘积的形式。（ ）

贪婪算法的复杂度通常是线性的，即O(n)。（ ）

归并排序的时间复杂度为O(n log n)。（ ）

根据同余计算，可以推导出(a*b)%m=(a%m*b%m)%m。（ ）

二分查找算法的复杂度通常表示为O(log n)。（ ）

def(十六进制) = 103231(五进制)。（ ）

小杨的武器

时间限制：1.0 s
内存限制：512.0 MB
题面描述
小杨有n种不同的武器，他对第i种武器的初始熟练度为ci。小杨会依次参加m场战斗，每场战斗小杨只能且必须选择一种武器使用，假设小杨使用了第i种武器参加了第j场战斗，战斗前该武器的熟练度为bj，则战斗后小杨对该武器的熟练度会变为bj+aj。小杨想请你编写程序帮他计算出如何选择武器才能使得m场战斗后，自己对n种武器的熟练度的最大值尽可能大。

第一行包含两个正整数n, m，含义如题面所示。
第二行包含n个正整数ci，代表小杨对武器的初始熟练度。
第三行包含m个正整数aj，代表每场战斗后武器熟练度的变化值。

输出一个整数，代表m场战斗后小杨对n种武器的熟练度的最大值最大是多少。

样例输入
2 2
9 9
1 -1
样例输出
10
数据范围
对于全部数据，保证有1 ≤ n, m ≤ 10⁵，1 ≤ ci ≤ 10⁹，-10⁹ ≤ aj ≤ 10⁹。

挑战怪物

时间限制：1.0 s
内存限制：512.0 MB
题面描述
小杨正在和一个怪物战斗，怪物的血量为x，只有当怪物的血量恰好为0时小杨才能够成功击败怪物。小杨有两种攻击怪物的方式：物理攻击，假设当前为小杨第i次使用物理攻击，则会对怪物造成2^(i-1)点伤害；魔法攻击，小杨选择任意一个质数p（p不能超过怪物当前血量），对怪物造成p点伤害。由于小杨并不擅长魔法，他只能使用至多一次魔法攻击。小杨想知道自己能否击败怪物，如果能，小杨想知道自己最少需要多少次攻击。

第一行包含一个正整数t，代表测试用例组数。
接下来是t组测试用例。对于每组测试用例，第一行包含一个正整数x，代表怪物血量。

对于每组测试用例，如果小杨能够击败怪物，输出一个整数，代表小杨需要的最少攻击次数，如果不能击败怪物，输出-1。

样例输入
3
6
188
9999
样例输出
2
4
-1
数据范围
对于全部数据，保证有1 ≤ t ≤ 10⁴，1 ≤ x ≤ 10⁵。