111 學年度商業類學生技藝競賽

題目出處：點擊

pA1. 民國年

print(int(input())-1911)

pA2. 閏年(0結束)

n = int(input())
while n:
    print("a leap year" if n%4 == 0 and n%100 != 0 or n%400 == 0 else "a normal year")
    n = int(input())

pB. 壞的遙控器

a, b = map(int, input().split())
b = b-a
if b < 0:
    b += 200
print(b)

pC. 反轉數字

print(int(input()[::-1]))

pD. 不重複隨機亂數產生器

input()
l = set([int(i) for i in input().split()])
print(len(l))
print(*sorted(l))

pE. 重複隨機亂數統計

d=[0 for i in range(1001)]
n=int(input())
l=[int(i) for i in input().split()]
for i in l:
    d[i]+=1
for i in range(1001):
    if d[i]!=0:
        print(i,d[i])

pF. 字元刪除

s1=list(input())
s2=list(input())
for i in range(len(s1)):
    if s1[i] in s2:
        s1[i]=''
print(''.join(s1))

pG. 編碼

for _ in range(int(input())):
    s = input()
    q = s[0]
    ans = ''
    num = ''
    for i in s[1::]:
        if i.isdigit():
            num += i
        else:
            ans += q*int(num)
            num = ''
            q = i
    ans += q*int(num)
    print(ans)
'''
1
A4B3C2D1E4
'''

pH. 分組反轉字串

while True:
    try:
        flag = False
        n = input().split()
        if len(n) == 1 and n[0] != "0":
            print()
        elif n[0] == "0":
            continue
        else:
            n, s = int(n[0]), n[1]
            if n == 0:
                flag = True
                break
            team = len(s)//n
            ans = ""
            for i in range(0, len(s), team):
                ans = ans+s[i:i+team][::-1]
            print(ans)
    except EOFError:
        break

pI. 字元出現次數（要多練練）

while True:
    try:
        w = list(input())
        s = list(set(w))

        s.sort(key= lambda x: (w.count(x), -ord(x)))
        for i in s:
            print(f"{ord(i)} {w.count(i)}")
    
    except:
        break

d = {}
s = input()
for i in s:
    if d.get(ord(i)):
        d[ord(i)] += 1
    else:
        d[ord(i)] = 1
for i in sorted(d, key = lambda x: [d[x], -x]):
    print(i, d[i])

pJ. 質數（要多練練）

質數只要搜索到 N 的 0.5 次方即可。

n = int(input())
for _ in range(n):
    m, p = map(int, input().split())
    if m == 1: m = 2
    for i in range(m, p+1):
        for j in range(2, int(i**0.5)+1):
            if i%j == 0:
                break
        else:
            print(i)
    if _ != n-1:
        print()

pK. 質因數

n = N = int(input())
while n:
    ans = set()
    while n != 1:
        for i in range(2, int(n**0.5)+1):
            if not(n%i):
                ans.add(i)
                n //= i
                break
        else:
            ans.add(n)
            break
    print(f"{N} : {len(ans)}")
    n = N = int(input())

pL. 二進制bit為1（要多練練）

n = int(input())
ans = 0
two = 1
while two <= n:
    cycle = n // (two*2)
    now = n % (two*2)
    ans += cycle*two
    ans += max(0, now-two+1)
    two *= 2
print(ans)

pM. 格雷碼（要多練練）

遞迴
先算1位元的格雷碼，再將1位元的前端加上'0'做正序，再把1位元的前端加上'1'做倒序

def gary(n):
    if(n == 1):
        return ['0', '1']
    lst = gary(n-1)
    output = []
    for i in lst:
        output.append('0' + i)
    for i in lst[::-1]:
        output.append('1' + i)
    return output
n = int(input())
print(*gary(n),sep='\n')

pN. 進步獎

DP

n = int(input())
s = [int(i) for i in input().split()]
dp = [1]*(n)
for i in range(n):
    for j in range(i-1, -1, -1):
        if s[j] < s[i]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))
'''
11
20 40 32 67 40 20 89 300 404 13 13
'''

pO. 硬幣（要多練練）

DP背包
dp(i)代表裝滿容量為i的背包有幾種硬幣組合

$$dp(i)=dp(i)+dp(i-coin)$$

n, x = map(int, input().split())
count = [int(i) for i in input().split()]
mod = 10**9+7 #數值過大的話就求餘數
dp = [0]*(x+1); dp[0] = 1
for coin in count:
    for i in range(coin, x+1):
        dp[i] += dp[i-coin] % mod
print(dp[x])

pP. 二元樹走訪（要多練練）

利用前序第一個為root，中序中間是root的特性，分出左子樹以及右子樹，再分成小問題然後回傳左樹 + 右樹 + root就是答案。

def tree(l, m):
    if not l:
        return ""

    node = l[0]
    node_index = m.index(node)

    left_tree = tree(l[1:1+node_index], m[:node_index])
    right_tree = tree(l[1+node_index:], m[node_index+1:])

    return left_tree + right_tree + node
while True:
    try:
        l, m = map(str, input().split())
    except:
        break
    ans = tree(l, m)
    print(ans)

pQ. 二元樹資訊

from collections import deque
n = int(input())
depth = [0]*(n)
d = {}
p = [i for i in range(n)]
for i in range(n):
    arr = [int(i) for i in input().split()]
    d[arr[0]] = arr[1::]
    for i in arr[1::]:
        if i != -1:
            p[i] = arr[0]
ans = ["" for _ in range(n)]
def find(x):
    if p[x] == x: return x
    p[x] = find(x)
    return p[x]
def bfs(x):
    q = deque([x])
    while len(q):
        node = q.popleft()
        for i in d[node]:
            if i != -1:
                depth[i] = depth[node]+1
                q.append(i)
def dfs(x):
    height = 0
    degree = 0
    for i in d[x]:
        if i != -1:
            height = max(height, dfs(i))
            degree += 1
    ans[x] = f"node {x}: parent = {p[x] if p[x] != x else -1}, degree = {degree}, depth = {depth[x]}, height = {height},"
    return height+1
root = find(0)
bfs(root)
#print(root) 根節點
dfs(root)
for i in ans:
    print(i)