ZeroJudge A251: 假費波那契數

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
標籤

相關文章

發佈留言