2011-10-02 09:14:24Morris
a251. 假費波那契數
a251. 假費波那契數
/**********************************************************************************/
/* Problem: a251 "假費波那契數" from 成功高中校內賽初賽 第一題 */
/* Language: C (394 Bytes) */
/* Result: AC(2ms, 246KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-02 07:07:09 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int cmp(const void *i, const void *j) {
return *(int *)i - *(int *)j;
}
int main() {
int T, S[21], i, n;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(i = 1; i <= 4; i++)
scanf("%d", &S[i]);
for(i = 5; i <= n; i++)
S[i] = S[i-4] + S[i-1];
qsort(S+1, n, sizeof(int), cmp);
printf("%d\n", S[n/2+1]);
}
return 0;
}
內容 ：
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
提示
：
出處
：
成功高中校內賽初賽 第一題
(管理：david942j)
/**********************************************************************************/
/* Problem: a251 "假費波那契數" from 成功高中校內賽初賽 第一題 */
/* Language: C (394 Bytes) */
/* Result: AC(2ms, 246KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-02 07:07:09 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int cmp(const void *i, const void *j) {
return *(int *)i - *(int *)j;
}
int main() {
int T, S[21], i, n;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(i = 1; i <= 4; i++)
scanf("%d", &S[i]);
for(i = 5; i <= n; i++)
S[i] = S[i-4] + S[i-1];
qsort(S+1, n, sizeof(int), cmp);
printf("%d\n", S[n/2+1]);
}
return 0;
}