TopCoder SRM 570 Div1

2013. 02. 13.

아 요즘 ㅋㅋ......왜 풀어도 레이팅이 10씩 꾸준히 떨어지는걸까.......아....

250이 기하라서 긴장해서 좀 실수해서 늦은 감이 있다.. 250따위에 쫄지 말자!!ㅜㅜ

250

양수 배열 a와 양수 T (T <= 10억) 가 주어질 때, 다음 문제를 해결하라!

2차원 평면에 로봇이 임의의 방향을 바라보고 있다.

그리고 1시간마다 모든 a[i]에 대해 다음과 같은 일을 한다:

- 바라보는 방향으로 a[i]칸 이동한다.

- 오른쪽으로 90도씩 a[i]번 회전한다.

이 때, 로봇이 T시간 뒤에 있는 위치와 원래 위치의

맨하탄 거리 (L1-metric distance)를 구하여라.

*맨하탄 거리 : |x1-x2| + |y1-y2|

기하라서 쫄 수도 있지만 알고보면 무지무지 쉬운 문제다.

1시간이 지났을 때, 로봇이 어느 방향을 바라보고 있을지 생각해보면

T가 10억이지만 1번이나 2번, 많아야 3번만 봐도 된다는것을 알 수 있다(!)

1시간이 지났을 때, 로봇이 어느 방향을 바라보고 있을지는 다음과 같이 구할 수 있다.

( a[0] + a[1] + ... + a[a.size()-1] ) % 4

이게 0이면 처음 방향과 같은 방향을 보고있으므로

T시간 후에는 (1시간 간 거리)*T 만큼 떨어져있을것이고,

이게 1이거나 3이면 4시간마다 처음 상황으로 돌아올것이므로 T%4 시간만큼만 보면 되고,

( 1이면 한 시간마다 90도 회전한단 뜻이고, 3이면 -90도 회전한다는 뜻이니까 )

이게 2이면 2시간마다 처음 상황으로 돌아올것이므로 T%2 시간만큼만 보면 된다.

( 2이면 한 시간마다 180도 회전한단 뜻이니까 )

참 쉽죠? :D

500

1000