URAL 2011 Long Statement：組合計數判斷能否構成 ≥6 個不同單詞

題目大意

有 n (≤100) 個字母片段，每個是 'a'/'b'/'c'（用 1/2/3 表示）。能否用這些字母拼出至少 6 個長度為 n 的不同單詞？

數學分析：避開大數階乘

總排列數 = n! / (cnt1! cnt2! cnt3!)。100! 極大不可直接算。改用情況分類直接判斷是否 ≥ 6。

分類條件（經驗結論）

• n = 3：必須三字母各至少 1 個（1,1,1）→ 6 種排列。
• n = 4,5：三字母全出現，或存在兩種字母計數 ≥ 2。
• n ≥ 6：至少有兩種不同字母出現即可（排列數 ≥ C(n,2) ≥ 15 > 6）。
• 其餘情況：No。

AC 代碼（C++）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    while (cin >> n) {
        int cnt1=0, cnt2=0, x;
        for (int i=0;i>x; if(x==1)cnt1++; else if(x==2)cnt2++;}
        int cnt3 = n - cnt1 - cnt2;
        bool ok = false;
        if (n == 3) ok = (cnt1 && cnt2 && cnt3);
        else if (n == 4 || n == 5) ok = (cnt1 && cnt2 && cnt3) || (cnt1>=2) + (cnt2>=2) + (cnt3>=2) >= 2;
        else if (n >= 6) ok = (cnt1>0) + (cnt2>0) + (cnt3>0) >= 2;
        cout << (ok ? "Yes" : "No") << '\n';
    }
    return 0;
}

關鍵點

1. 不計算具體排列數，直接用組合條件判斷 ≥ 6。
2. 邊界 n=3,4,5 需單獨處理，n≥6 規律統一。
3. 題目保證輸入合法，無需異常處理。