Bamboo segment lengths
Statement
A certain bamboo grows by raising one segment at a time from the bottom upward. The segments are numbered 1, 2, 3 and on from the very bottom.
The length of a segment of this bamboo is set by how much the segments below press on it. Segments 1, 2 and 3 are all 1 long. From segment 4 upward, the length of the segment two places below added to the length of the segment three places below becomes the length of that segment. The length of the segment directly below is not used.
A researcher studying the bamboo wants to know how long the segment with a particular number is. The researcher asks this T times.
So, given a segment number N, write a program that finds the length of segment N.
For example, working out the lengths of segment 1 through segment 12 in order gives the table below.
| Segment | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Length | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 7 | 9 | 12 | 16 |
The length of segment 4 is segment 2 added to segment 1, which is 1+1, so 2. The length of segment 5 is segment 3 added to segment 2, which is 1+1, so 2, and the length of segment 6 is segment 4 added to segment 3, which is 2+1, so 3. In the same way segment 7 is 2+2, so 4, and segment 12 is segment 10 added to segment 9, which is 9+7, so 16.
So if N=6 the answer is 3, and if N=12 the answer is 16. Setting only the first three segments to 1 and filling in the rest in order lets any number be pulled out right away.
As the segment number grows the length grows very fast. Note that by the time N reaches 100 the length passes 800 billion, so a 32-bit integer cannot hold it.
Input and Output Examples
Example 1
Input
2 6 12
Output
3 16
Example 2
Input
3 1 2 3
Output
1 1 1
Example 3
Input
1 100
Output
888855064897
Input
First the number of times the researcher asks T is given as a natural number. (T is a natural number less than or equal to 100.)
Then T lines follow, each holding one segment number N asked that time, one per line and in order. (N is a natural number from 1 to 100.) The same number may be asked several times.
Output
Across T lines, print the length of segment N asked each time, one per line, in the order the questions came. Only one number is printed per line, so no space is left at the end of the line.
Requirements
- Segments 1, 2 and 3 are all 1 long
- From segment 4 upward the length is the segment two places below added to the segment three places below. The segment directly below is not used
- N comes in up to 100, so you can fill in the lengths up to segment 100 ahead of time and pull them out as the questions come
- The length of segment 100 goes past the range of a 32-bit integer, so it has to be handled with a wider integer
- Split the output into as many lines as there are questions and print them in order
- You must write a program that reads from standard input and writes to standard output
- Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
- The languages you can use are Python and JavaScript
- The memory limit is 256MB. The browser does not measure it, it only states it
- The time limit is set by measuring the setter's reference solution on the same runtime
- On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
- The output has to match the expected value down to the character. A space inside a line counts the same as any other character.
- There are 15 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
- You have to pass all 15 cases to solve this.
Examples
3 public cases. Judging also uses hidden cases. You have to pass all 15 cases to solve this.
2 6 12
3 16
1 100
888855064897
3 1 2 3
1 1 1
Solution
Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.
Submitting requires you to log in. Running against the public cases works without one.
You can test with 3 public cases. Submitting runs the hidden cases too.
People who solved this problem
The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.
Log in and you can see the code once you solve this problem.