Codeforces Round #313 A. Currency System in Geraldion：最小不可組成金額

題目大意

給定 n 種銀行券面值 a_1..a_n（各不相同），每種可用無限張。若某正整數無法用這些面值組合表示，稱為「不幸運數」。求最小的不幸運數；若所有正整數皆可組成，輸出 -1。

關鍵觀察

若面值中包含 1，則任意正整數均可組成（用 1 湊），答案為 -1。否則，最小面值 min_a > 1，則 1 無法組成，答案為 1。因此，答案就是：若存在面值 1 則 -1，否則 1。

證明

• 若 1 ∈ A：對任意 k ≥ 1，用 k 張 1 元組成。
• 若 1 ∉ A：最小面值 ≥ 2，故金額 1 無法組成，且為最小正整數。

代碼實現

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        bool hasOne = false;
        for (int i = 0; i < n; i++) {
            int x; scanf("%d", &x);
            if (x == 1) hasOne = true;
        }
        if (hasOne) printf("-1\n");
        else printf("1\n");
    }
    return 0;
}

複雜度

時間 O(n)，空間 O(1)。極簡題目，核心在於洞察「1 是萬能面值」。