Codeforces Round #273 (Div. 2) 完整題解：A-D 四題詳解

A. Initial Bet - 簡單數學

5 人各押 b 枚硬幣，之後只傳遞硬幣 (總數不變)。給定最終硬幣數 c1..c5，求 b 或判斷無解 (-1)。

解：sum = c1+...+c5。若 sum == 0 或 sum % 5 != 0 輸出 -1，否則 b = sum / 5。
sum==0 時 b=0 但題目要求 b 為正整數，故特判 -1。

B. Random Teams - 貪心數學

n 人分 m 組 (每組 ≥1)，組內兩兩成為朋友。求最小/最大朋友對數。

• 最大值：盡量集中，n-m+1 人一組，其餘 m-1 組各 1 人。
  kmax = C(n-m+1, 2) = (n-m+1)(n-m)/2。
• 最小值：盡量均勻。q = n/m, r = n%m。
  r 組 q+1 人，m-r 組 q 人。
  kmin = r*C(q+1,2) + (m-r)*C(q,2)。

注意 n,m ≤ 1e9，用 long long。

C. Table Decorations - 貪心/數學

r,g,b 三色氣球，每桌恰 3 個且不全同色。求最多桌數。

解：排序 a[0] ≤ a[1] ≤ a[2]。
若 a[0] + a[1] ≤ a[2]/2 (最小兩色總和 ≤ 最大色一半)，則最大色永遠多餘，答案 = a[0] + a[1]。
否則三色可均衡消耗，答案 = (a[0]+a[1]+a[2]) / 3 (整除)。

D. Red-Green Towers - DP (同 CF 478D)

r,g 紅綠方塊，搭最高塔 (第 i 層 i 塊，同層同色)。求最高塔高度 h 及方案數模 1e9+7。

解：
1. 算 h：最大滿足 h(h+1)/2 ≤ r+g。
2. DP：dp[j] = 用 j 紅方塊的方案數 (滾動陣列)。
初始 dp[0]=1。
枚舉層數 i=1..h，倒序 j=r..0：
if (j>=i) dp[j] = (dp[j] + dp[j-i]) % MOD (選紅)。
(選綠隱含在不更新 dp[j]，但需確保綠夠用：最後累加時只加滿足 j ≥ h(h+1)/2 - g 的 dp[j])。
3. 答案 = ∑_{j=min_r..r} dp[j] % MOD。

代碼片段 (D 題核心)

int dp[MAXR] = {1};
for (int i = 1; i <= h; ++i)
    for (int j = r; j >= i; --j)
        dp[j] = (dp[j] + dp[j-i]) % MOD;
int min_r = max(0, h*(h+1)/2 - g);
int ans = 0;
for (int j = min_r; j <= r; ++j) ans = (ans + dp[j]) % MOD;