| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12144 | Dark Souls |
|
| 12254 | Thanos' Dilemma |
|
Description
Dark Souls is a famous video game. The main character in Dark Souls 3 is known as
" Ashen one ". Today you are the Ashen one.
You are in a 5*5 room. You are at the
position ( 1, 1 ) -- the top left corner -- and you want to reach the
position ( 5, 5 )-- the lower right corner.
There's no obstacle in the room but monsters. If you and the monster are at the same position, you need to fight it.
The rule of fighting is Turn-based. You can always attack first, if the monster didn't die after your attack, then it's the monster's turn to attack you and so on.
There is always only two result after a fight, you died or the monster died.
Note that once you lost your hp you can't restore it.
Find out if you can reach the position ( 5,5 )
Input
input contain servel lines.
First line contains three integers.
The Hp, attack of Ashen one and k( 1 <= k <= 25 ) the number of monsters.
Following k lines each lines contains four integers.
The Hp, attack of i-th monster and the position x,y of i-th monster.
All numbers are >= 1 and in the range of int
Output
If you can reach the position ( 5 ,5 ) print "HEIR OF FIRE DESTROYED"
otherwise print "YOU DIED"
remember to print \n at the end of output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In "Avengers 3", we know that Thanos wants to eliminate half of the world to keep the world in a good balance. But, have you ever wondered about how he choose "1/2" ? Why don't he choose "1/3", "1/4", or "253/502" ?
He knows that the population of this world would just keep growing, so he calculated the formula of population of this world:
On the i-th year from the start of the world, the population of this world P(i) would be: P(i-1) + 2 * P(i-2) + P(i-3).
From this formula, he concluded that P(1)=1, P(2)=12, P(3)=13.
According to this formula, he could estimate the populations of the world on every year, so that he could choose the percentage of the population he would like to eliminate. (We don't know how he choose)
Because Thanos has a lot of planets to conquer, he asks you to calculate P(x), while x is given by him.
The world has lived for so many years, so he might ask you P(x) where x would be very large. And in case of P(x) is super large, the number should mod 109+7.
"Thanos Thinking About This Problem"
If you click on this picture, something might happen...
- Given t, indicates the number of testcases.
- P(i) = P(i-1) + 2*P(i-2) + P(i-3)
- P(1)=1, P(2)=12, P(3)=13
- Given x, you are going to calculate P(x)%(109+7) of every testcase.
Hint: use fpw(快速冪) to solve this problem!
If we rewrite the equation into matrix form, we could get the following formula:
With this formula, we can do something more:
Now, we can implement fpw(快速冪) method on the matrix power part. For those n<=3, just output the answer.
Note that you are encouraged to implement a "matrix" struct to solve this easier.
Input
The first line contains one integer t, indicates the number of testcases.
There are t lines below, each line contains one integer x.
1 <= t <= 20, 1 <= x <= 1018.
Output
For each testcase, output exactly one integer P(x)%(109+7).
Remember to output a '\n' at the end of every testcase.