Algo and Math
001 - Print 5+N
print(int(input()) + 5)
002 - Sum of 3 Integers
print(sum(map(int, input().split())))
003 - Sum of N Integers
input()
print(sum(map(int, input().split())))
004 - Product of 3 Integers
import functools
import operator
print(functools.reduce(operator.mul, map(int, input().split())))
005 - Modulo 100
input()
print(sum(map(int, input().split())) % 100)
006 - Print 2N+3
print(int(input()) * 2 + 3)
007 - Number of Multiples 1
在不超過 N 的正整數中，有多少個數是 X 的倍數，或者 Y 的倍數？
import math
n, x, y = map(int, input().split())
print(n // x + n // y - n // math.lcm(x, y))
008 - Brute Force 1
你有兩張卡片，分別是紅色和藍色，你需要在每張卡片上寫下 1 到 N 之間的整數。有多少種寫法可以讓卡片上數字的總和不超過 S？
- 1 ≤ N ≤ 1000
- 1 ≤ S ≤ 2000
$$\sum_x\sum_y |(x + y \leq S)|$$
n, s = map(int, input().split())
print(sum(x + y <= s for x in range(1, n + 1) for y in range(1, n + 1)))
009 - Brute Force 2
有 N 張卡片排成一列。第 i 張卡片 (1 ≤ i ≤ N) 上寫著整數 $A_i$。 請問是否可以從卡片中選擇一些，使得它們的總和恰好為 S？
- 1 ≤ N ≤ 60
- 1 ≤ $A_i$ ≤ 10000
- 1 ≤ S ≤ 10000
- 輸入皆為整數
n, s = map(int, input().split())
v = [False] * (s + 1)
v[0] = True
for x in map(int, input().split()):
v = [v[i] or (i >= x and v[i - x]) for i in range(s + 1)]
print(["No", "Yes"][v[s]])
010 - Factorial
import math
print(math.factorial(int(input())))
import functools
import operator
fac = lambda n: functools.reduce(operator.mul, range(1, n + 1), 1)
print(fac(int(input())))
011 - Print Prime Numbers
請按照由小到大的順序，列印出所有不大於 N 的質數。
n = int(input())
ans = []
for i in range(2, n + 1):
if all(i % x != 0 for x in ans):
ans.append(i)
print(*ans)
(Cont) 篩法解
sieve:
n = int(input())
p = [True] * (n + 1)
p[0] = p[1] = False
ans = []
for i in range(2, n + 1):
if p[i]:
ans.append(i)
for j in range(i * i, n + 1, i):
p[j] = False
print(*ans)
sieve2
def sieve(a):
return [a[0]] + sieve([x for x in a[1:] if x % a[0] != 0]) if a else []
print(sieve(list(range(2, 1000))))
012 - Primality Test
請判斷給定的數字 N 是否為質數。
import math
n = int(input())
ans = all(n % i != 0 for i in range(2, math.isqrt(n) + 1))
print(["No", "Yes"][ans])
013 - Divisor Enumeration
給定一個整數 N。請列舉 N 的所有因數。
import math
n = int(input())
ans = []
for i in range(1, math.isqrt(n) + 1):
if n % i == 0:
ans.append(i)
if i != n // i:
ans.append(n // i)
print(*sorted(ans))
014 - Factorization
將自然數 N 進行質因數分解。
n = int(input())
i = 2
ans = []
while i * i <= n:
while n % i == 0:
ans.append(i)
n //= i
i += 1
if n > 1:
ans.append(n)
print(*ans)
015 - Calculate GCD
請找出 A 和 B 的最大公約數。
限制
- 1 ≤ A, B ≤ 109
- A 和 B 為整數
a, b = map(int, input().split())
gcd = lambda a, b : a if b == 0 else gcd(b, a % b)
print(gcd(a, b))
016 - Greatest Common Divisor of N Integers
給定 N 個正整數 $A_1, A_2, \dots, A_N$，請計算它們的最大公約數。
import math
input()
print(math.gcd(*map(int, input().split())))
017 - Least Common Multiple of N Integers
給定 N 個正整數 $A_1, A_2, \dots, A_N$，請計算它們的最小公倍數。
import math
input()
print(math.lcm(*map(int, input().split())))
018 - Convenience Store 1
便利商店裡賣有 N 種商品，第 i 種商品（1 ≤ i ≤ N）的價格是 $A_i$ 元。
從不同的兩種商品中，總金額為 500 元的方法有多少種？
限制
- 2 ≤ N ≤ 200000
- $A_i$ 是 100、200、300、400 其中之一
- 所有輸入皆為整數
from collections import defaultdict
d = defaultdict(int)
int(input())
ans = 0
for x in map(int, input().split()):
ans += d[500 - x]
d[x] += 1
print(ans)
019 - Choose Cards 1
有 N 張卡片，從左到右編號為 i（1 ≤ i ≤ N），第 i 張卡片的顏色是 $A_i$。當 $A_i$=1 時為紅色，$A_i$=2 時為黃色，$A_i$=3 時為藍色。有多少種選擇 2 張相同顏色卡片的方法？
from collections import defaultdict
d = defaultdict(int)
int(input())
ans = 0
for x in map(int, input().split()):
ans += d[x]
d[x] += 1
print(ans)
020 - Choose Cards 2
你有 N 張卡片，從左到右，第 i 張卡片上寫著一個整數 A_i。
請問有多少種選擇 5 張卡片的方法，使得選中的卡片上所寫的整數的總和恰好是 1000？
import functools
n = int(input())
a = list(map(int, input().split()))
@functools.cache
def dp(i, sel, remain):
if remain == 0 and sel == 0:
return 1
if i < 0 or remain <= 0 or sel <= 0:
return 0
return dp(i - 1, sel, remain) + dp(i - 1, sel - 1, remain - a[i])
print(dp(n - 1, 5, 1000))
021 - Combination Easy
給定整數 n 和 r。
請編寫一個程式，計算並輸出 ${}_n\mathrm{C}_r$。
限制條件
- 1 ≤ r ≤ n ≤ 20
- 所有輸入皆為整數
from functools import cache
@cache
def nCr(n, r):
if r == 0 or r == n:
return 1
if r > n:
return 0
return nCr(n - 1, r) + nCr(n - 1, r - 1)
n, r = map(int, input().split())
print(nCr(n, r))
from math import factorial as f
n, r = map(int, input().split())
print(f(n) // (f(r) * f(n - r)))
022 - Choose Cards 3
你有 N 張卡片，每張卡片上寫著一個整數，左邊第 i 張卡片上的數字是 A_i。
請寫一個程式，計算有多少種選擇兩張卡片的方法，使得這兩張卡片上的數字之和為 100000。
from collections import defaultdict
d = defaultdict(int)
int(input())
ans = 0
for x in map(int, input().split()):
ans += d[100000 - x]
d[x] += 1
print(ans)
023 - Dice Expectation
你有兩個 N 面骰子，分別為藍色和紅色。每個骰子的點數如下：
- 藍色骰子：以相同的機率顯示 B₁，B₂，…，Bₙ。
- 紅色骰子：以相同的機率顯示 R₁，R₂，…，Rₙ。
你同時擲這兩個骰子，而你獲得的獎金金額等於兩個骰子點數的總和。請你計算你獲得獎金的期望值。
n = int(input())
f = lambda : sum(map(int, input().split())) / n
print(f() + f())
024 - Answer Exam Randomly
一個國語測驗有 N 道題目，所有題目都是選擇題。 第 i 題 (1 ≤ i ≤ N) 有 P_i 個選項，其中只有一個是正確答案，每題配點為 Q_i 分。 太郎君完全沒有頭緒，決定隨機回答所有題目。 請計算太郎君能獲得的點數的期望值。
n = int(input())
ans = 0
for _ in range(n):
p, q = map(int, input().split())
ans += q / p
print(ans)
025 - Jiro’s Vacation
次郎君的暑假有 N 天。
他決定第 i 天 (1 ≤ i ≤ N) 的學習時間，按照以下步驟：
- 每天早上擲骰子。
- 如果擲出 1 或 2：學習 Ai 小時。
- 如果擲出 3、4、5 或 6：學習 Bi 小時。
請編寫一個程式來計算他在整個暑假的總學習時間的期望值。
n = int(input())
ans = 0
for a, b in zip(map(int, input().split()), map(int, input().split())):
ans += a / 3 + b * 2 / 3
print(ans)
026 - Coin Gacha
你有一台機器，每次投入 1 美元，就會等機率地出現 N 種不同種類的硬幣中的一種。
請你編寫一個程式，計算收集所有 N 種硬幣所需的期望花費金額。
條件
- 2 ≤ N ≤ 106
- N 是一個整數
n = int(input())
print(sum(n / i for i in range(1, n + 1)))
027 - Sorting
給定一個長度為 N 的數組 [A₁，A₂，…，Aₙ]。
請基於書中描述的「進行合併排序的未完成程序」，編寫一個對數組進行升序排序的程序。
限制
- 通過正確解答名為 “small” 的測試案例，可以獲得 50% 的分數。
- “small” 測試案例滿足以下限制：
- 2 ≤ N ≤ 2000
- 1 ≤ Aᵢ ≤ 10⁹
- 所有輸入都是整數
- “small” 測試案例滿足以下限制：
- 通過正確解答滿足以下限制的測試案例，可以獲得全部的分數：
- 2 ≤ N ≤ 200000
- 1 ≤ Aᵢ ≤ 10⁹
- 所有輸入都是整數
import heapq
input()
a = list(map(int, input().split()))
heapq.heapify(a)
ans = []
while a:
ans.append(heapq.heappop(a))
print(*ans)
028 - Frog 1
有 N 個平台。平台編號為 1, 2, …, N。對於每個 i (1 ≤ i ≤ N)，平台 i 的高度為 h_i。 起初，青蛙在平台 1 上。青蛙重複以下行動若干次，試圖到達平台 N。
- 當青蛙在平台 i 上時，跳到平台 i + 1 或 i + 2。此時，跳躍到的平台是 j，需要支付成本 |h_i - h_j|。
求青蛙到達平台 N 所需支付的總成本的最小值。
n = int(input())
a = list(map(int, input().split()))
dp = [0] * n
for i in range(1, n):
dp[i] = dp[i - 1] + abs(a[i] - a[i - 1])
if i >= 2:
dp[i] = min(dp[i], dp[i - 2] + abs(a[i] - a[i - 2]))
print(dp[-1])
029 - Climb Stairs
太郎君想要爬上 N 級台階。他可以一次爬 1 級或 2 級台階。他從第 0 級台階開始，計算有多少種不同的方式可以到達第 N 級台階。
限制
- 1 ≤ N ≤ 45
- N 是一個整數
a, b = 0, 1
for _ in range(int(input())):
a, b = b, b + a
print(b)
030 - Knapsack 1
有 N 個物品。物品有編號 1, 2, …, N。對於每個 i ( 1 ≤ i ≤ N )，物品 i 的重量是 wᵢ，價值是 vᵢ。太郎君從 N 個物品中選擇一些，放進背包裡帶走。背包的容量是 W，帶走的物品的總重量必須 ≤ W。求太郎君帶走的物品的價值總和的最大值。
$$ dp[i][j] = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \newline dp[i-1][j] & \text{if } w_i > j \newline \max(dp[i-1][j], dp[i-1][j-w_i] + v_i) & \text{if } w_i \le j \end{cases} $$
n, m = map(int, input().split())
dp = [0] * (m + 1)
for _ in range(n):
w, v = map(int, input().split())
for i in range(m, w - 1, -1):
dp[i] = max(dp[i], dp[i - w] + v)
print(dp[m])
031 - Taro’s Vacation
太郎君的暑假有 N 天，已知如果他在第 i 天學習，他的實力會增加 A_i 。但是，他不想連續兩天都學習。請你編寫一個程式，計算太郎君在暑假期間最多能提升多少實力。
條件：
- 2 ≤ N ≤ 500000
- 0 ≤ A_i ≤ 10^9
- 所有輸入皆為整數
input()
rest, study = 0, 0
for x in map(int, input().split()):
study, rest = max(rest + x, study), max(study, rest)
print(max(study, rest))
032 - Binary Search
給你一個長度為 N 的數組 A = [A_1, …, A_N]，以及一個詢問（查詢）。
詢問的內容如下：
詢問：元素 X 是否在數組 A 中？
請編寫一個程式，針對給定的詢問，輸出答案。
限制
1 ≤ N ≤ 10^5 1 ≤ X ≤ 10^9 1 ≤ A_i ≤ 10^9 所有輸入皆為整數。
import bisect
n, x = map(int, input().split())
a = sorted(list(map(int, input().split())))
index = bisect.bisect_left(a, x)
print(["No", "Yes"][index < n and a[index] == x])
033 - Distance
在二維平面上有點A, B, C。點 A 的坐標是 (a_x, a_y)，點 B 的坐標是 (b_x, b_y)，點 C 的坐標是 (c_x, c_y)。
求點 A 與線段 BC 上點的最短距離。
import math
read_point = lambda : tuple(map(int, input().split()))
a, b, c = read_point(), read_point(), read_point()
dot = lambda p1, p2 : p1[0] * p2[0] + p1[1] * p2[1]
sub = lambda p1, p2 : (p1[0] - p2[0], p1[1] - p2[1])
ba = sub(a, b)
bc = sub(c, b)
ac = sub(c, a)
t = dot(ba, bc) / dot(bc, bc)
if 0 <= t <= 1:
proj = (b[0] + bc[0] * t, b[1] + bc[1] * t)
print(math.hypot(*sub(proj, a)))
else:
print(min(math.hypot(*ba), math.hypot(*ac)))
complex流派:
$$\text{conj}(a) \cdot b = (a_r + a_i i)(b_r - b_i i) = a_r b_r + a_i b_i + i(a_i b_r - a_r b_i) = \vec{a} \cdot \vec{b} + i(\vec{a} \times \vec{b})$$
$$\text{Re}(\text{conj}(a) \cdot b) = \vec{a} \cdot \vec{b}$$ $$\text{Im}(\text{conj}(a) \cdot b) = \vec{a} \times \vec{b}$$
read_point = lambda : complex(*map(int, input().split()))
a, b, c = read_point(), read_point(), read_point()
bc, ba = c - b, a - b
t = (ba.conjugate() * bc).real / abs(bc) ** 2
if 0 <= t <= 1:
proj = b + t * bc
print(abs(a - proj))
else:
print(min(abs(a - b), abs(a - c)))
034 - Nearest Points
在二維平面上有 N 個點，第 i 個點 (1 ≤ i ≤ N) 的坐標是 (x_i, y_i)。
請找出距離最近的兩個點之間的距離。
限制：
- 2 ≤ N ≤ 2000
- 0 ≤ x_i, y_i ≤ 10^6 (1 ≤ i ≤ N)
- 所有輸入都是整數
import math
import itertools
n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]
print(min(math.dist(x, y) for x, y in itertools.combinations(points, 2)))
035 - Two Circles
在二維平面上有兩個圓，其資訊如下：
- 第一個圓的圓心座標為 (x₁，y₁)，半徑為 r₁
- 第二個圓的圓心座標為 (x₂，y₂)，半徑為 r₂
這兩個圓的位置關係有以下五種情況：
- 其中一個圓完全包含另一個圓，且兩個圓不相切。
- 其中一個圓完全包含另一個圓，且兩個圓相切。
- 兩個圓互相交錯。
- 兩個圓的內部沒有共同部分，但兩個圓相切。
- 兩個圓的內部沒有共同部分，且兩個圓不相切。
給定這兩個圓的資訊，請判斷它們屬於哪一種位置關係，並輸出對應的編號。
import math
x1, y1, r1 = map(int, input().split())
x2, y2, r2 = map(int, input().split())
match (math.dist((x1, y1), (x2, y2)), r1, r2):
case (d, r1, r2) if d < abs(r1 - r2):
print(1)
case (d, r1, r2) if d == abs(r1 - r2):
print(2)
case (d, r1, r2) if abs(r1 - r2) < d < r1 + r2:
print(3)
case (d, r1, r2) if d == r1 + r2:
print(4)
case (d, r1, r2) if d > r1 + r2:
print(5)
036 - : (Colon)
考慮一個類比時鐘，其時針和分針的長度分別為 A 厘米和 B 厘米。時針和分針各自的一端固定在同一個固定點上，且它們繞該點以恆定的角速度順時針旋轉。時針需要 12 小時旋轉一圈，分針需要 1 小時旋轉一圈。在 0 時 0 分時，時針和分針重合。現在，給定時間恰好是 H 時 M 分，請問兩針未固定的一端之間的距離是多少厘米？
-
首先計算時針和分針的角度（弧度制）：
- 時針角度：$\theta_h = (h/12 + m/720) \times 2\pi$
- 分針角度：$\theta_m = (m/60) \times 2\pi$
-
使用複數表示時針和分針末端的位置：
- 時針位置：$P_h = A \cdot e^{i\theta_h}$
- 分針位置：$P_m = B \cdot e^{i\theta_m}$
這裡使用歐拉公式 $e^{i\theta} = \cos\theta + i\sin\theta$，將極坐標轉換為複平面上的點。
import math
a, b, h, m = map(int, input().split())
angle_hour = (h / 12 + m / 720) * math.tau
angle_minute = m / 60 * math.tau
p_hour = a * (math.e ** complex(0, angle_hour))
p_minute = b * (math.e ** complex(0, angle_minute))
print(abs(p_hour - p_minute))
037 - Intersection
在二維平面上，存在兩條線段。
第一條線段連接點 (x₁，y₁) 和 (x₂，y₂)。 第二條線段連接點 (x₃，y₃) 和 (x₄，y₄)。
如果這兩條線段相交，請輸出 Yes，如果它們不相交，請輸出 No。
這裡，兩條線段相交指的是，存在一個點同時包含於這兩條線段。
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __add__(self, other):
return Point(self.x + other.x, self.y + other.y)
def __sub__(self, other):
return Point(self.x - other.x, self.y - other.y)
def __mul__(self, scalar):
return Point(self.x * scalar, self.y * scalar)
def dot(self, other):
return self.x * other.x + self.y * other.y
def cross(self, other):
return self.x * other.y - self.y * other.x
def p_on_seg(p, a, b):
return (
min(a.x, b.x) <= p.x <= max(a.x, b.x)
and min(a.y, b.y) <= p.y <= max(a.y, b.y)
and (p - a).cross(b - a) == 0
)
r = lambda: Point(*map(int, input().split()))
a, b, c, d = r(), r(), r(), r()
d1 = (b - a).cross(c - a)
d2 = (b - a).cross(d - a)
d3 = (d - c).cross(b - c)
d4 = (d - c).cross(a - c)
ans = (
(d1 * d2 < 0 and d3 * d4 < 0)
or p_on_seg(a, c, d)
or p_on_seg(b, c, d)
or p_on_seg(c, a, b)
or p_on_seg(d, a, b)
)
print("Yes" if ans else "No")
[!CAUTION] 這題如果使用浮點數運算可能會有精度問題。以下做法會得到一個WA。
r = lambda: complex(*map(int, input().split()))
a, b, c, d = r(), r(), r(), r()
cross = lambda a, b: (a.conjugate() * b).imag
def p_on_seg(p, a, b):
return (
min(a.real, b.real) <= p.real <= max(a.real, b.real)
and min(a.imag, b.imag) <= p.imag <= max(a.imag, b.imag)
and cross(p - a, b - a) == 0
)
d1 = cross(b - a, c - a)
d2 = cross(b - a, d - a)
d3 = cross(d - c, b - c)
d4 = cross(d - c, a - c)
ans = (
(d1 * d2 < 0 and d3 * d4 < 0)
or p_on_seg(a, c, d)
or p_on_seg(b, c, d)
or p_on_seg(c, a, b)
or p_on_seg(d, a, b)
)
print("Yes" if ans else "No")
038 - How Many Guests?
遊樂園「ALGO-RESORT」將舉辦為期 N 天的活動，第 i 天 (1 ≤ i ≤ N) 有 A_i 個人來訪。
請撰寫程式回答以下總共 Q 個問題。
- 第 1 個問題：從第 L_1 天到第 R_1 天的總來訪人數是多少？
- 第 2 個問題：從第 L_2 天到第 R_2 天的總來訪人數是多少？
- …
- 第 Q 個問題：從第 L_Q 天到第 R_Q 天的總來訪人數是多少？
限制
- 1 ≤ N, Q ≤ 10^5
- 1 ≤ A_i ≤ 10000
- 1 ≤ L_i ≤ R_i ≤ N
- 所有輸入皆為整數
n, q = map(int, input().split())
s = [0] + list(map(int, input().split()))
for i in range(1, n + 1):
s[i] += s[i - 1]
for _ in range(q):
l, r = map(int, input().split())
print(s[r] - s[l - 1])
[!TIP] 前綴和
039 - Snowy Days
ALGO 國被分為 N 個區域，從西邊開始依次編號為 1 到 N。
最初，所有區域都沒有積雪，但接下來的 Q 天將持續降雪。在第 i 天 (1 ≤ i ≤ Q)，區域 Lᵢ, Lᵢ₊₁, …, Rᵢ 的積雪量預計將增加 Xᵢ cm。
編寫一個程式，輸出一個長度為 N-1 的字串，表示降雪結束後各區域積雪量的大小關係。字串的第 i 個字符應如下：
- 如果（區域 i 的積雪量）>（區域 i+1 的積雪量）：輸出
> - 如果（區域 i 的積雪量）=（區域 i+1 的積雪量）：輸出
= - 如果（區域 i 的積雪量）<（區域 i+1 的積雪量）：輸出
<
例如：
如果積雪量從區域 1 開始依次為 [3 cm, 8 cm, 5 cm, 5 cm, 4 cm]，則正確的輸出為 <>=>。
限制
- 2 ≤ N ≤ 10⁵
- 1 ≤ Q ≤ 10⁵
- 1 ≤ Lᵢ ≤ Rᵢ ≤ N
- 1 ≤ Xᵢ ≤ 10000
- 所有輸入均為整數
n, q = map(int, input().split())
s = [0] * (n + 2)
for _ in range(q):
l, r, x = map(int, input().split())
s[l] += x
s[r + 1] -= x
for i in range(1, n + 1):
s[i] += s[i - 1]
for i in range(1, n):
sgn = (s[i] > s[i + 1]) - (s[i] < s[i + 1])
print("<=>"[sgn + 1], end='')
print()
[!TIP] imos法
040 - Travel
ALGO 鐵道資訊線上有 N 個車站，從西邊開始依序編號為 1 到 N。車站 i 和車站 i+1 (1 ≤ i ≤ N-1) 之間有雙向連接，距離為 A_i 公里。
太郎君從車站 B_1 出發，依序經過車站 B_2, B_3, …, B_{M-1}，最後在車站 B_M 結束旅程。請你計算他總共移動了多少公尺。
限制
- 2 ≤ N ≤ 200,000
- 2 ≤ M ≤ 200,000
- 1 ≤ A_i ≤ 10^7 (1 ≤ i ≤ N-1)
- 1 ≤ B_j ≤ N (1 ≤ j ≤ M)
- B_{j} ≠ B_{j+1} (1 ≤ j ≤ M-1)
- 所有輸入皆為整數
n = int(input())
coordinates = [0] * (n + 1)
a = list(map(int, input().split()))
for i in range(2, n + 1):
coordinates[i] = coordinates[i - 1] + a[i - 2]
m = int(input()) - 1
x = int(input())
ans = 0
for _ in range(m):
y = int(input())
ans += abs(coordinates[x] - coordinates[y])
x = y
print(ans)
041 - Convenience Store 2
某間便利商店在時刻 0 開門，在時刻 T 關門。這間便利商店有 N 位員工在工作，第 i 位員工（1 ≤ i ≤ N）在時刻 L_i 上班，在時刻 R_i 下班。請撰寫一個程式，對於 t = 0, 1, 2, …, T-1，輸出在時刻 t+0.5 時，便利商店裡的員工數量。
限制
- 1 ≤ T ≤ 500,000
- 1 ≤ N ≤ 500,000
- 0 ≤ L_i < R_i ≤ T (1 ≤ i ≤ N)
- 所有輸入皆為整數
T = int(input())
n = int(input())
a = [0] * (T + 1)
for _ in range(n):
l, r = map(int, input().split())
a[l] += 1
a[r] -= 1
for i in range(1, T + 1):
a[i] += a[i - 1]
for i in range(T):
print(a[i])
042 - Sum of Divisors
對於正整數 X，我們定義 f(X) 為 X 的正因數的個數。 給定一個正整數 N，計算 $\sum_{K=1}^N K * f(K)$。
$1 ≤ N ≤ 10^7$
n = int(input())
f = [1] * (n + 1)
for i in range(2, n + 1):
for j in range(i, n + 1, i):
f[j] += 1
ans = 0
for i in range(1, n + 1):
ans += i * f[i]
print(ans)
043 - Depth First Search
給定一個有 N 個頂點 M 條邊的無向圖，頂點的編號分別為 1, 2, …, N。第 i 條邊連接頂點 A_i 和頂點 B_i。
如果整個圖是連通的，輸出: The graph is connected.
否則，輸出: The graph is not connected.
import sys
sys.setrecursionlimit(10 ** 6)
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
vis = set()
def dfs(u):
if u in vis:
return
vis.add(u)
for v in g[u]:
dfs(v)
for _ in range(m):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
dfs(1)
if len(vis) == n:
print("The graph is connected.")
else:
print("The graph is not connected.")
Disjoint set流派
import sys
sys.setrecursionlimit(10 ** 6)
n, m = map(int, input().split())
parent = list(range(n + 1))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
for _ in range(m):
u, v = map(int, input().split())
parent[find(u)] = find(v)
if all(find(i) == find(1) for i in range(1, n + 1)):
print("The graph is connected.")
else:
print("The graph is not connected.")
044 - Shortest Path 1
給定一個有 N 個頂點和 M 條邊的無向圖。每個頂點都有一個從 1 到 N 的編號，第 i 條邊連接頂點 A_i 和頂點 B_i。
對於所有從 1 到 N 的整數 k，請回答以下問題：
考慮從頂點 1 走到頂點 k，經過若干條邊。輸出需要經過的邊的最小數量。如果無法移動，則輸出 -1。
約束：
- 所有輸入都是整數
- 1 ≤ N ≤ 10^5
- 0 ≤ M ≤ min(10^5, N(N-1)/2)
- 1 ≤ A_i < B_i ≤ N
- 圖中沒有多重邊或自環。
from collections import deque
q = deque()
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
d = [-1] * (n + 1)
d[1] = 0
for _ in range(m):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
q.append(1)
while q:
u = q.popleft()
for v in g[u]:
if d[v] == -1:
d[v] = d[u] + 1
q.append(v)
for k in range(1, n + 1):
print(d[k])
045 - Easy Graph Problem（★2）
給定一個有 N 個頂點和 M 條邊的連通無向簡單圖。圖的頂點分別被標記為 1 到 N。第 i 條邊連接頂點 a_i 和 b_i（雙向）。
請你輸出滿足以下條件的頂點的數量：
- 恰好存在一個比自身頂點編號小的相鄰頂點。
限制
- 2 ≤ N ≤ 100000
- N - 1 ≤ M ≤ min(N(N - 1)/2, 100000)
- 1 ≤ a_i, b_i ≤ N
- 給定的圖是簡單圖。
- 給定的圖是連通圖。
- 輸入的所有值都是整數。
n, m = map(int, input().split())
d = [0] * (n + 1)
for _ in range(m):
u, v = map(int, input().split())
d[max(u, v)] += 1
print(sum(x == 1 for x in d))
046 - 幅優先探索
from collections import deque
R, C = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
g = [input() for _ in range(R)]
d = [[-1] * C for _ in range(R)]
d[sx-1][sy-1] = 0
q = deque()
q.append((sx-1, sy-1))
while q:
x, y = q.popleft()
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < R and 0 <= ny < C and g[nx][ny] != '#' and d[nx][ny] == -1:
d[nx][ny] = d[x][y] + 1
q.append((nx, ny))
print(d[gx-1][gy-1])
047 - Bipartite Graph
給定一個有 N 個頂點和 M 條邊的圖。每個頂點都標有從 1 到 N 的數字，第 i 條邊 (1 ≤ i ≤ M) 連接頂點 Aᵢ 和頂點 Bᵢ（雙向）。
如果這個圖是二部圖，輸出 “Yes”，如果不是，輸出 “No”。
n, m = map(int, input().split())
c = [None] * (n + 1)
g = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
def dfs(u, color):
c[u] = color
for v in g[u]:
if c[v] is None:
if not dfs(v, 1 - color):
return False
elif c[v] == c[u]:
return False
return True
for i in range(1, n + 1):
if c[i] is not None:
continue
if not dfs(i, 0):
print("No")
break
else:
print("Yes")
048 - Small Multiple
找出 K 的正整數倍數，其十進位表示下各個位數的總和的最小值。
$$2 ≤ K ≤ 10^5$$
import heapq
import math
k = int(input())
d = [math.inf] * k
q = [(i, i % k) for i in range(1, 10)]
heapq.heapify(q)
while q:
cost, mod = heapq.heappop(q)
if d[mod] < cost:
continue
for i in range(10):
new_mod = (mod * 10 + i) % k
new_cost = cost + i
if new_cost < d[new_mod]:
d[new_mod] = new_cost
heapq.heappush(q, (new_cost, new_mod))
print(d[0])
from collections import deque
import math
k = int(input())
d = [math.inf] * k
q = deque()
for i in range(1, 10):
d[i % k] = min(d[i % k], i)
q.append((i % k, i))
while q:
mod, cost = q.popleft()
for i in range(10):
new_mod = (mod * 10 + i) % k
new_cost = cost + i
if d[new_mod] > new_cost:
d[new_mod] = new_cost
q.append((new_mod, new_cost))
print(d[0])
049 - Fibonacci Easy (mod 1000000007)
給定以下遞迴關係定義的斐波那契數列的第 N 項 a_N，求其對 1000000007 (=10^9+7) 取餘數的結果。
- a_1 = 1, a_2 = 1
- a_n = a_{n-1} + a_{n-2} (n ≥ 3)
限制：
- 3 ≤ N ≤ 10^7
- N 為整數
https://en.wikipedia.org/wiki/Fibonacci_sequence#Matrix_form
import numpy as np
_MOD = 10 ** 9 + 7
_N = 2
_A = np.matrix([[1, 1], [1, 0]], dtype=np.uint64)
_B = np.matrix([[1], [0]], dtype=np.uint64)
def pow_mod(a, n):
res = np.eye(_N, dtype=np.uint64)
while n > 0:
if n % 2 == 1:
res = res * a % _MOD
a = a * a % _MOD
n //= 2
return res
def fib(n):
return (pow_mod(_A, n) * _B % _MOD)[1, 0]
print(fib(int(input())))
050 - Power
請計算 a 的 b 次方除以 1000000007 (即 10^9 + 7) 的餘數。
限制
- 1 ≤ a ≤ 100
- 1 ≤ b ≤ 10^9
- 所有輸入皆為整數
範例說明
計算 5^23 除以 10^9+7 的餘數。由於 5^23 = 11920928955078125，所以答案是 871631629。
print(pow(*map(int, input().split()), 10 ** 9+7))
051 - Combination Hard
有一個無限大的格子，每個格子可以用兩個整數 (a, b) 表示。對於所有格子 (a, b)，右邊的格子是 (a+1, b)，上面的格子是 (a, b+1)。
從格子 (0, 0) 出發，每次只能往上或往右移動到相鄰的格子，有多少種方法可以到達格子 (X, Y)？ 答案需要對 1000000007 （一個質數）取餘。
條件
- 1 ≤ X, Y ≤ 105
- 所有的輸入都是整數。
_MAXN = 2 * 10 ** 5 + 10
_MOD = 10 ** 9 + 7
fac = [1] * _MAXN
inv = [1] * _MAXN
for i in range(1, _MAXN):
fac[i] = fac[i - 1] * i % _MOD
inv[i] = pow(fac[i], -1, _MOD)
assert fac[i] * inv[i] % _MOD == 1
x, y = map(int, input().split())
print(fac[x + y] * inv[x] % _MOD * inv[y] % _MOD)
052 - Knight
二維網格上有一枚西洋棋的騎士，位於原點 (0,0)。
騎士可以從格子 (i,j) 僅移動到格子 (i+1,j+2) 或 (i+2, j+1)。
有多少種方法可以將騎士移動到格子 (X,Y)？ 請算出答案對 10^9+7 取模的結果。
限制：
1 ≤ X ≤ 10^6 1 ≤ Y ≤ 10^6 輸入的所有數值皆為整數。
_MAXN = 10 ** 6 + 10
_MOD = 10 ** 9 + 7
fac = [1] * _MAXN
inv = [1] * _MAXN
for i in range(1, _MAXN):
fac[i] = fac[i - 1] * i % _MOD
inv[-1] = pow(fac[-1], -1, _MOD)
for i in range(_MAXN - 2, -1, -1):
inv[i] = inv[i + 1] * (i + 1) % _MOD
assert fac[i] * inv[i] % _MOD == 1
x, y = map(int, input().split())
ans = 0
for i in range(min(x, y // 2) + 1):
rx = x - i
j = ry = y - i * 2
if rx != ry * 2:
continue
ans = (ans + fac[i + j] * inv[i] % _MOD * inv[j]) % _MOD
print(ans)
053 - Sum of 4^N
給定一個正整數 N，請輸出 4^0 + 4^1 + … + 4^N 除以 1,000,000,007 的餘數。
- 1 ≤ N ≤ 10^18
$$\frac{4^{N+1} - 1}{4 - 1}$$
R = 4
N = int(input()) + 1
_MOD = 10 ** 9 + 7
up = pow(R, N, _MOD) - 1
down = R - 1
print(up * pow(down, -1, _MOD) % _MOD)
054 - Fibonacci Hard (mod 1000000000)
給定一個由以下遞迴關係定義的斐波那契數列的第 N 項 a_N，請輸出其除以 10^9 後的餘數。
a_1 = 1, a_2 = 1 a_n = a_{n-1} + a_{n-2} (n ≥ 3)
import numpy as np
_MOD = 10 ** 9
_N = 2
_A = np.matrix([[1, 1], [1, 0]], dtype=np.uint64)
_B = np.matrix([[1], [0]], dtype=np.uint64)
def pow_mod(a, n):
res = np.eye(_N, dtype=np.uint64)
while n > 0:
if n % 2 == 1:
res = res * a % _MOD
a = a * a % _MOD
n //= 2
return res
def fib(n):
return (pow_mod(_A, n) * _B % _MOD)[1, 0]
print(fib(int(input())))
055 - Recurrence Formula 1
給定一個由以下遞迴關係定義的數列，求數列的第 N 項 a_N 除以 1000000007（=10^9+7）的餘數。
- a_1 = 1
- a_2 = 1
- a_n = 2a_{n－1} + a_{n－2} (n ≥ 3)
限制：
- 3 ≤ N ≤ 10^{18}
- N 是一個整數
$$ \begin{bmatrix} a_N \newline a_{N-1} \end{bmatrix} = \begin{bmatrix} 2 & 1 \newline 1 & 0 \end{bmatrix} \begin{bmatrix} a_{N-1} \newline a_{N-2} \end{bmatrix} $$
$$ \begin{bmatrix} a_N \newline a_{N-1} \end{bmatrix} = \begin{bmatrix} 2 & 1 \newline 1 & 0 \end{bmatrix}^{N-2} \begin{bmatrix} a_2 = 1 \newline a_1 = 1 \end{bmatrix} $$
import numpy as np
_MOD = 10 ** 9 + 7
_N = 2
_A = np.matrix([[2, 1], [1, 0]], dtype=np.uint64)
_B = np.matrix([[1], [1]], dtype=np.uint64)
def pow_mod(a, n):
res = np.eye(_N, dtype=np.uint64)
while n > 0:
if n % 2 == 1:
res = res * a % _MOD
a = a * a % _MOD
n //= 2
return res
def f(n):
return (pow_mod(_A, n - 2) * _B % _MOD)[0, 0]
print(f(int(input())))
056 - Recurrence Formula 2
請你求出以下遞迴關係定義的數列的第 N 項 a_N 除以 1000000007 (=10^9+7) 的餘數。
a_1 = 1, a_2 = 1, a_3 = 2 a_n = a_{n－1} + a_{n－2} + a_{n-3} (n ≥ 4)
這個數列 (a_1, a_2, a_3, …) 被稱為三波那契數列。
限制
4 ≤ N ≤ 10^{18} N 是一個整數
$$ \begin{bmatrix} a_N \newline a_{N-1} \newline a_{N-2} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \newline 1 & 0 & 0 \newline 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} a_{N-1} \newline a_{N-2} \newline a_{N-3} \end{bmatrix} \newline $$
$$ \begin{bmatrix} a_N \newline a_{N-1} \newline a_{N-2} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \newline 1 & 0 & 0 \newline 0 & 1 & 0 \end{bmatrix}^{N-3} \begin{bmatrix} a_3 = 2 \newline a_2 = 1 \newline a_1 = 1 \end{bmatrix} \newline $$
import numpy as np
_MOD = 10 ** 9 + 7
_N = 3
_A = np.matrix([[1, 1, 1], [1, 0, 0], [0, 1, 0]], dtype=np.uint64)
_B = np.matrix([[2], [1], [1]], dtype=np.uint64)
def pow_mod(a, n):
res = np.eye(_N, dtype=np.uint64)
while n > 0:
if n % 2 == 1:
res = res * a % _MOD
a = a * a % _MOD
n //= 2
return res
def f(n):
return (pow_mod(_A, n - 3) * _B % _MOD)[0, 0]
print(f(int(input())))
057 - Domino Tiling
給定一個 K × N 的長方形網格，求用 1 × 2 或 2 × 1 的長方形瓷磚完全覆蓋它的方法數，對 1000000007 (=10^9+7) 取模。滿足以下條件的鋪設方式被認為是有效的鋪設方式：
- 瓷磚不能超出網格的範圍，並且不同的瓷磚不能重疊。
- 所有瓷磚都恰好覆蓋網格的 2 個方格。
此外，旋轉或翻轉後一致的鋪設方式也被視為不同的鋪設方式。
限制：
- 2 ≤ K ≤ 4
- 5 ≤ N ≤ 10^{18}
可能出現如下排列
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| A | A | F | F |
| B | D | D | H |
| B | E | E | H |
| C | C | G | G |
狀態應該設計為前一個Column督多少方塊過來，需要維護的狀態數量就變成了$2^K$個。
import numpy as np
_MOD = 10 ** 9 + 7
def pow_mod(a, n):
res = np.eye(*a.shape, dtype=np.uint64)
while n > 0:
if n % 2 == 1:
res = res @ a % _MOD
a = a @ a % _MOD
n //= 2
return res
k, n = map(int, input().split())
m = 1 << k
a = np.zeros((m, m), dtype=np.uint64)
for occupied in range(m):
spaces = [j for j in range(k) if (occupied >> j) & 1]
for vert in range(1 << (k - 1)):
if (vert & 0b11) == 0b11 or (vert & 0b110) == 0b110:
continue
vert |= vert << 1
if vert & occupied:
continue
next = (m - 1) ^ (vert | occupied)
a[occupied][next] += 1
print(pow_mod(a, n)[0, 0])
058 - Move on Squares 1
在一個無限延伸的棋盤上，放置了一個棋子。你將進行「恰好 N 次移動棋子的操作，每次移動棋子到上下左右相鄰的格子」。
設棋子最初放置的格子為 (0, 0)。當棋子向右移動 a 格，向上移動 b 格時，其位置為格子 (a, b)。請你判斷，是否可以通過 N 次移動，將棋子最終移動到格子 (X, Y)。
顯然 $$ N \geq |X| + |Y| $$
觀察奇偶性，顯然 $$ N \equiv |X| + |Y| \mod 2 $$
n, x, y = map(int, input().split())
xy = abs(x) + abs(y)
ans = n >= xy and n % 2 == xy % 2
print("Yes" if ans else "No")
059 - Power of Two
請找出 2 的 N 次方的個位數。
print([6, 2, 4, 8][int(input())%4])
060 - Stones Game 1
有 N 個石頭，兩位玩家輪流拿石頭。每次輪到一位玩家時，他必須拿走至少 1 個，至多 3 個石頭。首先無法拿石頭的玩家輸掉遊戲。給定一個整數 N，判斷在雙方都採取最佳策略的情況下，誰會獲勝。
n = int(input())
print(["First", "Second"][n % 4 == 0])
可以理解為在模4為零的狀態下，無論先手怎麼拿，後手都可以將石頭數量取成模4為零。詳細的數學解析如下：
$$S(0) = \text{Lose} \newline S(1) = \text{Win} \newline S(2) = \text{Win} \newline S(3) = \text{Win} \newline S(N) = \text{Win} \iff \exist {i\in{1,2,3}}, S(N - i) = \text{Lose} $$
061 - Stones Game 2
有 N 個石頭。在每一回合中，假設目前剩餘 a 個石頭，玩家必須拿走至少 1 個，至多 a/2 個石頭 (取整)。第一個無法再拿石頭的玩家輸掉遊戲。請撰寫程式，判斷在雙方都採取最佳策略的情況下，先手玩家和後手玩家誰會獲勝。
- 1 ≤ N ≤ 10^18
- 對於名為 small 的測試案例，額外的限制條件為：1 ≤ N ≤ 10^5
$$S(0) = \text{Lose} \newline S(1) = \text{Lose} \newline S(2) = \text{Win} \newline S(N) = \text{Win} \iff \exist {1 \leq i \leq \lfloor \frac{N}{2} \rfloor}, S(N - i) = \text{Lose} $$
import functools
@functools.cache
def dp(n):
if n <= 1:
return False
return any(not dp(n - i) for i in range(1, n // 2 + 1))
for i in range(100):
if not dp(i):
print(i)
觀察後可發現先手敗的$N$是：0, 1, 3, 7, 15, 31, 63。 可以大膽假設$N+1$是二的冪次則先手必敗。
print(['First', 'Second'][(int(input())+1).bit_count() == 1])
062 - Teleporter
高橋王國有 N 個城鎮。城鎮編號從 1 到 N。 每個城鎮都設置有一台傳送器。城鎮 i (1 ≤ i ≤ N) 的傳送器傳送目的地是城鎮 A_i。
高橋王喜歡正整數 K。任性的高橋王想知道，如果從城鎮 1 出發並使用傳送器恰好 K 次，會到達哪個城鎮。
$2 ≤ N ≤ 2 × 10^5$ $1 ≤ A_i ≤ N$ $1 ≤ K ≤ 10^{18}$
n, k = map(int, input().split())
d = [[] for _ in range(64)]
d[0] = [0] + list(map(int, input().split()))
for i in range(63):
d[i + 1] = [d[i][d[i][x]] for x in range(n + 1)]
p = 1
for i in range(64):
if k & (1 << i):
p = d[i][p]
print(p)
063 - Move on Squares 2
有一個 $N × N$ 的格狀棋盤。
從左上角的格子出發，重複地上下左右移動到相鄰的格子，判斷是否存在一條路徑，使得可以回到出發點，並且路徑（除了起點和終點）恰好只經過每個格子一次。
$2 \leq N \leq 10^9$
print(["No", "Yes"][int(input()) % 2 == 0])
064 - All Zero
給定一個長度為 N 的數列 A = (A₁ , A₂ , …, Aₙ)。 你需要在數列上執行以下操作恰好 K 次：
- 選擇一個介於 1 到 N 之間的整數 x，然後將 Aₓ 增加 1 或減少 1。
判斷是否可以將數列的所有元素都變成零，也就是 (A₁ , A₂ , …, Aₙ) = (0, 0, …, 0)。
n, k = map(int, input().split())
s = sum(abs(x) for x in map(int, input().split()))
print(["No", "Yes"][s % 2 == k % 2 and k >= s])
065 - Bishop
有一個 H 行、W 列的棋盤。在棋盤的左上角放置了一個角行棋子。
這個棋子可以重複移動 0 次或更多次，請問可以到達的棋盤格有多少個？ 角行棋子的移動方式是斜向移動。
更嚴格地說，若棋子從上數第 r₁ 行、左數第 c₁ 列的格子移動到上數第 r₂ 行、左數第 c₂ 列的格子，則需滿足以下條件之一：
- r₁ + c₁ = r₂ + c₂
- r₁ - c₁ = r₂ - c₂
例如，如下圖所示，棋子可以一步移動到紅色的格子。
限制
- 1 ≤ H, W ≤ 10⁹
- 所有輸入都是整數。
h, w = map(int, input().split())
if h == 1 or w == 1:
print(1)
else:
print(h * (w // 2) + (h + 1) // 2 * (w % 2))
066 - Three Cards
有黑色、白色和灰色的卡片各一張。
求有多少種方法，可以在每張卡片上寫上1到N之間的整數，使得滿足以下至少一個條件：
-
黑色卡片和白色卡片上寫的整數的差的絕對值 ≥ K
-
黑色卡片和灰色卡片上寫的整數的差的絕對值 ≥ K
-
灰色卡片和白色卡片上寫的整數的差的絕對值 ≥ K
-
1 ≤ N ≤ 100000
-
1 ≤ K ≤ min(5, N - 1)
n, k = map(int, input().split())
ans = n ** 3
for x in range(n):
w = min(k, n - x)
ans -= 1 # xxx
ans -= (w - 1) * 3 * 2 # xxy, xyy
ans -= (w - 1) * (w - 2) * 3 # xyz
print(ans)
067 - Cross Sum（★2）
有一個 H 行 W 列的網格。位於第 i 行、第 j 列的格子 (i, j) 上寫著一個整數 A_{i, j}。
對於所有格子 (i, j) (1 ≤ i ≤ H, 1 ≤ j ≤ W)，請計算以下值：
將格子 (i, j) 和與其位於同一行或同一列的所有格子上寫的整數加總起來的值。
n, m = map(int, input().split())
r, c = [0] * n, [0] * m
a = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
for j, x in enumerate(a[i]):
r[i] += x
c[j] += x
for i in range(n):
for j in range(m):
print(r[i] + c[j] - a[i][j], end=" ")
print()
068 - Number of Multiples 2
給定一個介於1到N之間的整數，請寫一個程式計算有多少個整數是V₁, V₂, …, Vₖ中至少一個數字的倍數。
限制：
- 1 ≤ N ≤ 10¹²
- 1 ≤ K ≤ 10
- 1 ≤ Vᵢ ≤ 50
所有輸入均為整數。
import itertools
import math
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(1, k + 1):
for s in itertools.combinations(a, i):
tmp = n // math.lcm(*s)
if i % 2 == 0:
ans -= tmp
else:
ans += tmp
print(ans)
069 - Product Max
給定四個整數 a, b, c, d。
對於滿足 a ≤ x ≤ b 且 c ≤ y ≤ d 的整數 x, y，求 x × y 的最大值。
import itertools
a, b, c, d = map(int, input().split())
print(max(x * y for x, y in itertools.product((a, b), (c, d))))
070 - Axis-Parallel Rectangle
在二維座標平面上有 N 個點。第 i 個點的座標是 (x_i, y_i)。
考慮一個長方形，其內部包含 N 個點中的至少 K 個點，並且長方形的邊與 X 軸或 Y 軸平行。在此情境下，長方形邊上的點也被視為包含在長方形內部。
請你找出這些長方形中，面積最小的那個長方形的面積。
限制
- 2 ≤ K ≤ N ≤ 50
- -10^9 ≤ x_i, y_i ≤ 10^9 (1 ≤ i ≤ N)
- x_i ≠ x_j (1 ≤ i < j ≤ N)
- y_i ≠ y_j (1 ≤ i < j ≤ N)
- 所有輸入值都是整數。
import itertools
_INF = 10 ** 20
n, k = map(int, input().split())
points = [tuple(map(int, input().split())) for _ in range(n)]
x_axis = sorted(set(x for x, y in points))
ans = _INF
for l, r in itertools.combinations(x_axis, 2):
ys = [y for x, y in points if l <= x <= r]
if len(ys) < k:
continue
ys.sort()
min_k_cover = min(ys[i] - ys[i - k + 1] for i in range(k - 1, len(ys)))
ans = min(ans, (r - l) * min_k_cover)
print(ans)
071 - Linear Programming
給定一個正整數 N 和 N 組正整數 (a₁, b₁, c₁), (a₂, b₂, c₂), …, (aN, bN, cN)。
請編寫一個程序，找出所有滿足以下條件的實數對 (x, y) 中，x + y 的最大值：
a₁x + b₁y ≤ c₁ a₂x + b₂y ≤ c₂ … aNx + bNy ≤ cN
- 1 ≤ N ≤ 500
- 1 ≤ aᵢ, bᵢ, cᵢ ≤ 10⁹
- 當 x + y 達到最大值時，x 和 y 都是正實數。
- 此限制允許使用 O(N³) 時間複雜度的解法。
直接請Gemini調用Scipy就好了。
import scipy.optimize
def solve_linear_programming(N, constraints):
"""
使用 scipy.optimize.linprog 解決線性規劃問題。
Args:
N: 約束條件的數量。
constraints: 約束條件的列表，每個約束條件都是 (a, b, c) 的元組。
Returns:
x + y 的最大值，如果找到解；否則返回 None。
"""
c = [-1, -1] # 目標函數：最大化 x + y
A_ub = [] # 不等式約束的係數矩陣
b_ub = [] # 不等式約束的右側向量
for a, b, c_val in constraints:
A_ub.append([a, b])
b_ub.append(c_val)
bounds = [(0, None), (0, None)] # x 和 y 都是正數
result = scipy.optimize.linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds)
if result.success:
return -result.fun # 返回 x + y 的最大值
else:
return None # 沒有找到解
# 範例輸入
N = int(input())
constraints = [tuple(map(int, input().split())) for _ in range(N)]
# 解決問題
max_value = solve_linear_programming(N, constraints)
print(max_value)
072 - Max GCD 2
給定兩個整數 A 和 B。請找出在選擇整數 x 和 y，使得 A ≤ x < y ≤ B 時，gcd(x, y) 的最大值。
$1 ≤ A < B ≤ 2 × 10^5$
a, b = map(int, input().split())
ans = 1
for i in range(1, b - a + 1):
y = b // i * i
x = y - i
if a <= x < y <= b:
ans = i
print(ans)
073 - Sum of Maximum
有 N 個整數 A_1, A_2, …, A_N，從中選擇至少一個數的方法有 2^N - 1 種。
對於每種選擇，計算「所選整數的最大值」。
求所有這些最大值的總和，並輸出結果對 1000000007 取模後的餘數。
- 1 ≤ N ≤ 300000
- 1 ≤ A_1 < A_2 < … < A_N ≤ 10^9
_MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
print(sum(pow(2, i, _MOD) * a[i] for i in range(n)) % _MOD)
074 - Sum of difference Easy
有 N 個整數 A_1, A_2, …, A_N。這裡滿足 A_1 < A_2 < … < A_N。
請計算 $\displaystyle \sum_{i=1}^{N} \sum_{j=i+1}^{N} (A_j-A_i)$ 的值。
- 2 ≤ N ≤ 200000
- 1 ≤ A_1 < A_2 < … < A_N ≤ 10^6
n = int(input())
a = list(map(int, input().split()))
s, ans = 0, 0
for i, x in enumerate(a):
ans += x * i - s
s += x
print(ans)
075 - Pyramid
給你一個 N 層的金字塔，最底層由左至右寫著整數 A_1, A_2, \dots, A_N。
從底層往上，執行「將相鄰的兩個數相加，答案寫在上一層」的操作。請問，最頂層寫的整數是多少？
請輸出答案除以 1000000007 (=10^9+7) 的餘數。
條件：
- 2 ≤ N ≤ 200000
- 1 ≤ A_i ≤ 10^9
- 所有輸入皆為整數
_MAXN = 200010
_MOD = 10 ** 9 + 7
fac = [1] * _MAXN
ifac = [1] * _MAXN
for i in range(1, _MAXN):
fac[i] = fac[i - 1] * i % _MOD
ifac[-1] = pow(fac[-1], -1, _MOD)
for i in range(_MAXN - 2, -1, -1):
ifac[i] = ifac[i + 1] * (i + 1) % _MOD
for i in range(1, _MAXN):
assert (fac[i] * ifac[i]) % _MOD == 1
def C(n, m):
if n < m:
return 0
return fac[n] * ifac[m] % _MOD * ifac[n - m] % _MOD
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
ans = (ans + C(n - 1, i) * a[i]) % _MOD
print(ans)
076 - Sum of difference
計算 $$\displaystyle{\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |A_i-A_j|}$$
n = int(input())
a = sorted(list(map(int, input().split())))
s, ans = 0, 0
for i, x in enumerate(a):
ans += x * i - s
s += x
print(ans)
077 - Distance Sum
在二維座標平面上，有 N 個點。第 i 個點的座標是 $(X_i, Y_i)$。
定義 $\mathcal{dist} (i, j)$ 為第 i 個點和第 j 個點之間的曼哈頓距離。
曼哈頓距離定義為：座標 $(x_1 , y_1)$ 和座標 $(x_2, y_2)$ 之間的曼哈頓距離是:$$|x_1 − x_2| + |y_1 − y_2|$$
請編寫一個程序來計算以下公式的值：
$$\sum_{i=1}^{N} \sum_{j=i+1}^{N} \mathcal{dist} (i,j)$$
條件
- 2 ≤ N ≤ 200000
- -10^5 ≤ X_i , Y_i ≤ 10^5
- X_i, Y_i 是整數
維度是獨立的，因此本質跟一維解法一樣。
def f(a):
a.sort()
s, ans = 0, 0
for i, x in enumerate(a):
ans += x * i - s
s += x
return ans
n = int(input())
p = [tuple(map(int, input().split())) for _ in range(n)]
print(f([x[0] for x in p]) + f([x[1] for x in p]))
078 - Difference Optimization 1
ALGO 家有 N 位家庭成員，每個人都有一個從 1 到 N 的編號。已知 1 號成員的年齡是 0 歲，其他人的年齡都是 0 到 120 歲之間的整數。此外，滿足以下 M 個條件：
- 成員 A₁ 和成員 B₁ 的年齡差是 0 歲或 1 歲。
- 成員 A₂ 和成員 B₂ 的年齡差是 0 歲或 1 歲。
- …
- 成員 Aₘ 和成員 Bₘ 的年齡差是 0 歲或 1 歲。
請輸出每個成員可能的最大年齡。
條件
- 2 ≤ N ≤ 100000
- 1 ≤ M ≤ 500000
- 1 ≤ Aᵢ < Bᵢ ≤ N
- 所有輸入皆為整數
裸BFS。
from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
d = [120] * (n + 1)
d[1] = 0
q = deque([1])
while q:
x = q.popleft()
for y in g[x]:
if d[y] == 120:
d[y] = d[x] + 1
q.append(y)
for i in range(1, n + 1):
print(d[i])
079 - ModSum
對於一個整數 N，我們選取 ${1, 2, …, N}$ 的一個排列 ${P_1, P_2, …, P_N}$。
然後，對於每個 i=1,2,…,N，我們計算 i 除以 P_i 的餘數，記為 M_i。
請你求出 M_1 + M_2 + … + M_N 的最大值。
$$\max_{P} \sum_{i=1}^N i \mod P_i$$
n = int(input())
print(n * (n - 1) // 2)
080 - Difference Optimization 2
給定整數 $x_1, x_2, \dots, x_N$ 滿足以下所有條件：
- $x_1 = 0$
- 對於 $1 \le i \le M$ ，滿足 $|x_{A_i} - x_{B_i}| \le C_i$
請編寫一個程式，以找出 $x_N$ 的可能最大值。
限制：
- $2 \le N \le 100000$
- $0 \le M \le 500000$
- $1 \le A_i < B_i \le N$
- $0 \le C_i \le 10^9$
- 所有輸入皆為整數
如果可以將 $x_N$ 設為任意大的值，輸出 -1。否則，輸出 $x_N$ 的最大值。
Dijkstra
import heapq
_INF = 10 ** 18
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
u, v, w = map(int, input().split())
g[u].append((v, w))
g[v].append((u, w))
d = [_INF] * (n + 1)
d[1] = 0
q = [(d[1], 1)]
while q:
dist, node = heapq.heappop(q)
if dist > d[node]:
continue
for v, w in g[node]:
if d[v] > d[node] + w:
d[v] = d[node] + w
heapq.heappush(q, (d[v], v))
print(d[n] if d[n] != _INF else -1)
081 - Bill Changing Problem
你用 1000 元、5000 元和 10000 元的紙鈔來支付 N 元。請找出用最少幾張紙鈔就能支付 N 元。
- 你可以假設每種面額的紙鈔都有足夠的數量。
- 1000 ≤ N ≤ 200000
- N 是 1000 的倍數
n = int(input())
ans = 0
for x in [10000, 5000, 1000]:
ans += n // x
n %= x
print(ans)
082 - Interval Scheduling Problem
今天有 N 部電影上映。第 i 部電影在時刻 L_i 開始，在時刻 R_i 結束。
請問最多可以完整看完幾部電影？
可以看完一部電影後立刻接著看下一部，但不能同時看多部電影。
限制
- 1 ≤ N ≤ 300000
- 0 ≤ L_i < R_i ≤ 86400
- 所有輸入皆為整數
子任務
- 對於滿足 N ≤ 2000 的測試案例，若答案正確，可獲得 500 分。
n = int(input())
movies = [tuple(map(int, input().split())) for _ in range(n)]
movies.sort(key=lambda x: x[1])
end = 0
ans = 0
for l, r in movies:
if l >= end:
end = r
ans += 1
print(ans)
083 - We Used to Sing a Song Together（★3）
問題：
AGC 街道上有 N 個小學生，小學生 i（1 ≤ i ≤ N）的家位於位置 Aᵢ。 也有 N 所小學，小學 j（1 ≤ j ≤ N）位於位置 Bⱼ。
AGC 街道上的小學生性格不好，彼此關係惡劣，所以希望所有人都去不同的學校上學。
不便度定義如下： 設小學生 i 的家到學校的距離為 Eᵢ，則不便度是距離的總和，即 E₁ + E₂ + … + Eₙ。
位置 u 到位置 v 的距離為 |u - v|。
在每個學生都上不同的學校的條件下，求不便度的最小值。
限制：
- 1 ≤ N ≤ 100000
- 0 ≤ Aᵢ ≤ 10⁹
- 0 ≤ Bⱼ ≤ 10⁹
- A₁, A₂, …, Aₙ 彼此不同
- B₁, B₂, …, Bₙ 彼此不同
- 所有輸入都是整數
n = int(input())
f = lambda : sorted(list(map(int, input().split())))
print(sum(abs(x - y) for x, y in zip(f(), f())))
084 - Sqrt Inequality
$\sqrt{a} + \sqrt{b} < \sqrt{c}$ 嗎？
- 1 ≤ a, b, c ≤ 10^9
- 輸入皆為整數。
$a + b + 2 \sqrt{ab} < c$ $2 \sqrt{ab} < c - a - b$
a, b, c = map(int, input().split())
ans = c - a - b >= 0 and 4 * a * b < (c - a - b) ** 2
print(["No", "Yes"][ans])
085 - Two Conditions
給定整數 N、X 和 Y，判斷是否存在一組由 1 到 N 之間的整數 (a, b, c, d)，同時滿足以下兩個條件：
- a + b + c + d = X
- a * b * c * d = Y
條件：
- 1 ≤ N ≤ 300
- 1 ≤ X ≤ 109
- 1 ≤ Y ≤ 109
import itertools
n, x, y = map(int, input().split())
s = set()
for a, b in itertools.product(range(1, n+1), repeat=2):
s.add((a + b, a * b))
if a + b <= x and y % (a * b) == 0:
c, d = x - (a + b), y // (a * b)
if (c, d) in s:
print('Yes')
break
else:
print('No')
086 - Parentheses Check
給定一個長度為 N 的由 “(” 和 “)” 組成的括號序列 S，判斷 S 是否為一個合法的括號序列。
input()
st = 0
for c in input():
if c == '(':
st += 1
else:
st -= 1
if st < 0:
print("No")
break
else:
print("Yes" if st == 0 else "No")
087 - Simple Math Easy
給定一個整數 N。
$$\sum_{i=1}^N\sum_{j=1}^N i\times j$$
然後將結果對 1000000007 (=10^9+7) 取餘。
1 ≤ N ≤ 10^9
n = int(input())
print((n * (n + 1) // 2) ** 2 % 1000000007)
088 - Simple Math
給定三個正整數 A、B 和 C。
$$\sum_{a=1}^A\sum_{b=1}^B\sum_{c=1}^C a\times b\times c$$
結果除以 998244353 後的餘數。
$1 ≤ A, B, C ≤ 10^9$
a, b, c = map(int, input().split())
f = lambda x: x * (x + 1) // 2
print(f(a) * f(b) * f(c) % 998244353)
089 - Log Inequality 2
判斷以下是否成立： $$\log_2 a < b \log_2 c$$
- 1 ≤ a ≤ 10¹⁸
- 1 ≤ b ≤ 10¹⁸
- 1 ≤ c ≤ 10¹⁸
import math
a, b, c = map(int, input().split())
if b * math.log2(c) >= 64 or a < c ** b:
print("Yes")
else:
print("No")
090 - Digit Product Equation（★7）
定義函數 f(x) 如下： f(x) = (x 的各個位數數字的乘積) 例如 f(777) = 343，f(8691) = 432，f(869120) = 0。
給定整數 N 和 B，請找出 1 到 N 之間的整數 m，使得 $m - f(m) = B$ 的 m 的個數。
$1 ≤ N < 10^{11}$ $1 ≤ B < 10^{11}$
091 - How Many Ways?
請找出滿足以下所有條件的整數三元組 (a, b, c) 的數量：
- 1 ≤ a < b < c ≤ N
- a + b + c = X
$3 \leq N \leq 100$ $0 \leq X \leq 300$
import itertools
n, x = map(int, input().split())
print(sum(
sum(p) == x
for p in itertools.combinations(range(1, n + 1), 3)
))
092 - Beautiful Rectangle
給定一個面積為N的長方形，其長和寬皆為整數。請找出這個長方形的最小周長。
$1 \leq N \leq 10^{12}$
import math
n = int(input())
ans = n * 2 + 2
for i in range(2, math.isqrt(n) + 1):
if n % i == 0:
ans = min(ans, 2 * (n // i + i))
print(ans)
093 - Large LCM（★3）
給定兩個正整數 A 和 B。請找出 A 和 B 的最小公倍數。如果答案超過 10^18，則輸出 Large。
$$ 1 \leq A, B \leq 10^{18} $$
import math
a, b = map(int, input().split())
lcm = math.lcm(a, b)
if lcm > 10**18:
print("Large")
else:
print(lcm)
094 - Maximal Value
有一個長度為 N 的整數數列 A，其值未知。給定一個長度為 N-1 的整數數列 B。 已知對所有 i， $B_i ≥ \max(A_i, A_{i+1})$ 都成立。請找出 A 的元素總和可能的最大值。
- $2 \leq N \leq 100$
- $0 \leq B_i \leq 10^5$
$$A_i \leq \min(B_i, B_{i-1})$$
從大到小給值就可以了。
_INF = 10 ** 9
n = int(input())
b = sorted([(x, i) for i, x in enumerate(map(int, input().split()))], reverse=True)
a = [_INF] * n
for x, i in b:
a[i] = a[i+1] = x
print(sum(a))
095 - Score Sum Queries（★2）
ABC 大學有 N 個一年級學生。班級分為 2 個，學號為 i 的學生的班級是 C_i 班。今天期末考試發回來了，學號為 i 的學生的分數是 P_i 分。
現在有 Q 個查詢，格式如下。 對於每個 j = 1, 2, …, Q：
- 計算學號 L_j ~ R_j 範圍內 1 班學生的期末考試總分。
- 計算學號 L_j ~ R_j 範圍內 2 班學生的期末考試總分。
分別求出這兩個值。
限制
- 1 ≤ N ≤ 100000
- 1 ≤ C_i ≤ 2
- 0 ≤ P_i ≤ 100
- 1 ≤ Q ≤ 100000
- 1 ≤ L_j ≤ R_j ≤ N
輸入
輸入包含所有整數。
輸出
輸出格式如下，其中 A_j 是學號 L_j ~ R_j 範圍內 1 班學生的期末考試總分，B_j 是學號 L_j ~ R_j 範圍內 2 班學生的期末考試總分：
A_1 B_1 A_2 B_2 … A_Q B_Q
096 - Cooking
高橋要製作從料理 1 到料理 N 的 N 道料理。
料理 i 需要使用烤箱連續 T_i 分鐘才能完成。
一台烤箱不能同時給兩道或以上的料理使用。
當可以使用兩台烤箱時，製作所有 N 道料理所需的最短時間是多久？ 請注意，可以忽略使用烤箱以外的時間。
限制
- 1 ≤ N ≤ 100
- 1 ≤ T_i ≤ 10^3
輸入
- 輸入皆為整數。
即要把數字分成兩堆，兩堆的和要儘量相同。
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
dp = [False] * (s + 1)
dp[0] = True
ans = s
for x in a:
for i in range(s, x - 1, -1):
dp[i] |= dp[i - x]
if dp[i]:
ans = min(ans, max(i, s - i))
print(ans)
bit流：
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
dp = 1
for x in a:
dp |= dp << x
ans = s
for i in range(s):
if (dp >> i) & 1:
ans = min(ans, max(i, s - i))
print(ans)
097 - Primes in an Interval
問題：計算在 L 到 R 之間（包含 L 和 R）的素數個數。注意 1 不是素數。
限制：
- 1 ≤ L ≤ R ≤ 10^12
- R - L ≤ 500000
_N = 10 ** 6 + 1
is_prime = [True] * _N
is_prime[0] = is_prime[1] = False
primes = []
for i in range(2, _N):
if is_prime[i]:
primes.append(i)
for j in range(i * i, _N, i):
is_prime[j] = False
l, r = map(int, input().split())
is_prime_large = [True] * (r - l + 1)
if l == 1:
is_prime_large[0] = False
for p in primes:
m = max(2, (l + p - 1) // p)
for i in range(m * p, r + 1, p):
is_prime_large[i - l] = False
print(sum(is_prime_large))
098 - Polygon and Point
問題敘述
給定一個有 N 個頂點的多邊形。點 P_i 的坐標為 (X_i, Y_i)，連接 P_i 和 P_{i+1} 的線段 (i = 1, 2, …, N-1) 是多邊形的邊。另外，連接 P_N 和 P_1 的線段也是多邊形的邊。
编写一个程序來判斷坐標 (A, B) 是否包含在多邊形的內部。
限制
- $3 ≤ N ≤ 100000$
- $10^9 ≤ X_i ≤ 10^9$
- $10^9 ≤ Y_i ≤ 10^9$
- $10^9 ≤ A ≤ 10^9$
- $10^9 ≤ B ≤ 10^9$
- 點 (A, B) 不在多邊形的任何一條邊上。
- 多邊形的內角不會恰好為 180°。
- 所有輸入皆為整數。
部分分數
如果您的程序對於多邊形是凸多邊形的所有情況都正確，則可以獲得 500 分。
099 - Tree Distance（★5）
給定一個有 N 個節點的樹。樹的節點分別標記為 1 到 N。第 i 條邊連接了節點 a_i 和節點 b_i，且長度都為 1。
請計算 $\displaystyle \sum_{u=1}^{N-1} \sum_{v=u+1}^{N} dist(u, v)$ 的值。
其中 dist(u, v) 表示從節點 u 到節點 v 的最短距離。
- 2 ≤ N ≤ 100000
- 1 ≤ a_i, b_i ≤ N
- 給定的圖是一棵樹。
- 輸入的所有值都是整數。
即計算每條邊會被走幾次：兩側聯通塊大小乘起來。
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
ans = 0
def dfs(u, p):
size = 1
for v in g[u]:
if v != p:
size += dfs(v, u)
global ans
ans += size * (n - size)
return size
dfs(1, 0)
print(ans)
100 - Simulation of Chemicals
對於 i = 1, 2, …, Q，請解決以下問題。
試管中分別有 a, b, c 克的三種物質 A, B, C，在接下來的 1 秒內，會發生以下變化：
- 物質 A 中有 aXᵢ 克變成物質 C。
- 物質 B 中有 bYᵢ 克變成物質 A。
- 物質 C 中有 cZᵢ 克變成物質 B。
也就是說，1 秒後，物質 A, B, C 的量分別為 a(1-Xᵢ) + bYᵢ, b(1-Yᵢ) + cZᵢ, c(1-Zᵢ) + aXᵢ 克。
最初，試管中物質 A, B, C 的量分別為 1 克。請編寫程式，求出 Tᵢ 秒後物質 A, B, C 的量。
限制：
- 1 ≤ Q ≤ 10⁴
- 0 ≤ Xᵢ, Yᵢ, Zᵢ ≤ 1
- 1 ≤ Tᵢ ≤ 10⁷
- X, Y, Z 為實數，最多到小數點後 7 位。
- T 為整數
$$ \begin{bmatrix} A’ \newline B’ \newline C’ \end{bmatrix} = \begin{bmatrix} 1-X & Y & 0 \newline 0 & 1-Y & Z \newline X & 0 & 1-Z \end{bmatrix} \begin{bmatrix} A \newline B \newline C \end{bmatrix} \newline $$
import numpy as np
for _ in range(int(input())):
qs = input().split()
x, y, z = map(float, qs[:3])
t = int(qs[3])
a = np.matrix([[1-x,y,0],[0,1-y,z],[x,0,1-z]])
ans = a**t * np.matrix([[1],[1],[1]])
print(ans[0,0], ans[1,0], ans[2,0])
101 - Don’t be too close（★6）
你有 N 個球，每個球上寫著從 1 到 N 的整數。對於 k = 1, 2, 3, …, N，回答以下問題：
從這 N 個球中選擇至少一個球的方法有 2^N - 1 種，其中有多少種選擇滿足以下條件：
對於任何兩個被選中的球，它們上面寫的整數之差都至少為 k。
注意：答案可能非常大，所以請輸出答案對 10^9 + 7 取模的結果。
約束條件：
1 ≤ N ≤ 10^5 N 是一個整數
102 - Tricolor Pyramid
有 N 個方塊排成一列，每個方塊塗成藍、白、紅三種顏色之一。
從這個狀態開始，將方塊堆疊起來，形成一個 N 層的金字塔。
金字塔的堆疊方式如下：
- 每次從底部開始堆疊一個方塊。
- 如果正下方兩個方塊的顏色相同，則堆疊相同顏色的方塊。
- 如果正下方兩個方塊的顏色不同，則堆疊與這兩個顏色都不同的方塊。
請問，金字塔最頂端方塊是什麼顏色？
條件
- N 是一個滿足 2 ≤ N ≤ 400000 的整數。
- c_1, c_2, …, c_N 分別是 B, W, R 之一，分別代表藍色、白色、紅色。
103 - Circle Packing
找到一種方法，在一個中心位於 (0, 0)，半徑為 1 的圓內，鋪設 100 個半徑相等的圓，使得這些圓的半徑盡可能大。這是一個尚未解決的難題，即使在 21 世紀也一直在被挑戰。
條件：
-
對於每一個 i (1 ≤ i ≤ 100)，圓心坐標 (xᵢ, yᵢ) 必須滿足 √((xᵢ)² + (yᵢ)²) < 1。
-
如果您的輸出格式與指定的格式不符（包括使用指數表示法），則會被判斷為錯誤（WA）。
-
得分取決於圓的半徑 R。
-
得分基於 R 的 9 個基準點，得分會根據 R 呈線性增加（折線圖）：
- R = 0.00 時，得分 = 0
- R = 0.07 時，得分 = 350
- R = 0.08 時，得分 = 750
- R = 0.085 時，得分 = 1250
- R = 0.088 時，得分 = 1700
- R = 0.089 時，得分 = 2000
- R = 0.0895 時，得分 = 2700
- R = 0.0900 時，得分 = 4000
- R = 0.090235 時，得分 = 8700
-
當 R > 0.090235 時，每增加 10⁻⁹，得分增加 1 分。
-
得分將四捨五入為最接近的整數。
104 - Graph Master
請建構一個滿足所有以下條件的無向無權重圖：
- 沒有多重邊或自環。
- 所有節點的度數都小於等於4。
- 所有兩個節點之間的最短路徑長度小於等於4。
節點數量越多，分數越高。