同題: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