Mr. X has invented a new method for generating sequences, which he calls "Pseudo-Fibonacci sequence" because his method is very similar to the Fibonacci sequence. The sequence starts with four initial numbers (S1, S2, S3, S4 <=5). For any number Si (i > 4), it is defined as: Si = Si-4 + Si-1.
For an odd number N, Mr. X wants to generate N pseudo-Fibonacci numbers, and he always wants to know what the median of these N numbers is. For example, if S1 = 3, S2 = 2, S3 = 4, S4 = 1, and N = 7, then the sequence is:
3, 2, 4, 1, 4, 6, 10
After sorting:
1, 2, 3, 4, 4, 6, 10
So, the median number is 4.
For the given initial numbers and N, please output the number Mr. X wants to know.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first number T in each test case file indicates how many sets of test data are present. Each test case consists of five numbers: N, S1, S2, S3, S4. The test data guarantees that N (5 <= N < 20) is odd and 0 <= S1, S2, S3, S4 <= 5. All numbers are integers. | For each test case, output one line representing the number Mr. X wants to know. |
| 2 5 3 2 4 1 7 3 2 4 1 | 3 4 |
Thought Process
Input the data and perform calculations until the length of the sequence is N. Then, sort the sequence and output the number at position N/2 in the array.
Sample Code－ZeroJudge A251: Fake Fibonacci
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for (int i = 0; i<T; i++)
{
int N;
cin >> N;
vector<int>num;
for (int j = 0; j<4; j++)
{
int tmp;
cin >> tmp;
num.push_back(tmp);
}
for (int j = 4; j<N; j++)
{
int tmp = num[j-4] + num[j-1];
num.push_back(tmp);
}
sort(num.begin(), num.end());
cout << num[N/2] << "\n";
}
}
//ZeroJudge A251
//Dr. SeanXD