ReflectiveRectangle
SRM 626 · 2013-12-22 · by lg5293
Problem Statement
Raymond has a rectangle with dimensions sideA times sideB. The sides of the rectangle are perfect mirrors. There is a directional light source in one corner of the rectangle. Raymond can point the light source in any direction. (I.e., he can choose any angle strictly between 0 and 90 degrees. The chosen angle does not have to be an integer.) When Raymond turns the light source on, it will shine a ray of light into the rectangle. The light follows the law of reflection: whenever it hits a mirror, the angle of incidence equals the angle of reflection.
Raymond's goal is to shine the ray of light in the following way:
- The light must bounce off the sides of the rectangle exactly bounces times, without hitting a corner of the rectangle.
- After exactly that many bounces, the light must reach the opposite corner.
Raymond found all solutions to the above problem. In other words, he found all choices of the initial angle that lead to the desired outcome. He then took a sheet of paper. For each of the solutions, he computed the square of the distance the light traveled before hitting the opposite corner, and he wrote down the result. (Note that the squared distance is always an integer.)
You are given the
Constraints
- sizeA will be between 1 and 10^6, inclusive.
- sizeB will be between 1 and 10^6, inclusive.
- bounces will be between 0 and 10^9, inclusive.
3 4 0 Returns: 25
As there should be 0 bounces, Raymond has to point the light source directly at the opposite corner. The squared length of that light beam will be 3^2 + 4^2 = 25.
3 3 2 Returns: 180
There are two possible paths, each with squared length 90.
13 17 1 Returns: 0
Sometimes, it is not possible to find any valid path that satisfies the conditions.
59325 31785 262142 Returns: 48032850
Don't forget to take the answer modulo 10^9+7.
1000000 1000000 1000000000 Returns: 145972110
Be careful with overflow.
493285 816238 223092868 Returns: 507599497
3*5*7*11*...*23*2-2
734123 571842 536870912 Returns: 283488121
2^29-2
993829 181 999999984 Returns: 999277825
large prime*2-2
Submissions are judged against all 52 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ReflectiveRectangle with a public method int findSum(int sideA, int sideB, int bounces) · 52 test cases · 2 s / 256 MB per case