Mr. X invented a new way to create a sequence of numbers which he called “Fake Fibonacci numbers” because the rule to create the sequence is very similar to the rule for Fibonacci numbers. Mr. X’s sequence starts with some four initial numbers S1, S2, S3, and S4 (1 ≤ S1, S2, S3, S4≤ 5).
A number Si (i > 4) in the sequence is the sum of Si-4 and Si-1:
Si = Si-4 + Si-1
For a given odd positive integer N, Mr. X would like to generate the first N fake Fibonacci numbers, then sort them in ascending order, and find out what the middle number of the sorted sequence is. For example, with S1=3, S2=2, S3=4, S4=1, and N = 7, the first 7 fake Fibonacci numbers are:
3, 2, 4, 1, 4, 6, 10
After sorting, the sequence is:
1, 2, 3, 4, 4, 6, 10
And the middle number of the sorted sequence is 4.
Given four initial numbers S1, S2, S3, and S4, and N, your task is to write a program to help Mr. X find the middle number in the sorted sequence of the first N fake Fibonacci numbers.
The input file consists of several data sets. The first line of the input file contains the number of data
sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.
Each data set consists of only one line, which contains an odd integer N (5 ≤ N ≤ 19) followed by four
numbers S1, S2, S3, and S4 separated by space.
For each data set, write in one line the middle number of the sorted sequence of the first N fake Fibonacci numbers.
2 5 3 2 4 1 7 3 2 4 1
3 4
Migrated from old NTUJ.
The ACM-ICPC 2010 Asia Regional Contest, Site Hanoi
| No. | Testdata Range | Score |
|---|