# python解題
## o077 2. 電子畫布
```py
def bfs(r, c, t, x):
global maps
visit = [[0] * w for i in range(h)]
q = [(r, c)]
visit[r][c] = 1
maps[r][c] += x
while len(q)>0:
nowx, nowy = q.pop(0)
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
newx, newy = nowx+dx, nowy+dy
if newx < 0 or newy < 0 or newx >= h or newy >= w:
continue
if abs(r-newx) + abs(c - newy) <= t and visit[newx][newy] == 0:
maps[newx][newy] += x
visit[newx][newy] = 1
q.append((newx, newy))
return
h, w, n = map(int, input().split())
maps = []
for i in range(h):
row = [0 for _ in range(w)]
maps.append(row)
for i in range(n):
r, c, t, x = map(int, input().split())
bfs(r, c, t, x)
for i in range(h):
print(*maps[i])
```
## o078 3. 缺字問題
```py
visit = False
def dfs(letters, l, now):
global visit
if visit == True:
return
if len(now) == l:
if now not in v:
visit = True
print(now)
return
for i in letters:
dfs(letters, l, now + i)
letters = sorted(set(input()))
l = int(input())
s = input()
v = set()
for i in range(len(s) - l + 1):
v.add(s[i:i+l])
dfs(letters, l, "")
```
## q839. 4. 分組遊戲
```py
import collections
def bfs(m):
visit = [0 for i in range(n+1)]
count = 0
for i in range(n): #遍歷每個點作為起點BFS
if visit[i+1] == 1:
continue
count += 1
q = collections.deque([i+1]) #起點
visit[i] = 1
while len(q) > 0: #進BFS的while
now = q.popleft()
for next, distance in v[now]:
if visit[next] == 1 or distance >= m:
continue
visit[next] = 1
q.append(next)
return count >= k #距離是否大於k
n, k = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(n)] #建立地圖
r = max(max(row) for row in arr) #二分搜右側：二維串列內最大的值
l = 0 #最小值就是0 題目有規定
#建立鄰接串列v
v = [[] for _ in range(n + 1)]
for i in range(n):
for j in range(n):
if i != j:
v[i + 1].append((j + 1, arr[i][j]))
ans = -1
#二分搜
while l <= r:
m = (l + r) // 2
if bfs(m) == True: #如果能分出k組
ans = m
l = m + 1
else:
r = m - 1
print(ans)
```
## e287. 機器人的路徑
```py
from collections import deque
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(n)] #生成地圖
min_ = 1000000
count = 0
#找出地圖中最小值的位置 s
for i in range(n):
for j in range(m):
if arr[i][j] < min_:
min_ = arr[i][j]
s = (i, j)
#初始化BFS
visit = [[0] * m for i in range(n)]
q = deque()
q.append(s)
visit[s[0]][s[1]] = 1
count += arr[s[0]][s[1]] #加上初始格的數字
#BFS:貪婪式單線行走
while q:
x, y = q.popleft()
next_pos = None #下一格座標
min_sur = 1000000 #最小的那格之值
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]: #嘗試走上下左右
newx, newy = x+dx, y+dy
if 0 <= newx < n and 0 <= newy < m and visit[newx][newy] == 0: #可以走且未探訪過
#尋找最小的鄰格
if arr[newx][newy] < min_sur:
min_sur = arr[newx][newy]
next_pos = (newx, newy)
#找到下一步，走下去
if next_pos:
q.append(next_pos)
visit[next_pos[0]][next_pos[1]] = 1 #標記走過
count += arr[next_pos[0]][next_pos[1]] #加上那一格的數字
print(count)
```
## d133. 00357 - Let Me Count The Ways
```py
method = [0 for i in range(30001)]
method[0] = 1
for i in [1, 5, 10, 25, 50]:
for j in range(i, 30001):
method[j] += method[j-i]
while True:
try:
n = int(input())
if method[n] == 1:
print(f'There is only 1 way to produce {n} cents change.')
else:
print(f'There are {method[n]} ways to produce {n} cents change.')
except:
break
```
## c942. 露營區規劃
```py
import math
def place(rad, space, m): #判斷在給定的距離下能否在所有圓上放至少m個點
count = 0
#對每個圓的r計算這個圓的周長，然後除以距離，得到最多能放幾個點
for _ in rad:
count += int((2 * math.pi * _) // space)
return count >= m
while True:
n, m = map(int, input().split())
if n == 0 and m == 0: #輸入0 0測資結束
break
rad = list(map(int, input().split())) #n個圓的半徑
l, r = 0.0, max(rad) * 2 * math.pi #最小距離為0，最大距離為圓周長
#二分搜 找到最大仍可放m個點的距離
for i in range(100):
mid = (l + r) / 2
if place(rad, mid, m) == True: #如果點的數量>=m
l = mid
else:
r = mid
#根據距離判斷每個圓可以放幾個點
result = [] #每個圓的點數
total = 0 #總點數
for i in rad:
#計算這個圓最多能放幾個點，加入結果，更新總點數
d = int((2 * math.pi * i) // l)
result.append(d)
total += d
#如果總點數超過m，就從半徑最大的圓開始減少點數，直到等於m
while total > m:
maxr, maxi = -1, -1 #找半徑最大的圓的i
for i in range(n):
#如果是目前還有點數且半徑最大的圓，減少該圓之點數
if result[i] > 0 and rad[i] > maxr:
maxr = rad[i]
maxi = i
result[maxi] -= 1 #減少該圓的點數
total -= 1 #減少總點數
print(*result) #輸出每個圓的露營點點數(用空格分隔)
```
## f332. 貝瑞的鐵線體積
```py
from math import pi #其實自己弄3.14159也可以
def integrate(a, b, co):
cosq = [0 for i in range(2*time+1)] #cosq是係數(co)的平方(sq)
for i in range(time+1):
for j in range(time+1):
cosq[i+j] += co[i] * co[j] #記得是+=不是= (我就這樣吃了一次WA)
f = [] #積分後的函數
up, down = 0, 0
for i in range(2*time+1):
f.append(cosq[i]/(2*time + 1 - i)) #∫ x^n dx = x^(n+1)/(n+1)
for i in range(2*time+1):
exp = 2*time + 1 - i #每一項的次數
up += f[i]*(b**exp) #代上限 係數f[i]乘上b的exp次方
down += f[i]*(a**exp) #代下限 係數f[i]乘上a的exp次方
return up - down #代上限減下限
n = int(input())
for i in range(n):
time = int(input())
co = list(map(int, input().split())) #係數
a, b = map(int, input().split())
print(f'{pi * integrate(a, b, co):.2f}') #強制讓小數點到第二位:.2f
```
## h084. 4. 牆上海報
```py
def post(h):
w = weight.copy()
count = 0
for i in range(n):
if height[i] >= h:
count += 1 #如果這裡有牆壁，就count++
else:
count = 0 #沒有牆壁歸零跳下一個
continue
if w and count == w[0]: #如果還有須要貼東西且牆壁格數夠貼
w.pop(0) #待貼清單pop掉最前面一項
count = 0
if w == []:
return True #如果待貼清單空了(貼完了)就return true
return False
n, k = map(int, input().split())
height = list(map(int, input().split()))
weight = list(map(int, input().split()))
#二分搜(如果上面可以貼代表下面的一定更可以)
l, r = 0, max(height) + 1
while l < r:
mid = (l + r) // 2
if post(mid):
l = mid + 1
else:
r = mid
print(l-1) #因為二分搜是(l, r]，l不合法，所以要-1
```
## k413. Python 縮排檢查
```py
arr = []
stack = [0]
correct = True
isNextShouldIndent = False
while True:
try:
s = input()
arr.append(s)
except:
break
for i in range(len(arr)):
indent = len(arr[i]) - len(arr[i].lstrip())
if indent > stack[-1] and not isNextShouldIndent:
print(f'line {i+1}')
print(arr[i])
print("unexpected indent")
correct = False
break
if isNextShouldIndent:
if indent <= stack[-1]:
print(f'line {i+1}')
print(arr[i])
print("expected an indented block")
correct = False
break
stack.append(indent)
isNextShouldIndent = True if arr[i][-1] == ":" else False
continue
while stack and indent < stack[-1]:
stack.pop()
if stack and indent != stack[-1]:
print(f'line {i+1}')
print(arr[i])
print("unindent does not match any outer indentation level")
correct = False
break
isNextShouldIndent = True if arr[i][-1] == ":" else False
if correct:
print("Indention OK")
```
## f377. 運算式轉換
```py
while True:
try:
s = map(str, input().split())
dic = {"+": 0, "-": 0, "*": 1, "/":1}
stack = []
ans = []
for i in s:
if i in "+-*/":
while stack and stack[-1] != "(" and dic[stack[-1]] >= dic[i]:
ans.append(stack.pop())
stack.append(i)
elif i == "(":
stack.append(i)
elif i == ")":
while stack and stack[-1] != "(":
ans.append(stack.pop())
stack.pop()
else:
ans.append(i)
while stack:
ans.append(stack.pop())
print(*ans)
except:
break
```
## f581. 3. 圓環出口
```py
from sys import stdin
def find(target):
l, r = 0, 2 * n - 1
while l < r:
mid = (l + r) // 2
if prefix[mid] >= target:
r = mid
else:
l = mid + 1
return l
n, m = map(int, input().split())
p = list(map(int, stdin.readline().split()))
q = list(map(int, stdin.readline().split()))
prefix = [0] * (2 * n)
prefix[0] = p[0]
for i in range(1, 2 * n):
prefix[i] = prefix[i-1] + p[i % n]
finish = find(q[0]) % n
for i in range(1, m):
finish = find(prefix[finish] + q[i]) % n
print((finish + 1) % n)
```
Google Drive
Gist
Clipboard
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
