Mr. X 發明了一種新的方法來製造數列，他把它叫做「假費波那契數」，因為他製造數列的方法和費波那契數非常相似。Mr. X 的數列由 4 個初始數字開始 (S1, S2, S3, S4 <=5)，對於數字Si (i > 4) 定義為：Si = Si-4 + Si-1 :
對於一個奇數 N，Mr. X 希望產生 N 個假費波那契數，而 Mr. X 總是想知道這 N 個數的中位數是多少。舉例來說 S1 = 3, S2 = 2, S3 = 4, S4 = 1，而N = 7，則數列為：
3, 2, 4, 1, 4, 6, 10
排序後為：
1, 2, 3, 4, 4, 6, 10
所以中位數字是4.
對於給定的初始數字及 N，請輸出 Mr. X 想要知道的數
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 每個測資檔第一個數字 T 代表接下來有幾組測資。 每筆測資有五個數字 N、S1、S2、S3、S4，測資保證 N (5 <= N < 20) 為奇數且 0 <= S1, S2, S3, S4 <= 5，所有數字皆為整數。 | 對每筆測資輸出一行，代表 Mr. X 想要知道的數字。 |
| 2 5 3 2 4 1 7 3 2 4 1 | 3 4 |
解題思路
將資料輸入並運算至數列長度為 N 之後進行排序並輸出陣列中第 N/2 的位置。
範例程式碼－ZeroJudge A251: 假費波那契數
#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