| Submit | All submissions | Best solutions | Back to list |
BUILDTOW - Build the Tower |
8. Build the Tower
The president of Yanyang University has decided to build a new tower in front of the auditorium and has invited the students of SCE to help with the project. The tower is one of a kind and is made up of N cuboids one over the other. Each cuboid has a height of 1 unit and the length and breadth of a cuboid is equal. The top most cuboid’s length is 1 unit. The cuboid below it has a length of 2. All the cuboids below it have their lengths equal to the sum of the lengths of the 2 cuboids above it.
|
Cuboid |
Length |
Breadth |
Height |
|
1 |
1 |
1 |
1 |
|
2 |
2 |
2 |
1 |
|
3 |
3 |
3 |
1 |
|
4 |
5 |
5 |
1 |
|
5 |
8 |
8 |
1 |
As a token of appreciation the president has decided to give SCE a grant of
$ ((Volume of Tower) % 1000000007)
Your task is to calculate the amount of grant received by SCE for a given value of N.
Input
The first line contains the number of test cases (T) followed by T lines each containing a single integer N.
Output
For each test case output the grant that SCE receives for building the tower.
Constraints
T <= 20, N <= 10^18
Example
Sample Input
2 5 10
Sample Output
$103 $12815
| Added by: | Saransh Bansal |
| Date: | 2012-03-21 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
hide comments
|
|||||
|
2017-02-15 02:37:08 ben
100th :) |
|||||
|
2016-10-17 20:21:38
good question teaches us a new important algo |
|||||
|
2016-01-04 21:35:52 Deepak
patterns in fibonacci numbers ;).. |
|||||
|
2015-06-20 19:12:53 harshit sharma
copy paste fibosum solution.... :P |
|||||
|
2015-03-08 06:07:27 Vikrant Singh
stupid '$' gave me 1 WA :P |
|||||
|
2014-05-24 12:03:22 anshul garg
Getting TLE!! My solution is O(logn). Submission Id :: 11636338 Please help |
|||||
|
2014-05-24 09:31:49 [Lakshman]
@Ak Your algorithm complexity O( n )is too much for this problem and you are getting RTE because of too much recursion. curious? but how did you got AC? Last edit: 2014-05-24 09:33:35 |
|||||
|
2014-05-24 07:30:10 `Ak
pls help.... getiing runtime error(SIGSEGV) :( <snip> Last edit: 2022-12-20 23:34:10 |
|||||
|
2014-03-06 11:56:47 free mind ;)
easy one just like FIBOSUM ! @akhil for (10^18)-1 =712534868 ! |
|||||
|
2013-12-22 01:00:57 Ankit Kumar
@Rohan Phadke Your program fails for n>20 as fib[20] has only 20 elements while in the loop for(j=0;j<height;j++) {sum=sum+fib[j];.....} your prog will access fib[20],fib[21]... which doesn't exist so it will give a runtime error PS : Your whole approach is wrong here even though you fix the above problem.. |
|||||
RSS