문제
정후는 자신의 강아지를 데리고 공원을 산책하는 중이다.
산책 중이던 정후가 잠깐 한눈 판 사이, 강아지가 정후의 시야에서 사라져버렸다!
하지만 걱정할 필요가 없다.
정후의 강아지는 습관적으로 K분의 주기를 갖고 같은 방식으로만 움직이기 때문이다.
심지어 정후는 강아지의 습관을 모두 수첩에 적어 놓았으므로, 쉽게 강아지의 동선을 추적할 수 있다.
예를 들어 아래 기록이 정후의 수첩에 적혀 있다고 가정하자.
4분 주기로 아래 행동을 반복
1분: (동1m,북1m) 2분: (동1m,남1m) 3분: (남1m) 4분: (서1m) |
만약 정후가 처음 강아지를 시야에서 놓친지 10분이 지났다면,
좌표평면에 다음과 같이 매 분마다의 위치를 그려서 현재 강아지의 위치를 찾아낼 수 있다.
그림 1
그림 1에서 붉은 선은 처음부터 4분 뒤까지 강아지의 동선을 그린 것이며,
푸른 선은 4분부터 8분까지의 동선을 나타낸 것이고,
녹색 선은 8분부터 10분까지의 동선을 그린 것이다.
그림 1을 바탕으로, 정후가 처음 강아지를 잃어버린 곳에서부터 동쪽으로 4m, 남쪽으로 2m지점에 강아지가 있음을 알 수 있다.
정후의 수첩에 적힌 강아지의 습관에 관한 정보가 주어질 때, T분 뒤 강아지의 위치를 출력하는 프로그램을 작성하라.
입력
첫 줄에 강아지의 행동주기인 K와, 강아지를 찾고자 하는 시점인 T가 공백을 사이에 두고 주어진다.
둘째 줄부터 다음 K줄에 걸쳐, 매 분마다 강아지의 이동방식이 주어진다.
이동 방식은 xi yi의 형식으로 주어지는데, 강아지가 마지막 위치에서 xi만큼 동쪽으로(음수라면 |xi| 만큼 서쪽으로), yi 만큼 북쪽(음수라면 |yi| 만큼 남쪽으로)으로 이동한다는 뜻이다.
(참고로 |a|는 절댓값 a를 뜻하며, 부호에 상관없는 그 숫자의 크기만을 의미한다.)
[제약 조건]
모든 부분문제에서 1≤K≤10,000 , 0≤T≤109(10억), -10 ≤ xi, yi ≤ 10을 만족한다.
모든 입력값은 정수이다.
출력
첫 줄에, 처음 강아지의 좌표를 (0,0)이라고 했을 때, T분 뒤의 강아지의 좌표 X,Y를 공백을 사이에 두고 출력한다.
C++ 사용자의 경우, 64bit 정수형 자료형인 long long을 사용해야 할 수도 있음에 유의한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 2점 | T=0 |
| #2 | 14점 | K분 후 강아지의 위치는 (0,0)을 만족한다. |
| #3 | 22점 | T≤106(1백만)을 만족한다. |
| #4 | 38점 | T를 K로 나눈 몫을 D라고 하면, D≤50,000을 만족한다. |
| #5 | 24점 | 주어진 조건 외에 아무 제약조건이 없다. |
예제
4 10
1 1
1 -1
0 -1
-1 0
4 -2
로그인해야 코드를 작성할 수 있어요.