시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
7 초 (추가 시간 없음) | 1024 MB | 12 | 7 | 7 | 58.333% |
Given a square in the plane with corners at $(-1,-1)$, $(-1,1)$, $(1,1)$ and $(1,-1)$, we fire a ray from point $(-1,0)$ into the interior of the square on a path with a given slope. The ray bounces off of the sides of the square with an angle of reflection which is the same as the angle of incidence to the side at the point of intersection.
After a number of bounces, the ray intersects one of the square's sides again at some point which has rational coordinates. Find those rational coordinates in reduced form.
The single line of input contains three integers $a$, $b$ and $n$ ($1 \le a,b,n \le 10^6$, $\gcd(a,b)=1$), where the slope of the ray's initial path is $a/b$, and there are $n$ bounces. Note that $a$ and $b$ are relatively prime. The slope will be chosen so that the ray never bounces at a corner of the square.
Output a single line with four space-separated integers $p$, $q$, $s$ and $t$, where $(p/q, s/t)$ is the final point where the ray hits a side of the square, $p/q$ and $s/t$ are in reduced form, and the denominators ($q$ and $t$) are positive. If one of the coordinates has value $0$, output it as 0 1
.
1 1 3
-1 1 0 1
1 7 4
-1 1 6 7
355 113 123456
1 1 -58 113
The following is a picture of the first sample:
ICPC > Regionals > North America > Pacific Northwest Regional > 2021 ICPC Pacific Northwest Region > Division 2 T번
ICPC > Regionals > North America > South Central USA Regional > 2021 South Central USA Regional Contest > Division 2 H번
ICPC > Regionals > North America > Southeast USA Regional > 2021 Southeast USA Regional Programming Contest > Division 2 H번