ZeroJudge D123: B2-Sequence

同題:UVa 11063 – B2-Sequence

所謂「B2 數列」係指一正整數數列 1 <= B1 < B2 < B3 …,其中所有的 Bi + Bj (i <= j) 皆不相等。

您的任務是判別某一數列是否為「B2 數列」

範例測資

範例輸入範例輸出
EOF 輸入,每筆測試資料有兩行,第一行代表該數列有 N 個數值(2 ≤ N ≤ 100),第二行則為該數列的 N 個數值。每個數值 Bi 皆為整數,且 Bi ≤ 10000。每筆測試資料以一行輸出,且每筆輸出資料後均需輸出一空白行。
4
1 2 4 8
4
3 7 10 14
5
13 14 15 16 17
Case #1: It is a B2-Sequence.

Case #2: It is not a B2-Sequence.

Case #3: It is not a B2-Sequence.

解題思路

使用兩個 For迴圈 將所有組合的任意兩數相加,需要注意的是「第二個裡面的迴圈 j 要等於 i」,要避免往回加的情況。舉例1+2等於2+1,因為要用Map來確認任意兩數的和出現過幾次,且這樣子其實只有算一次的情況,所以不能往回加。

如果有任意兩數的和已經出現過的情況,可以直接Break迴圈並輸出答案。

Case的部分可以在EOF外面宣告一個變數每次進來While迴圈做+1即可。

範例程式碼-ZeroJudge D123: B2-Sequence

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, count = 1;
    while (cin >> N)
    {
        vector<int>num;
        map<int, int>MAP;
        for (int i = 0; i<N; i++)
        {
            int tmp;
            cin >> tmp;
            num.push_back(tmp);
        }
        bool stop = false;
        for (int i = 0; i<N; i++)
        {
            for (int j = i; j<N; j++)
            {
                if (MAP[num[i]+num[j]] != 0)
                {
                    stop = true;
                    break;
                }
                MAP[num[i]+num[j]]++;
            }
            if (stop) break;
        }
        if (stop) cout << "Case #" << count << ": It is not a B2-Sequence.\n";
        else cout << "Case #" << count << ": It is a B2-Sequence.\n";
        count++;
    }
}

//ZeroJudge D123
//Dr. SeanXD

發佈留言