UCV2013F - Life on Fornax

NASA's Ultrasonic Crawling Vessel, UCV for short, has arrived to galaxy UDFj - 39546284 in the Fornax constellation and has found a peculiar type of bacteria-like lifeform. As you may imagine a plan to collect samples a bring them back to earth has been set in motion. However, it would be rather unfortunate if they are all dead by the time the UCV gets back, the trip would take approximately 13.42 x 10^9 years travelling at light speed. Therefore, its necessary to pick a number of bacterium so that there are at least some of them alive when the UCV arrives back.

The UCV has studied the reproduction cycle of the bacterium inside a cryogenic pod and their behavior when released from the pod, but it lacks the algorithm to compute the final number for such a long period of time. Fortunately, it's been designed with a wormhole plugin installation mechanism that allows to upload algorithms in a matter of only a few years.

  1. Aging phase: Each bacteria becomes a year older.
  2. Reproduction phase: Each bacteria gives birth to a new bacteria, this is slightly different to earth bacteria in the sense that the new and old bacterium are no identical. The new bacteria is 0 years old while the old bacteria is at least 1 year old.
  3. Passing phase: Each bacteria that reaches maturity, exactly M years old, dies.

Fox example, this one reproduction cycle given a 0 years old bacteria and a 1 years old bacteria if maturity is reached at 2 years old.

Reproduction cycle

As you can see, during cryogenic reproduction, there's no fear of bacterium extinction, the number of births is at least as much as the number of deaths. However, when the pod is opened the bacterium enter into a strange iterative reduction phase, in each step of the reduction the oldest R bacterium die immediately; this process ends when there are fewer than R bacterium left. Note that the biggest problem arises when at some iteration there are exactly R bacterium left because they all die at that moment.

NASA ha asked you to write the algorithm that will be uploaded to the UCV to determine the number of bacterium that will exist after the pod is opened here on earth.

Input

The input contains several test cases, each one corresponding to a single simulation. Each test case starts with a line with three integers, the maturity age (1 <= M <= 50), the number of years for the UCV to come back (0 <= Y <= 10^12) and the reduction size (1 <= R <= 10^9); separated by a single space. The following line contains M integers, they
represent the number of 0, 1, ...,M - 1 years old bacterium placed inside the cryogenic pod.


The end of input is indicated by a test case with M = Y = R = 0.

Output

For each simulation output a single line containing a single integer, the number of bacterium that will be alive after the reduction process has finalized.

Example

Input:
2 1 4
1 1
2 1 2
1 1
2 2 2
1 1
2 2 5
1 1
6 0 100000
0 1 2 3 4 5
6 1000000000000 100000
0 1 2 3 4 5
0 0 0 Output: 3
1
1
0
15
21809

Added by:Hector Navarro
Date:2013-07-22
Time limit:1s-10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Local UCV 2013. Carlos Guía

hide comments
2013-08-08 18:52:30 alind
@Federico
Your nice time really pushed me to learn about Intel. I normally work on ARM :) Thanks
2013-08-08 18:19:54 Federico Lebrón
Very nice times alind :)

And yes, these data structures are quite special...
2013-08-07 12:24:59 alind
@Hector Very nice problem! Really forced me to learn new things.

@Miguel I don't want to spoil it for you but maybe if you look at the numbers in the data structure you are generating you will notice patterns. Also maybe you don't need to mod everywhere... Happy optimizing!
2013-07-28 18:32:31 Miguel Oliveira
Nice problem. I misunderstood the statement several times. Should have read it more carefully.

My solution is quite slower than the top solutions. If you read this, I would like to know how you solved it (either comment here or my e-mail is on my profile). Thanks.
2013-07-27 15:35:02 Miguel Oliveira
edit: nevermind, I think I understood the problem now

Last edit: 2013-07-27 18:23:28
2013-07-26 14:41:59 Hector Navarro
@Miguel: the number of bacterium fits on a 32 bit unsigned integer. The reduction R guarantees that the final answer will fit on a 64 bit integer
2013-07-26 00:07:50 Miguel Oliveira
Hi,
What is the limit on the number of bacterium of each age originally in the pod?
Also, can you say if the answer is guaranteed to fit in a 64 bit signed integer?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.