PIB - Pibonacci

no tags 

You might have heard of the Fibonacci numbers and of the number pi. If you let these two ideas merge, a new and esoteric concept comes into being: the Pibonacci numbers. These can be defined for real x>=0 by:

P(x) = 1 for 0<=x<4
P(x) = P(x-1) + P(x-pi) for 4<=x,

where pi = 3.1415926535... In this problem, you are asked to compute P(x) for a given x.

Input file specification

The input file contains several non-negative integer numbers (less than 30000) each on a separate line. The last line contains -1 marking the end of the input file.

Output file specification

For each non-negative real number in the input file, output the corresponding Pibonacci number. If the Pibonacci number be more than 50 digits long, divide it on the consecutive lines, outputting 50 digits on each (the last line may contain less digits).

Example

Input file:
0
4
11
-1
Output file:
1
2
20

hide comments
chalarangelo: 2015-07-01 14:18:27

Could I have the results for n=29 to n =50?

wisfaq: 2013-06-14 19:39:13

great problem, enjoyed it very much

:D: 2012-10-25 11:22:02

It should not work. I did the same the first time around. If you analyze it, you'll see you will generate way to many intermediate values. You need to analyze call tree and deduce some formula from there. Definitively not an easy problem!

Out0fbounds: 2012-06-05 13:40:43

recursion with memorization not working... plz help

[Rampage] Blue.Mary: 2011-05-27 02:34:16

(1) Each integer in the input file is less than 30000. Number of test cases is small.
(2) The original IPSC problem states that.

Erick Wong: 2011-05-26 23:29:09

Clarifications:

Is 30000 a bound on the number of inputs, or the size of each input?

If the input consists of non-negative integers, why refer to real numbers in the output section?


Added by:Fudan University Problem Setters
Date:2007-12-01
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:IPSC 2001; standard program and test data by Blue Mary