第一題：開鎖——數學期望

# 最優策略：鑰匙的選擇先從消耗時間最少的開始選擇，然后選擇第二小的依次類推
# 開鎖概率1/n
def openLockTime(n, m, time):time_reverse = []  # (n,m)->(m,n)for i in range(m):m_time = []for j in range(n):m_time.append(time[j][i])time_reverse.append(sorted(m_time))E = 0.000000p = 1 / nfor i in range(m):i_sum = 0for j in range(n):i_sum = i_sum + sum(time_reverse[i][:j + 1])E += p * i_sumreturn E# 鑰匙數、鎖個數
n, m = list(map(int, input().split()))
# 第i把鑰匙打開第j把鎖的時間
time = []
for i in range(n):t = list(map(int, input().split()))time.append(t)
print(openLockTime(n,m,time))
'''
2 4
347 177 40 84
107 282 347 193
'''# 對time進行翻轉# 鑰匙數、鎖個數
n, m = list(map(int, input().split()))
# 第i把鑰匙打開第j把鎖的時間
time = []
for i in range(n):t = list(map(int, input().split()))time.append(t)

第二題：馬夫**鏈——條件概率（矩陣相乘）

def predictOwnP(step, last, P):# 第i-1步last到第i步cur的狀態for i in range(step):stab = 0.0Own = 0.0Fail = 0.0for j in range(3):stab += P[0][j] * last[j]Fail += P[1][j] * last[j]Own += P[2][j] * last[j]last = [stab, Fail, Own]if last[-1] > 0.5:return 1else:return 0group_num = int(input())
for i in range(group_num):step = int(input())first = list(map(float, input().split()))P = []for _ in range(3):P.append(list(map(float, input().split())))print(predictOwnP(step, first, P))'''
2
2
0.4 0.2 0.4
0.2 0.1 0.7
0.3 0.5 0.2
0.5 0.4 0.1
10
0.4 0.2 0.4
0.2 0.1 0.7
0.3 0.5 0.2
0.5 0.4 0.1
'''

第三題：迎賓車隊——極差（雙指針）

def carMaxNum(n,speed):speed = sorted(speed)maxNum = 0left = 0right = 0while right < n:if speed[right] - speed[left] <= 10:maxNum = max(maxNum,right - left + 1)right += 1else:left += 1return maxNumn = int(input())
speed = list(map(int,input().split()))
print(carMaxNum(n,speed))
'''
6
17 3 21 8 44 24
'''
'''
3
9 7 4
'''

第四題：水站的水流量——直接找的規律

def calcuMaxNode(n, t):# 第i層和第i-1層的水流支路有2i-2條，每條能分到1/(2i-2)個水流量，中間的結點每秒會得到1/(i-1)個水流量，因此需要i-1s才能滿載# 外面的兩個則需要2i-2s才能滿載# 每一層滿載需要消耗的時間為ismaxT = sum([i+1 for i in range(n)])if t >= maxT:return maxT# 先確定目前流到了哪一層time = [1 for _ in range(11)]for i in range(2,11):time[i] = time[i-1] + iprint(time)layers = 1for layer in range(1,n+1):if time[layer] > t:layers = layer # 流到了第layer層,且還沒有流滿breakinside_time = layers/(layers - 1) # 里面水結點流滿需要的時間outside_time = 2*layers/(layers - 1)  # 外面2個水結點流流滿的時間if time[layers-1] + inside_time*(layers-2) > t:return sum([i for i in range(1,layers)])elif time[layers-1] + inside_time*(layers-2) <= t and time[layers] + outside_time*2 > t:return sum([i for i in range(1,layers+1)]) - 2else:return sum([i for i in range(1,layers+1)])n, t = list(map(int, input().split()))
print(calcuMaxNode(n,t))'''
3 5
'''

第五題：轟炸——DFS或者BFS（將1包圍的0改為2）

def hongzha(matrix):m = len(matrix)n = len(matrix[0])# 先將沒有被1包圍的0給去掉，沒有被1包圍也就是可以通到矩陣的四邊# 判斷是否需要繼續遍歷def judge(indexi,indexj,hashtable,matrix):if indexi < 0 or indexj < 0 or indexi >= m or indexj >= n:return Falseif hashtable[indexi][indexj] == True:return Falseif matrix[indexi][indexj] == 1:return Falsereturn True# 廣度優先搜索def bfs(indexi,indexj,hashtable,res):''':param indexi::param indexj::param hashtable::param P: 存放著四邊上的0元素坐標，后面會將不被包圍的坐標也添加上去:return:'''P= [(indexi,indexj)]hashtable[indexi][indexj] = TrueI = [0,-1,1,0]J = [-1,0,0,1]while P:indexi,indexj = P[0]res.append(P[0])for i in range(4):if judge(indexi+I[i],indexj+J[i],hashtable,matrix):P.append((indexi+I[i],indexj+J[i]))hashtable[indexi+I[i]][indexj+J[i]] = TrueP = P[1:]hashtable = [[False for _ in range(n)] for _ in range(m)]res = []for i in range(m):if judge(i,0,hashtable,matrix):bfs(i,0,hashtable,res)if judge(i,n-1,hashtable,matrix):bfs(i, n-1, hashtable, res)for j in range(n):if judge(0,j,hashtable,matrix):bfs(0,j,hashtable,res)if judge(m-1,j,hashtable,matrix):bfs(m-1,j, hashtable, res)for i in range(m):for j in range(n):if matrix[i][j] == 0 and (i,j) not in res:matrix[i][j] = 2return matriximport random
m = random.randint(5,11)
n = random.randint(5,11)
matrix = []
for i in range(m):line = []for j in range(n):line.append(random.randint(0,1))matrix.append(line)newMatrix = hongzha(matrix)
for line in newMatrix:print(line)