시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 174 | 93 | 67 | 54.472% |
개미 N마리가 나무 판자 위에서 행진을 하고 있다. 개미는 1초에 1cm씩 앞으로 전진한다. 두 개미가 같은 곳에서 만나게 되면, 즉시 방향을 바꾸고 반대 방향으로 전진하게 된다. 개미가 나무의 끝에 도착하게 되면, 개미는 땅으로 떨어지고, 다른 개미에게 영향을 끼칠 수 없게 된다. (개미의 크기는 무시할 수 있다)
위의 그림은 시간이 0인 순간이다. 1초가 지난 후에 E와 A는 2에서 만나고, 두 개미는 방향을 바꾸게 된다. 1.5초가 지난 후에는 A와 B가 만나게 되고 동시에 C와 D도 만나게 된다. 네 개미는 모두 방향을 바꾼다. 0.5초가 지난 후 (3초)에는 E가 땅으로 떨어지게 된다.
개미의 움직임을 시뮬레이트하는 프로그램을 작성하시오.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 나무의 길이 L (단위: cm, 1 ≤ L ≤ 99,999)과 개미의 수 A (1 ≤ A ≤ L+1)가 주어진다.
다음 A개 줄에는 개미의 위치 Xi (0 ≤ Xi ≤ L)와 개미가 바라보고 있는 방향 (L: 왼쪽, R: 오른쪽)이 주어진다. 두 개미가 같은 위치에 있는 경우는 없다.
각 테스트 케이스 마다, "The last ant will fall down in T seconds - started at P."를 출력한다.
T는 마지막 개미가 떨어진 시간, P는 그 개미가 시간 0 때 있었던 위치이다. 두 개미가 동시에 떨어지는 경우에는 "started at P and Q"를 출력한다. (P < Q)
90000 1 0 R 10 1 0 L 14 5 3 L 6 L 13 L 8 R 1 R
The last ant will fall down in 90000 seconds - started at 0. The last ant will fall down in 0 seconds - started at 0. The last ant will fall down in 13 seconds - started at 6 and 8.