# 112 商業類程式設計技藝競賽-模擬試題
題目出處：[點我](https://sci.me.ntnu.edu.tw/PortalFile/ContestData/10116/24f3c648-fed4-4680-8a79-db42708208eb.pdf)
## ==建議看完題目再來看這裡。==
## pA. 電腦教室
尋找最大值即可。
```python=
n=int(input())
a=[int(i) for i in input().split()]
print(max(a))
```
## pB. 幾何圖形多面體
使用if來判斷文字是何種圖形，並定義個變數加上該圖形有的面數，最後印出即可。
```python=
n=int(input())
s=0 #總和
for _ in range(n):
a=input()
if a=="Tetrahedron":
s+=4
elif a=="Cube":
s+=6
elif a=="Octahedron":
s+=8
elif a=="Dodecahedron":
s+=12
elif a=="Icosahedron":
s+=20
print(s)
```
## pC. 等加速度位移
把輸入的 u 跟 t 帶入 𝑆(2𝑡)=2 × u × 𝑡 即可。
```python=
while True:
try:
u,t = map(int,input().split())
except:
break
print(2*u*t)
```
## pD. 買鉛筆
人數除於12，商數 × 50，餘數 × 5 相加即可。
```python=
n=int(input())
print(50*(n//12)+5*(n%12))
```
## pE. 出現最多次的正整數
建表，把出現過的值丟入相應的 index 裡，當數值是裡面出現最多時，在印出。
```python=
n=int(input())
a=[int(i) for i in input().split()]
count=[0 for _ in range(10)]
for i in a:
count[i] += 1
for i in range(10):
if count[i]==max(count):
print(i,end=" ")
```
## pF. 蛋糕
小蛋糕加起來的面積一定等於大蛋糕的面積，所以把小蛋糕的長*寬相加，然後除於大蛋糕的寬度就是大蛋糕的長度。
:::info
沒錯這題我想很久，結果洗個澡就想到了。
:::
```python=
while True:
try:
bw=int(input())
except:
break
s=0
for _ in range(int(input())):
a,b=map(int,input().split())
s+=a*b
print(s//bw)
```
## pG. 不同的正方形
透過遞迴關係我們能得知
$$ dp(n)=
\begin{cases}
dp[0]=1\\
dp[n]=(n+1)^2+dp[n-1]& \text{if n > 0}
\end{cases}
$$
寫成一般式就會是`dp[n]=(n+1)**2+dp[n-1]`
答案就會是`dp[n-1]`
```python=
dp=[0 for _ in range(101)]
dp[0]=1
for i in range(1,101):
dp[i] = (i+1)**2+dp[i-1]
while True:
n=int(input())
if n==0:
break
print(dp[n-1])
```
## pH. Bubble 計算swaps次數
用 Bubble 排序好，每換一次 swaps 就加1，最後印出swaps即可。
```python=
t=int(input())
for _ in range(t):
swaps=0
n=int(input())
train=[int(i) for i in input().split()]
for i in range(n):
for j in range(0,n-i-1):
if train[j]>=train[j+1]:
train[j],train[j+1] = train[j+1],train[j]
swaps += 1
print(f'Optimal train swapping takes {swaps} swaps.')
```
## pI. 鬧鈴的時間
把小時換成分鐘，如果 m2 >= m1 ，直接用 `m2-m1` 就是解答。如果是 m1 比較大的話，就用 `144-(m1 - m2)`即可。
```python=
while True:
h1,m1,h2,m2=map(int,input().split())
if h1==m1==h2==m2==0:
break
m1=h1*60+m1
m2=h2*60+m2
if m1>m2:
print(1440-(m1-m2))
else:
print(m2-m1)
```
## pJ. 求數列第n項
用動態規劃即可。遞迴關係式為：
$$ d(n)=
\begin{cases}
d=1 & \text{if n = 1}\\
d[n]=d[n-1]+n-1 & \text{if n > 1}
\end{cases}
$$
一般式為`d[n] = d[n-1]+(n-1)`
```python=
import sys
dp = [0, 1]
head = 2
for i in sys.stdin:
i = int(i)
if len(dp) <= i:
for j in range(head, i+1):
dp.append(j-1+dp[j-1])
head = i+1
print(dp[i])
```
其實數字不大也能一般加到底
```python=
import sys
for i in sys.stdin:
i = int(i)
d = 1
for j in range(1, i):
d += j
print(d)
```
## pK. 表演座位
沒什麼特別的，一直比較即可。要注意的是一跟三區是每排25位，第二區是50位。
```python=
seat=int(input())
if seat<=2500:
if seat%25==0 and seat!=2500:
print(f'1 {seat//25} 25')
elif seat==2500:
print(f'1 100 25')
else:
print(f'1 {seat//25+1} {seat%25}')
elif seat<=7500:
seat-=2500
if seat%50==0 and seat!=5000:
print(f'2 {seat//50} 50')
elif seat==5000:
print(f'2 100 50')
else:
print(f'2 {seat//50+1} {seat%50}')
else:
seat-=7500
if seat%25==0 and seat!=2500:
print(f'3 {seat//25} 25')
elif seat==2500:
print(f'3 100 25')
else:
print(f'3 {seat//25+1} {seat%25}')
n = int(input())
if 0 <= n <= 2500:
print(1, 1 if n <= 25 else n//25+1 if n%25 else n//25,n%25 if n%25 else 25)
elif 2501 <= n <= 7500:
n -= 2500
print(2, 1 if n <= 50 else n//50+1 if n%50 else n//50, n%50 if n%50 else 50)
else:
n -= 7500
print(3, 1 if n <= 25 else n//25+1 if n%25 else n//25,n%25 if n%25 else 25)
```
## pL. 數字的總和
利用 python 可以切換型態的方式做總和。
```python=
while True:
n=input()
if n=='0':break
while len(n)>1:
n=str(sum([int(i) for i in n]))
print(n)
```
## pM. 快樂數
數字不大，可以使用遞迴解
```python=
def happy(i,n,first):
try:
if n==1:
print(f'Case #{i}: {first} is a Happy number.')
else:
new = str(n)
sum = 0
for c in new:
sum += int(c)**2
return happy(i,sum,first)
except:
print(f'''Case #{i}: {first} is an Unhappy number.''',end='\n')
n=eval(input())
for i in range(1,n+1):
a = eval(input())
happy(i,a,a)
```
不遞迴版本
```python=
for _ in range(1, int(input())+1):
n = N = int(input())
seen = set()
while n != 1:
if n in seen:
print(f"Case #{_}: {N} is an Unhappy number.")
break
seen.add(n)
temp = 0
for i in str(n):
temp += int(i)**2
n = temp
else:
print(f"Case #{_}: {N} is a Happy number.")
```
## pN. 輸出星期幾
用內建模組 datetime 裡的 weekday ，就可以求出當天是星期幾。
```python=
from datetime import date
t=int(input())
w=['Monday','Tuesday','Wednesday','Thursday','Friday','Saturday','Sunday']
for _ in range(t):
M,D=map(int,input().split())
week=date(2023,M,D).weekday()
print(w[week])
```
## pO. 飯店
梯形公式推導而成
$s$ 為第一項，公差為 $1$。面積就要 $\geq d$ ，就變成：
$$(s+n)*(n-s+1)/2 \geq d$$
化簡就變成：
$$ n^2+n \geq 2*d+s^2-s $$
```python=
while True:
try:
s,d = map(int,input().split())
except:
break
find=d*2+s**2-s
ans=int(find**(1/2))
if ans*(ans+1)<find:
ans+=1
print(ans)
```
## pP. 霍夫曼編碼
class寫法
```python=
class Node: #初始化節點
def __init__(self, n, leaf):
self.n = n
self.left = None
self.right = None
self.leaf = leaf
def visit(self, d):
temp = 0
if self.leaf:
return d
temp += self.left.visit(d+1)
temp += self.right.visit(d+1)
return temp
n = int(input())
tree = []
num = [int(i) for i in input().split()]
for i in range(n):
temp = Node(num[i], 1)
num[i] = temp
tree.append(temp)
while len(num) > 1:
num.sort(key=lambda x: x.n, reverse=True)
a = num.pop()
b = num.pop()
temp = Node(a.n+b.n, 0)
temp.left = a
temp.right = b
num.append(temp)
print(num[0].visit(0))
```
字典寫法
```python=
n = int(input())
num = [int(i) for i in input().split()]
d = {}
co = num.copy()
while len(num) > 1: #創造樹
num.sort()
n1 = num.pop(0)
n2 = num.pop(0)
temp = n1 + n2
d[n1] = [temp]
d[n2] = [temp]
num.append(temp)
p = num[0]
def dfs(k):
q = [k]
seen = set()
seen.add(k)
head = 0
time = 0
while head < len(q):
node = q[head]; head += 1
if node == p:
break
for i in d[node]:
if i not in seen:
q.append(i)
seen.add(i)
time += 1
return time
ans = 0
for i in co:
ans += dfs(i)
print(ans)
```
## pQ. 逆序數對數量
時間優化BIT
```python=
def check():
ans=0
for i in range(len(l)):
for j in range(i+1,len(l)):
if l[i]>l[j]:
ans+=1
return ans
n,m=map(int,input().split())
l=[i for i in range(1,n+1)]
for _ in range(m):
a,b=map(int,input().split())
a=l.index(a)
b=l.index(b)
l[a],l[b]=l[b],l[a]
print(check())
```
TLE
Sign in with Wallet
Connect another wallet