시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 39 22 19 57.576%

문제

개미 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)

예제 입력 1

90000 1
0 R
10 1
0 L
14 5
3 L
6 L
13 L
8 R
1 R

예제 출력 1

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.
W3sicHJvYmxlbV9pZCI6IjY2MTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWJiZjhcdWM3NTggXHVjNzc0XHViM2Q5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjMWNcdWJiZjggTlx1YjljOFx1YjlhY1x1YWMwMCBcdWIwOThcdWJiMzQgXHVkMzEwXHVjNzkwIFx1YzcwNFx1YzVkMFx1YzExYyBcdWQ1ODlcdWM5YzRcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhYzFjXHViYmY4XHViMjk0IDFcdWNkMDhcdWM1ZDAgMWNtXHVjNTI5IFx1YzU1ZVx1YzczY1x1Yjg1YyBcdWM4MDRcdWM5YzRcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWFjMWNcdWJiZjhcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YWNmM1x1YzVkMFx1YzExYyBcdWI5Y2NcdWIwOThcdWFjOGMgXHViNDE4XHViYTc0LCBcdWM5ODlcdWMyZGMgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YmMxNFx1YWZiOFx1YWNlMCBcdWJjMThcdWIzMDAgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzgwNFx1YzljNFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YWMxY1x1YmJmOFx1YWMwMCBcdWIwOThcdWJiMzRcdWM3NTggXHViMDVkXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YWM4YyBcdWI0MThcdWJhNzQsIFx1YWMxY1x1YmJmOFx1YjI5NCBcdWI1NDVcdWM3M2NcdWI4NWMgXHViNWE4XHVjNWI0XHVjOWMwXHVhY2UwLCBcdWIyZTRcdWI5NzggXHVhYzFjXHViYmY4XHVjNWQwXHVhYzhjIFx1YzYwMVx1ZDVhNVx1Yzc0NCBcdWIwN2NcdWNlNjAgXHVjMjE4IFx1YzVjNlx1YWM4YyBcdWI0MWNcdWIyZTQuIChcdWFjMWNcdWJiZjhcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IFx1YmIzNFx1YzJkY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0KTxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2FudHMucG5nXCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjMmRjXHVhYzA0XHVjNzc0IDBcdWM3NzggXHVjMjFjXHVhYzA0XHVjNzc0XHViMmU0LiAxXHVjZDA4XHVhYzAwIFx1YzljMFx1YjA5YyBcdWQ2YzRcdWM1ZDAgRVx1YzY0MCBBXHViMjk0IDJcdWM1ZDBcdWMxMWMgXHViOWNjXHViMDk4XHVhY2UwLCBcdWI0NTAgXHVhYzFjXHViYmY4XHViMjk0IFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWJjMTRcdWFmYjhcdWFjOGMgXHViNDFjXHViMmU0LiAxLjVcdWNkMDhcdWFjMDAgXHVjOWMwXHViMDljIFx1ZDZjNFx1YzVkMFx1YjI5NCBBXHVjNjQwIEJcdWFjMDAgXHViOWNjXHViMDk4XHVhYzhjIFx1YjQxOFx1YWNlMCBcdWIzZDlcdWMyZGNcdWM1ZDAgQ1x1YzY0MCBEXHViM2M0IFx1YjljY1x1YjA5OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjEyNCBcdWFjMWNcdWJiZjhcdWIyOTQgXHViYWE4XHViNDUwIFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWJjMTRcdWFmYmNcdWIyZTQuIDAuNVx1Y2QwOFx1YWMwMCBcdWM5YzBcdWIwOWMgXHVkNmM0ICgzXHVjZDA4KVx1YzVkMFx1YjI5NCBFXHVhYzAwIFx1YjU0NVx1YzczY1x1Yjg1YyBcdWI1YThcdWM1YjRcdWM5YzBcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMWNcdWJiZjhcdWM3NTggXHVjNmMwXHVjOWMxXHVjNzg0XHVjNzQ0IFx1YzJkY1x1YmJhY1x1YjgwOFx1Yzc3NFx1ZDJiOFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWFlMzhcdWM3NzQgTCAoXHViMmU4XHVjNzA0OiBjbSwgMSAmbGU7IEwgJmxlOyA5OSw5OTkpXHVhY2ZjIFx1YWMxY1x1YmJmOFx1Yzc1OCBcdWMyMTggQSAoMSAmbGU7IEEgJmxlOyBMKzEpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIEFcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMxY1x1YmJmOFx1Yzc1OCBcdWM3MDRcdWNlNTggWDxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBYPHN1Yj5pPFwvc3ViPiAmbGU7IEwpXHVjNjQwIFx1YWMxY1x1YmJmOFx1YWMwMCBcdWJjMTRcdWI3N2NcdWJjZjRcdWFjZTAgXHVjNzg4XHViMjk0IFx1YmMyOVx1ZDVhNSAoTDogXHVjNjdjXHVjYWJkLCBSOiBcdWM2MjRcdWI5NzhcdWNhYmQpXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YWMxY1x1YmJmOFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwgJnF1b3Q7VGhlIGxhc3QgYW50Jm5ic3A7d2lsbCBmYWxsIGRvd24gaW4gVCBzZWNvbmRzIC0gc3RhcnRlZCBhdCBQLiZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlRcdWIyOTQgXHViOWM4XHVjOWMwXHViOWM5IFx1YWMxY1x1YmJmOFx1YWMwMCBcdWI1YThcdWM1YjRcdWM5YzQgXHVjMmRjXHVhYzA0LCBQXHViMjk0IFx1YWRmOCBcdWFjMWNcdWJiZjhcdWFjMDAgXHVjMmRjXHVhYzA0IDAgXHViNTRjIFx1Yzc4OFx1YzVjOFx1YjM1OCBcdWM3MDRcdWNlNThcdWM3NzRcdWIyZTQuIFx1YjQ1MCBcdWFjMWNcdWJiZjhcdWFjMDAgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7c3RhcnRlZCBhdCBQIGFuZCBRJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFAgJmx0OyBRKTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjY2MTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBbmRyZXcgdGhlIEFudCIsImRlc2NyaXB0aW9uIjoiPHA+QW5kcmV3IHRoZSBBbnQgaXMgZmFzY2luYXRlZCBieSB0aGUgYmVoYXZpb3Igb2YgaGlzIGZyaWVuZHMuIFRob3VzYW5kcyBvZiB0aGVtIGFyZSBtYXJjaGluZyB0aGVpciBwYXRocyBvbiBhbmQgb24uIFRoZXkgY2FuIGJ1aWxkIGhpZ2hseSBvcmdhbml6ZWQgYW50LWhpbGxzLiBTb21ldGltZXMsIGhvd2V2ZXIsIHRoZXkgYWN0IGEgbGl0dGxlIGJpdCBzdHVwaWRseS48XC9wPlxyXG5cclxuPHA+UmVjZW50bHksIEFuZHJldyB3YXRjaGVkIGhpcyBmZWxsb3cgYW50cyBtYXJjaGluZyBvbiB0b3Agb2YgYSBsb25nIHBpZWNlIG9mIHdvb2QuIEhlIG5vdGljZWQgdGhlaXIgYmVoYXZpb3JhbCBwYXR0ZXJuIGlzIHZlcnkgc2ltcGxlOiBFYWNoIGFudCB3YWxrcyBzbG93bHkgZm9yd2FyZCB3aXRoIGEgY29uc3RhbnQgc3BlZWQgb2YgMSBjbSBwZXIgc2Vjb25kLiBXaGVuZXZlciBpdCBtZWV0cyBhbm90aGVyIGFudCwgYm90aCBvZiB0aGVtIG9ubHkgdG91Y2ggd2l0aCB0aGVpciBhbnRlbm5hZSBhbmQgaW1tZWRpYXRlbHkgdHVybiBhcm91bmQgYW5kIHdhbGsgdGhlIG9wcG9zaXRlIGRpcmVjdGlvbi4gSWYgYW4gYW50IGNvbWVzIHRvIHRoZSBlbmQgb2YgdGhlIHdvb2QsIGl0IGZhbGxzIGRvd24gYW5kIGRvZXMgbm90IGFcdWZiMDBlY3Qgb3RoZXIgYW50cyBhbnltb3JlLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2FudHMucG5nXCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBwaWN0dXJlIGFib3ZlIHNob3dzIGFuIGV4YW1wbGUgb2YgbW92aW5nIGFudHMgaW4gdGltZSAwIHMuIEluIG9uZSBzZWNvbmQsIHRoZSBhbnRzIEUgYW5kIEEgbWVldCBhdCBwb3NpdGlvbiAyIGFuZCBjaGFuZ2UgdGhlaXIgZGlyZWN0aW9ucy4gVGhlIGFudCBBIHRoZW4gbWVldHMgQiBpbiB0aGUgbmV4dCAxLjUgc2Vjb25kcy4gQXQgdGhlIHNhbWUgdGltZSAoMi41IHNlY29uZHMgYWZ0ZXIgdGhlIHN0YXJ0KSwgdGhlIGFudHMgQyBhbmQgRCB3aWxsIG1lZXQgdG9vLiBBbGwgZm91ciBvZiB0aGVtIGNoYW5nZSB0aGVpciBkaXJlY3Rpb25zLiBJbiB0aGUgbmV4dCAwLjUgc2Vjb25kICh0aW1lIDMgcyksIHRoZSBcdWZiMDFyc3QgYW50IChFKSBmYWxscyBkb3duIG9cdWZiMDAgdGhlIGxlZnQgZW5kLCBldGMuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBzaW11bGF0ZSB0aGUgbW92ZW1lbnQgb2YgYW50cy4gRm9yIHNpbXBsaWNpdHksIHN1cHBvc2UgdGhhdCB0aGUgYW50cyBoYXZlIHplcm8gc2l6ZSAoYWx0aG91Z2ggdGhlIHBpY3R1cmUgY291bGQgc3VnZ2VzdCBzb21ldGhpbmcgZWxzZSkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5pc3RzIG9mIHNldmVyYWwgc2NlbmFyaW9zLiBFYWNoIHNjZW5hcmlvIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VyIG51bWJlcnMgTCBhbmQgQSwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIEwgaXMgdGhlIGxlbmd0aCBvZiB0aGUgd29vZCBpbiBjbXMgKDEgJmxlOyBMICZsZTsgOTkgOTk5KSwgYW5kIEEgaXMgdGhlIG51bWJlciBvZiBhbnRzIGF0IHRoZSBiZWdpbm5pbmcgb2YgdGhlIHNpbXVsYXRpb24gKDEgJmxlOyBBICZsZTsgTCsgMSkuPFwvcD5cclxuXHJcbjxwPlRoZW4gdGhlcmUgYXJlIEEgbGluZXMsIGVhY2ggY29udGFpbmluZyBhIHBvc2l0aXZlIGludGVnZXIgWDxzdWI+aTxcL3N1Yj4sIG9uZSBzcGFjZSwgYW5kIGFuIHVwcGVyY2FzZSBsZXR0ZXIuIFRoZSBudW1iZXIgKDAgJmxlOyBYPHN1Yj5pPFwvc3ViPiAmbGU7IEwpIHNwZWNpXHVmYjAxZXMgdGhlIHBvc2l0aW9uIG9mIHRoZSBpLXRoIGFudCBhbmQgdGhlIGxldHRlciBpdHMgaW5pdGlhbCBkaXJlY3Rpb246IGVpdGhlciAmbGRxdW87TCZyZHF1bzsgZm9yIGxlZnQgKHRvd2FyZHMgemVybykgb3IgJmxkcXVvO1ImcmRxdW87IGZvciByaWdodC4gTm8gdHdvIGFudHMgd2lsbCBzdGFydCBhdCB0aGUgc2FtZSBwb3NpdGlvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBzY2VuYXJpbywgeW91IHNob3VsZCBwcmludCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIHRleHQgJmxkcXVvO1RoZSBsYXN0IGFudCB3aWxsIGZhbGwgZG93biBpbiBUIHNlY29uZHMgLSBzdGFydGVkIGF0IFAuJnJkcXVvOywgd2hlcmUgVCBpcyB0aGUgZXhhY3QgdGltZSB3aGVuIHRoZSBsYXN0IGFudCAob3IgdHdvKSByZWFjaGVzIHRoZSBlbmQgb2YgdGhlIHdvb2QsIGFuZCBQIGlzIHRoZSBwb3NpdGlvbiB3aGVyZSB0aGF0IHBhcnRpY3VsYXIgYW50IGhhcyBvcmlnaW5hbGx5IHN0YXJ0ZWQgaW4gdGltZSAwLiBJZiB0d28gbGFzdCBhbnRzIGZhbGwgZG93biBhdCB0aGUgc2FtZSB0aW1lLCBwcmludCAmbGRxdW87c3RhcnRlZCBhdCBQIGFuZCBRJnJkcXVvOywgaW5kaWNhdGluZyBib3RoIG9mIHRoZWlyIHBvc2l0aW9ucywgUCAmbHQ7IFEuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

채점

  • 제출한 후 다른 소스를 제출하려면 3초가 지나야 한다.