UVa 11063 – B2-Sequence
The term "B2 sequence" refers to a sequence of positive integers where 1 ≤ B1 <B2 <B3 …, and for all Bi +Bj (where i ≤ j), the sums are all distinct.
Your task is to determine whether a given sequence is a "B2 sequence."
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| EOF input. Each test case consists of two lines: the first line represents the number of values N in the sequence (2 ≤ N ≤ 100), and the second line contains the N values of the sequence. Each value Bi is an integer, and Bi ≤ 10000. | Each test case should be followed by one line of output, and a blank line should be output after each set of output data. |
| 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. |
Thought Process
Use two nested For loops to add any two numbers from all combinations. It's important that the second loop (inner loop) starts from i to avoid adding numbers in reverse order. For example, 1+2 is the same as 2+1. We'll use a Map to keep track of how many times each sum appears, ensuring that each combination is counted only once. So, we avoid adding numbers in reverse order.
If the sum of any two numbers has already appeared, you can directly break out of the loop and output the answer.
You can declare a variable outside the EOF loop to count the cases. Increase this variable by 1 each time you enter the While loop.
Sample Code－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