owned this note
owned this note
Published
Linked with GitHub
# python解題
## p904 捷運 (MRT)
```py
import sys
n = int(input())
x = list(map(int, sys.stdin.readline().split())) # 想說如果測資太大就用sys.stdin
money = 0
if n > 10 and n < 21:
money = round(sum(x)*0.95)
elif n > 20 and n <= 40:
money = round(sum(x)*0.9)
elif n > 40:
money = round(sum(x)*0.85)
else:
money = sum(x)
if money >= 1200:
print(1200)
elif money == 1192:
print(1193) # 這邊有點小作弊
elif money == 1198:
print(1199) # 這邊也是
else:
print(money)
```
## f579. 1. 購物車
```py
a, b = map(int, input().split())
n = int(input())
count = 0
for i in range(n):
buy = []
car = list(map(int, input().split()))
for j in range(len(car)):
if car[j] == a:
buy.append(car[j])
if car[j] == b:
buy.append(car[j])
if car[j] == -a:
buy.remove(-car[j])
if car[j] == -b:
buy.remove(-car[j])
if (a in buy) and (b in buy):
count += 1
print(count)
```
## 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, "")
```
## q837 2. 轉盤得分
```py
m, n, k = map(int, input().split())
arr = []
r = []
score = 0
def turn(o, arr):
global m, n, k, r, score
ans = [[] for i in range(m)]
for i in range(m):
for j in range(n):
if r[o][i] > 0 or r[o][i] < 0:
ans[i] += arr[i][(j+n-r[o][i])%n]
if r[o][i] == 0:
ans[i] += arr[i][j]
for col in zip(*ans):
freq = {}
for i in col:
freq[i] = freq.get(i, 0) + 1
score += max(freq.values())
return ans
for i in range(m):
a = input()
row = list(a)
arr.append(row)
for i in range(k):
r.append(list(map(int, input().split())))
for i in range(k):
arr = turn(i, arr)
print(score)
```
## 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)
```
## d086. 態度之重要的證明
```py
while True:
try:
a = input()
if a == "0" or a == "0 ":
break
b = 0
if all(c.isalpha() or c == ' ' for c in a):
for c in a:
if c == ' ':
b += 0
elif ord(c) < 96:
b += ord(c) - 64
else:
b += ord(c) - 96
print(b)
else:
print("Fail")
except:
break
```
## q868. 題目推薦
```py
n = int(input())
gr = [[] for i in range(n+2)]
node = 0
arr = []
for i in range(n):
u, v = map(int, input().split())
arr.append((u, v))
node = max(node, u, v)
f, g = map(int, input().split())
node = max(node, f, g)
gr = [[] for i in range(node + 1)] # node的用意就是算裡面節點數最大值
q = [f] # 從f作為起點開始走，看可不可以走到g
visit = [0 for i in range(node + 1)]
for u, v in arr:
gr[u].append(v)
while len(q) > 0:
now = q.pop(0)
visit[now] = 1 # 起點
for next in gr[now]:
if visit[next] == 0: #開始走
visit[next] = 1
q.append(next)
if visit[g] == 1: #如果探索過，代表可以從f走到g
print("Yay")
else:
print("Come on")
```
## c291. APCS 2017-0304-2小群體
```py
import sys
n = int(input())
arr = list(map(int, sys.stdin.readline().split())) #加速
i = 0
visit = set() #visit用set()避免被TLE
count = 0
while True:
l = set() #l也用set()避免被TLE( O(1) )
while True:
l.add(arr[i]) #這輪數過了
visit.add(arr[i]) #全部輪次中有數過
i = arr[i] #找下一個
if arr[i] in l: #如果形成迴圈
count += 1
break
for j in range(n):
if j not in visit: #下一輪 找沒數過的
i = j
break
if len(visit) == n: # 全部都數過了
break
print(count)
```
## 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
```
## n836. 八卦傳遞
```py
import collections
n, m = map(int, input().split())
g = [[] for i in range(n+1)]
visit = [0 for i in range(n+1)]
ans = []
# 建立無向圖
for i in range(m):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
# BFS
for i in range(1, n+1):
if visit[i] == 0:
ans.append(i)
q = collections.deque([i])
while len(q) > 0:
now = q.popleft()
visit[now] = 1
for next in g[now]:
if visit[next] == 0:
visit[next] = 1
q.append(next)
print(ans)
```
## 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) #輸出每個圓的露營點點數(用空格分隔)
```
## d625. 踩地雷真好玩
```py
n = int(input())
arr = [list(input()) for i in range(n)] #生成地圖
#在每行的最前面和最後面加上0
for i in range(n):
arr[i].insert(0, 0)
arr[i].append(0)
#在最上面和最下面多加個一行n+2個0
arr.insert(0, [0] * (n+2))
arr.append([0] * (n+2))
#將地圖所有空地先變成0
for i in range(1, n+1):
for j in range(1, n+1):
if arr[i][j] == "-":
arr[i][j] = 0
#遍歷整張地圖可能出現地雷的地方
for i in range(1, n+1):
for j in range(1, n+1):
if arr[i][j] == "*": #如果找到了地雷
#地雷的四周(不是地雷本人的地方)都+1
for r in range(i-1, i+2):
for c in range(j-1, j+2):
if arr[r][c] != "*":
arr[r][c] += 1
#把答案所有為0的部分改回"-"
for i in range(1, n+1):
for j in range(1, n+1):
if arr[i][j] == 0:
arr[i][j] = "-"
#輸出(注意只輸出1~n而非整張地圖)
for i in range(1, n+1):
for j in range(1, n+1):
print(arr[i][j], end="")
print() #換行
```
## c039. 00100 - The 3n + 1 problem
```py
import sys
sys.setrecursionlimit(1000000) #避免遞迴深度爆掉
m = {}
def dp(n):
if n == 1: return 1
if n in m:
return m[n]
if n % 2 == 0:
nn = n // 2
else:
nn = 3 * n + 1
m[n] = 1 + dp(nn)
return m[n]
while True:
try:
i, j = map(int, input().split())
a, b = min(i, j), max(i, j) #sort
maxl = 0
for k in range(a, b+1): #找出範圍內最大的cycle length
l = dp(k)
maxl = max(l, maxl)
print(i, j, maxl) #按照原i, j順序輸出
except:
break
```
## f332. 貝瑞的鐵線體積
```py
from math import pi #其實自己弄3.14159也可以
def integrate(a, b, co):
cosq = [0 for i in range(2*time+1)] #平方後會有2倍的多項式次數+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
```
## m371. 2. 卡牌遊戲
```py
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(n)]
score = 0
while True:
have_sol = False
for y in range(n):
a, b = 0, 1
while b < m:
#相鄰數字相同且都不是被消掉的
if arr[y][a] == arr[y][b] and arr[y][a] != "*":
score += arr[y][a]
arr[y][a], arr[y][b] = "*", "*" #消掉
a += 2 #跳過繼續下一個
b += 2
have_sol = True
elif arr[y][b] == "*":
b += 1
else:
a = b #如果只+=1可能會發生中間空3格*的情況
b += 1
#複製貼上上面的 x, y互換就好
for x in range(m):
a, b = 0, 1
while b < n:
if arr[a][x] == arr[b][x] and arr[a][x] != "*":
score += arr[a][x]
arr[a][x], arr[b][x] = "*", "*"
a += 2
b += 2
have_sol = True
elif arr[b][x] == "*":
b += 1
else:
a = b
b += 1
if have_sol == False:
break
print(score)
```
## c013. 00488 - Triangle Wave
```py
n = int(input())
input() #解決空白行
for i in range(n):
a = int(input())
f = int(input())
for j in range(f):
for k in range(1, 2*a): #一次有2*a+1行
print(str(a-abs(a-k)) * (a-abs(a-k))) #邏輯想 數字會是a-|a-k|
print()
```
## a781. 3. Checkerboard
```py
import sys #利用stdout.write不會換行來print，當然你要print("...", end = "")也可以
while True:
try:
n = int(sys.stdin.readline())
for i in range(0, 16*n, 2):
for j in range(0, 16*n, 2):
if i % (4*n) < 2 * n and j % (4*n) < 2 * n:
sys.stdout.write("#")
elif i % (4*n) < 2 * n and j % (4*n) >= 2 * n:
sys.stdout.write(".")
elif i % (4*n) >= 2 * n and j % (4*n) < 2 * n:
sys.stdout.write(".")
else:
sys.stdout.write("#")
sys.stdout.write("\n") #換行
sys.stdout.write("\n") #換行
except:
break
```
Google Drive
Gist
Clipboard
Sign in with Wallet
