| Submit | All submissions | Best solutions | Back to list |
ADAMONEY - Ada and Economy |
Ada the Ladybug thinks she found out the key of her economy business. Ada is a farmer and she thinks she found a pattern in the way she makes money. She sees that the money for the next day can be counted from past days as the money she had during previous day plus double the money she had two days before plus five times the money she had four days before plus the money she had five days before. Simple isn't it? Well she wants this system to be automatic, so she had asked you to make a program for it.
Oh, one more thing. You must take one mind, that she buys a tractor as soon as she have enough money for it (possibly multiple tractors if it is possible). The cost of tractor is 109+7
Input
The first line contains 1 ≤ T ≤ 1000, the number of test-cases.
Each of the following T lines contains 6 integers 0 ≤ T0,T1,T2,T3,T4 < 109+7, meaning the money she has in the first 5 days, and 0 ≤ N ≤ 1016 meaning the Nth day for which she wants to know the money she will posses.
As you hopefully understood, today is day 0
Output
For each test-case print the amount of money she will have in Nth day (the money is counted at the end of a day, after she buys all tractors!).
Example Input
7 1 1 1 1 1 5 1 2 3 4 5 6 4 2 5 6 4 10 1 2 1 2 1 15 1 2 1 1 2 20 1 0 0 0 0 19 2 4 8 16 32 1024
Example Output
9 51 1777 49552 3128538 62128 565476237
| Added by: | Morass |
| Date: | 2017-02-11 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
hide comments
|
2022-09-28 07:24:09
First we have to do the task of the best cases, that is the value of the n is less than 5. On that case our answer will be come directly from the T array. So we have to count from the 5th index. First try to find the genaral equation. That is the for every value of the pemutated array T. The eqution will be the A(i) = A(i - 1) + 2 * A(i - 2) + 5 * A(i - 4) + A(i - 5) So, first try to build the matrixes, T = | 0 1 2 3 4 5 --|---------------------------------------------------------------- 0 | 0 0 0 0 0 0 --|---------------------------------------------------------------- 1 | 0 1 2 0 5 1 -> this will carry out the relation of the equation --|--------------------------------------------------------------- 2 | 0 1 0 0 0 0 --|---------------------------------------------------------------- 3 | 0 0 1 0 0 0 --|---------------------------------------------------------------- 4 | 0 0 0 1 0 0 --|--------------------------------------------------------------- 5 | 0 0 0 0 1 0 --|--------------------------------------------------------------- So our final mat will be the T^(n - 4). and the total number will come from the 1'th index of the matrix ans = sum(T(1, i) * T(j)), 1 <= i <= 5, 4 >= j >= 1 Last edit: 2022-09-28 07:40:13 |
|
|
2022-06-16 23:44:43 David
Beware. N can be 4 or less! |
|
|
2020-12-25 20:34:16
basic matrix expo |
|
|
2017-02-12 02:19:08
[Rampage] Blue.Mary: Sure! Thanks for advice + thanks for piloting tests!!! |
|
|
2017-02-12 02:15:08 [Rampage] Blue.Mary
This should be put into tutorial section because large numbers of (direct) Matrix multiplication problem exists in SPOJ classical section. |
RSS