Problem Description
Will has finally completed his A-levels and has decided to reward himself by spending a relaxing time at the arcade. After trying out the newest Time Crisis and Dance Dance Revolution machines, a retro Pinball machine caught his attention. The Pinball table is flat on the table unlike most Pinball machines and the entire Pinball map is very complex amd after a few tries, Will has found that the best spot to attain high scores is a triangular section of bumper walls located on the map.
The section is in the shape of an equilateral triangle with side length S and the pinball may only enter and exit at each of the vertices of the triangle. The pinball is very small compared to the size of section so it can be treated as a point. When the pinball enters the section, it bounces off the walls based on the usual laws of reflection and every time it bounces off a bumper wall Will scores a point.
The above diagram shows a possible path of a pinball as it enters through a vertex, bounces of 11 walls and exits through a vertex. The pinball does not have to exit by the same vertex that it enters through. The path above is worth 11 points. There are several other paths also worth 11 points. If S=1, we can add up the path lengths and find that the pinball travels a total distance of between 6 to 7 units
Today, Will is in luck because the arcade is having a "Jackpot Promotion" for the Pinball machine!! The arcade has come up with a Jackpot path and anyone who can match that EXACT path on the Pinball machine will win a prize. The prize today is an extremely cute Panda plushie and as Will stared into its adorable black panda eyes, he could feel the plushie calling out to him and he could not go home without it so he decided to take up the challenge.
The only clues that the arcade owners have given is that the path avoids all the obstacles and enters the triangular section of bumper walls at a specific vertex, bounces off N walls then exits at an unspecified vertex. With Will's uncomparable addiction and thus skill in gaming, he is able to aim very precisely at the unique path that will cause the pinball to enter the section at the required vertex at any angle he desires. Of course, there are only finitely many paths that satisfy the conditions above and thus Will would like to know what is the maximum number of tries he will need to get to his beloved panda plushie :)
Another idea struck Will as he was trying to help me get to his plushie quicker. He realised that there was friction between the pinball and the pinball table such that when the pinball enters the triangular section, it can only travel a maximum distance of D units before stopping. Knowing that the pinball must have exited the section in the Jackpot path, he only needs to try paths that will cause the pinball to exit within D units of distance, where exiting is defined as reaching any vertex. Help him find the maximum number of tries he needs!!
Implementation
You should submit a file that implements the following procedures
void init()
long long findPaths(long long S, long long N, long long D)
where S, N and D are as described above. If D=-1, there is negligible friction between the pinball and the table.
init will be called once at the start and subsequently findPaths can be called multiple times. findPaths should return the total number of possible paths that satisfy the conditions such that Will has to try them. If there are no possible paths, return -1.
Sample Input
5
1 2 -1
1 3 -1
2 7 8
2 7 9
2 7 10
Sample Output
-1
2
-1
2
4
Explanation: There are 4 possible paths for N=7 with 2 paths of length between 8 and 9 and 2 paths of length between 9 and 10
Subtasks
For all subtasks, -1 ≤ D ≤ 109 and findPaths will be called at most 1000 times
Subtask 1 (12 marks)
1 ≤ S,N ≤ 10
Subtask 2 (18 marks)
1 ≤ S,N ≤ 1000
Subtask 3 (23 marks)
1 ≤ S,N ≤ 109 and in addition D=-1 for all test cases
Subtask 4 (47 marks)
1 ≤ S,N ≤ 109