시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB122433332.353%

문제

스톡홀롬 지하철은 여러 개의 노선으로 이루어져 있다. 이 문제는 노선이 하나 있고, 자주 발생하는 문제인 신호 장애에 대해서 다룬다.

지하철 노선은 양 끝점을 연결하는 평행한 두 레일로 생각할 수 있다. 위쪽 레일에서 열차는 오른쪽에서 왼쪽으로 이동하며, 아래쪽 레일에서는 왼쪽에서 오른쪽으로 이동한다. 열차가 끝 점에 도착했을 때는, 반대편 레일로 이동한 다음, 방향을 바꿔서 다시 진행한다. 이렇게 방향을 바꾸고 반대편 레일로 이동하는데 걸리는 시간은 없다.

평소에 교통 흐름은 연속적이고, 열차는 항상 일정한 속도로 이동한다. (1분에 1칸) 열차는 균등하게 분포되어 있다. 따라서, 레일의 한 점을 지나가는 열차는 주기적이다. 열차가 역에 정차하고, 승객을 태우는데 걸리는 시간은 무시한다.

신호 장애가 발생했을 때, 열차는 레일 위에 랜덤하게 분포된다. 이 경우에 지하철 관제 센터에서는 열차를 재빠르게 균등하게 분포해야 한다. 각 열차의 현재 위치가 주어졌을 때, 얼마나 빠르게 균등하게 분포할 수 있는 지 구하는 프로그램을 작성하시오. 관제 센터에서는 열차를 잠시 멈추게 할 수도 있고, 방향을 반대로 바꿀 수도 있다. 방향을 바꾸는 경우에 열차는 반대편 라인으로 이동하게 된다.

위의 그림은 길이가 100인 레일을 나타낸다. 위쪽 그림에 열차는 5(오른쪽), 35(왼쪽), 46(왼쪽), 75(왼쪽), 85(오른쪽)에 있다. 열차를 균등하게 배치하는 한 가지 방법은 46에 있는 열차를 한 칸 움직이게 하고, 방향을 반대로 바꾸는 것이다. 하지만, 이 방법은 가장 빠른 방법은 아니다.

입력

첫째 줄에 레일의 길이 m, 열차의 수 n이 주어진다. 다음 n개 줄에는 열차의 현재 위치가 주어진다. 열차의 위치 xi와 함께 방향이 주어지며, L인 경우는 왼쪽, R인 경우는 오른쪽으로 열차가 향하는 것이다.

출력

열차를 균등하게 배치하는데 필요한 가장 빠른 시간을 출력한다. 소수점 오차는 10-6까지 허용한다.

제한

  • 100 ≤ m ≤ 100,000,000
  • 1 ≤ n ≤ 100,000
  • 0 ≤ xi ≤ m

예제 입력 1

100 5
5 R
35 L
46 L
75 L
85 R

예제 출력 1

0.5

예제 입력 2

100 8
9 L
15 R
41 L
33 L
81 R
33 R
100 L
97 R

예제 출력 2

15.500000
W3sicHJvYmxlbV9pZCI6IjI0MzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZTBcdWQ2MzggXHVjN2E1XHVjNTYwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyYTRcdWQxYTFcdWQ2NDBcdWI4NmMgXHVjOWMwXHVkNTU4XHVjY2EwXHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViMTc4XHVjMTIwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWIyOTQgXHViMTc4XHVjMTIwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM3ODhcdWFjZTAsIFx1Yzc5MFx1YzhmYyBcdWJjMWNcdWMwZGRcdWQ1NThcdWIyOTQgXHViYjM4XHVjODFjXHVjNzc4IFx1YzJlMFx1ZDYzOCBcdWM3YTVcdWM1NjBcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YjJlNFx1YjhlY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWMwXHVkNTU4XHVjY2EwIFx1YjE3OFx1YzEyMFx1Yzc0MCBcdWM1OTEgXHViMDVkXHVjODEwXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWQzYzlcdWQ1ODlcdWQ1NWMgXHViNDUwIFx1YjgwOFx1Yzc3Y1x1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzA0XHVjYWJkIFx1YjgwOFx1Yzc3Y1x1YzVkMFx1YzExYyBcdWM1ZjRcdWNjMjhcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwXHVjMTFjIFx1YzY3Y1x1Y2FiZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWJhNzAsIFx1YzU0NFx1Yjc5OFx1Y2FiZCBcdWI4MDhcdWM3N2NcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NWNcdWIyZTQuIFx1YzVmNFx1Y2MyOFx1YWMwMCBcdWIwNWQgXHVjODEwXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU4OFx1Yzc0NCBcdWI1NGNcdWIyOTQsIFx1YmMxOFx1YjMwMFx1ZDNiOCBcdWI4MDhcdWM3N2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjIFx1YjJlNFx1Yzc0YywgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YmMxNFx1YWZkNFx1YzExYyBcdWIyZTRcdWMyZGMgXHVjOWM0XHVkNTg5XHVkNTVjXHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YmMxNFx1YWZiOFx1YWNlMCBcdWJjMThcdWIzMDBcdWQzYjggXHViODA4XHVjNzdjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkM2M5XHVjMThjXHVjNWQwIFx1YWQ1MFx1ZDFiNSBcdWQ3NTBcdWI5ODRcdWM3NDAgXHVjNWYwXHVjMThkXHVjODAxXHVjNzc0XHVhY2UwLCBcdWM1ZjRcdWNjMjhcdWIyOTQgXHVkNTZkXHVjMGMxIFx1Yzc3Y1x1YzgxNVx1ZDU1YyBcdWMxOGRcdWIzYzRcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0LiAoMVx1YmQ4NFx1YzVkMCAxXHVjZTc4KSBcdWM1ZjRcdWNjMjhcdWIyOTQgXHVhZGUwXHViNGYxXHVkNTU4XHVhYzhjJm5ic3A7XHViZDg0XHVkM2VjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWI4MDhcdWM3N2NcdWM3NTggXHVkNTVjIFx1YzgxMFx1Yzc0NCBcdWM5YzBcdWIwOThcdWFjMDBcdWIyOTQgXHVjNWY0XHVjYzI4XHViMjk0IFx1YzhmY1x1YWUzMFx1YzgwMVx1Yzc3NFx1YjJlNC4gXHVjNWY0XHVjYzI4XHVhYzAwIFx1YzVlZFx1YzVkMCBcdWM4MTVcdWNjMjhcdWQ1NThcdWFjZTAsIFx1YzJiOVx1YWMxZFx1Yzc0NCBcdWQwZGNcdWM2YjBcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWJiMzRcdWMyZGNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJlMFx1ZDYzOCBcdWM3YTVcdWM1NjBcdWFjMDAgXHViYzFjXHVjMGRkXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjNWY0XHVjYzI4XHViMjk0IFx1YjgwOFx1Yzc3YyBcdWM3MDRcdWM1ZDAgXHViNzljXHViMzY0XHVkNTU4XHVhYzhjIFx1YmQ4NFx1ZDNlY1x1YjQxY1x1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM5YzBcdWQ1NThcdWNjYTAgXHVhZDAwXHVjODFjIFx1YzEzY1x1ZDEzMFx1YzVkMFx1YzExY1x1YjI5NCBcdWM1ZjRcdWNjMjhcdWI5N2MgXHVjN2FjXHViZTYwXHViOTc0XHVhYzhjIFx1YWRlMFx1YjRmMVx1ZDU1OFx1YWM4YyBcdWJkODRcdWQzZWNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVjNWY0XHVjYzI4XHVjNzU4IFx1ZDYwNFx1YzdhYyBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNWJjXHViOWM4XHViMDk4IFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWFkZTBcdWI0ZjFcdWQ1NThcdWFjOGMgXHViZDg0XHVkM2VjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFkMDBcdWM4MWMgXHVjMTNjXHVkMTMwXHVjNWQwXHVjMTFjXHViMjk0IFx1YzVmNFx1Y2MyOFx1Yjk3YyBcdWM3YTBcdWMyZGMgXHViYTQ4XHVjZDk0XHVhYzhjIFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwLCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYzE4XHViMzAwXHViODVjIFx1YmMxNFx1YWZjMCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYzE0XHVhZmI4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM1ZjRcdWNjMjhcdWIyOTQgXHViYzE4XHViMzAwXHVkM2I4IFx1Yjc3Y1x1Yzc3OFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzNjNmZlNTlkLTMzMzctNDM2NS04Nzg3LTg0M2Y5ZTQ1MDhmZVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNDAzcHg7IGhlaWdodDogMTQ4cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVhZTM4XHVjNzc0XHVhYzAwIDEwMFx1Yzc3OCBcdWI4MDhcdWM3N2NcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWM3MDRcdWNhYmQgXHVhZGY4XHViOWJjXHVjNWQwIFx1YzVmNFx1Y2MyOFx1YjI5NCA1KFx1YzYyNFx1Yjk3OFx1Y2FiZCksIDM1KFx1YzY3Y1x1Y2FiZCksIDQ2KFx1YzY3Y1x1Y2FiZCksIDc1KFx1YzY3Y1x1Y2FiZCksIDg1KFx1YzYyNFx1Yjk3OFx1Y2FiZClcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWM1ZjRcdWNjMjhcdWI5N2MgXHVhZGUwXHViNGYxXHVkNTU4XHVhYzhjIFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YjI5NCBcdWQ1NWMgXHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1Yzc0MCA0Nlx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNWY0XHVjYzI4XHViOTdjIFx1ZDU1YyBcdWNlNzggXHVjNmMwXHVjOWMxXHVjNzc0XHVhYzhjIFx1ZDU1OFx1YWNlMCwgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YmMxOFx1YjMwMFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Yzc3NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI4MDhcdWM3N2NcdWM3NTggXHVhZTM4XHVjNzc0IG0sIFx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1ZjRcdWNjMjhcdWM3NTggXHVkNjA0XHVjN2FjIFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWM3MDRcdWNlNTggeDxzdWI+aTxcL3N1Yj5cdWM2NDAgXHVkNTY4XHVhZWQ4IFx1YmMyOVx1ZDVhNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIExcdWM3NzggXHVhY2JkXHVjNmIwXHViMjk0IFx1YzY3Y1x1Y2FiZCwgUlx1Yzc3OCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YzVmNFx1Y2MyOFx1YWMwMCBcdWQ1YTVcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzVmNFx1Y2MyOFx1Yjk3YyBcdWFkZTBcdWI0ZjFcdWQ1NThcdWFjOGMgXHViYzMwXHVjZTU4XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWM2MjRcdWNjMjhcdWIyOTQgMTA8c3VwPi02PFwvc3VwPlx1YWU0Y1x1YzljMCBcdWQ1YzhcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEwMCAmbGU7IG0gJmxlOyAxMDAsMDAwLDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgbiAmbGU7IDEwMCwwMDA8XC9saT5cclxuXHQ8bGk+MCAmbGU7IHg8c3ViPmk8XC9zdWI+ICZsZTsgbTxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjQzMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN1YndheSBTaWduYWxsaW5nIEVycm9yIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgc3Vid2F5IGluIFN0b2NraG9sbSBjb25zaXN0cyBvZiBzZXZlcmFsIHN1YndheSBsaW5lcy4gSW4gdGhpcyBwcm9ibGVtIHdlIHdpbGwgY29uc2lkZXIgb25lIGxpbmUgaW4gcGFydGljdWxhciwgYW5kIHRoZSBwcm9ibGVtcyB0aGF0IHF1aXRlIG9mdGVuIGhhcHBlbnMgb24gaXQgd2hlbiB0aGVyZSZyc3F1bztzIGJlZW4gYSAmbGRxdW87c2lnbmFsbGluZyBlcnJvciZyZHF1bzsuPFwvcD5cclxuXHJcbjxwPkEgc3Vid2F5IGxpbmUgY2FuIGJlIHNlZW4gYXMgdHdvIHBhcmFsbGVsIHJhaWxzIGNvbm5lY3RlZCBhdCB0aGUgZW5kcG9pbnRzLiBJbiB0aGUgdXBwZXIgcmFpbCB0aGUgdHJhaW5zIGFyZSBnb2luZyBmcm9tIHJpZ2h0IHRvIGxlZnQgYW5kIGluIHRoZSBsb3dlciByYWlsIHRoZSB0cmFpbnMgYXJlIGdvaW5nIGZyb20gbGVmdCB0byByaWdodC4gV2hlbiBhIHRyYWluIHJlYWNoZXMgYW4gZW5kcG9pbnQgb2YgYSByYWlsLCBpdCBzd2l0Y2hlcyB0byB0aGUgb3Bwb3NpdGUgcmFpbCBhbmQgY2hhbmdlcyBkaXJlY3Rpb24uIFRoaXMgc3dpdGNoIGlzIGluc3RhbnRhbmVvdXMgYW5kIHRha2VzIG5vIHRpbWUuPFwvcD5cclxuXHJcbjxwPkR1cmluZyBub3JtYWwgdHJhZlx1ZmIwMWMsIHRoZSB0cmFmXHVmYjAxYyBcdWZiMDJvdyBpcyBjb250aW51b3VzIGFuZCB0aGUgdHJhaW5zIGFyZSBtb3ZpbmcgYXQgYSBjb25zdGFudCBzcGVlZCAoMSBsZW5ndGggdW5pdCBwZXIgdGltZSB1bml0KS4gVGhlIHRyYWlucyBhcmUgZXZlbmx5IGRpc3RyaWJ1dGVkOyB0aGF0IGlzLCBhdCBhbnkgZ2l2ZW4gcG9zaXRpb24gb24gYSByYWlsLCB0aGUgdHJhaW5zIHdpbGwgYXBwZWFyIHBlcmlvZGljYWxseS4gV2Ugd2lsbCBhc3N1bWUgdGhhdCB0aGUgdGltZSBpdCB0YWtlcyBmb3IgYSB0cmFpbiB0byBzdG9wIGFuZCBwaWNrIHVwIHBhc3NlbmdlcnMgaXMgbmVnbGlnaWJsZS48XC9wPlxyXG5cclxuPHA+Tm93LCBiZWNhdXNlIG9mIHNpZ25hbGxpbmcgZXJyb3JzLCB0aGUgdHJhaW5zIGhhdmUgYmVlbiByYW5kb21seSBkaXN0cmlidXRlZCBhbG9uZyB0aGUgbGluZS4gWW91ciBqb2IgYXMgdGhlIHRyYWZcdWZiMDFjIG1hbmFnZXIgaXMgdG8sIGFzIGZhc3QgYXMgcG9zc2libGUsIGVuc3VyZSB0aGF0IHRoZSB0cmFpbnMgd2lsbCBiZSBldmVubHkgZGlzdHJpYnV0ZWQgYWxvbmcgdGhlIGxpbmUgYWdhaW4uIFdyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgY3VycmVudCB0cmFpbiBwb3NpdGlvbnMsIGNhbGN1bGF0ZXMgaG93IGZhc3QgdGhpcyBjYW4gYmUgYWNoaWV2ZWQuIFlvdSBhcmUgYWxsb3dlZCB0byBvcmRlciB0aGUgdHJhaW5zIHRvIHRlbXBvcmFyaWx5IHN0b3AsIGFuZFwvb3IgY2hhbmdlIGRpcmVjdGlvbiBhbnl3aGVyZSBhbG9uZyB0aGUgbGluZS4gSWYgYSB0cmFpbiBjaGFuZ2VzIGRpcmVjdGlvbiwgaXQgd2lsbCBtb3ZlIGZyb20gb25lIHJhaWwgdG8gdGhlIG90aGVyLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzNjNmZlNTlkLTMzMzctNDM2NS04Nzg3LTg0M2Y5ZTQ1MDhmZVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNDAzcHg7IGhlaWdodDogMTQ4cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxOiBCb3RoIHJhaWxzIGhhdmUgdGhlIGxlbmd0aCAxMDAuIEluIHRoZSB1cHBlciBleGFtcGxlIHRoZSB0cmFpbnMgYXJlIHBvc2l0aW9uZWQgYXQgNSAoZGlyZWN0aW9uIHJpZ2h0KSwgMzUgKGxlZnQpLCA0NiAobGVmdCksIDc1IChsZWZ0KSBhbmQgODUgKHJpZ2h0KS4gT25lIHdheSB0byBtYWtlIHRoZSB0cmFpbnMgZXZlbmx5IGRpc3RyaWJ1dGVkIGlzIGZvciB0aGUgdHJhaW4gYXQgcG9zaXRpb24gNDYgdG8gdHJhdmVsIG9uZSB1bml0IHRvIHRoZSBsZWZ0IGFuZCB0aGVuIGNoYW5nZSBkaXJlY3Rpb24uIFRoaXMgdGFrZXMgb25lIHRpbWUgdW5pdC4gSG93ZXZlciwgdGhpcyBpcyBub3QgdGhlIG9wdGltYWwgc29sdXRpb247IHNlZSBFeGFtcGxlJm5ic3A7YmVsb3cuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgaW4gdGhlIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIHRoZSBsZW5ndGggbSBvZiB0aGUgc3Vid2F5IHJhaWxzLCBhbmQgdGhlIG51bWJlciBuIG9mIHRyYWlucyBvbiB0aGUgbGluZS4gVGhlbiBmb2xsb3dzIG4gbGluZXMgZWFjaCBkZXNjcmliaW5nIHRoZSBjdXJyZW50IHBvc2l0aW9uIG9mIGEgdHJhaW4uIFRoaXMgd2lsbCBiZSBnaXZlbiBhcyBhbiBpbnRlZ2VyIHg8c3ViPmk8XC9zdWI+IGFuZCBhIGRpcmVjdGlvbiAoTCBmb3IgbGVmdCwgUiBmb3IgcmlnaHQpLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIHNob3VsZCBvdXRwdXQgYSBzaW5nbGUgbGluZSB0byBzdGFuZGFyZCBvdXRwdXQsIGNvbnRhaW5pbmcgdGhlIHNob3J0ZXN0IHRpbWUgaXQgdGFrZXMgdG8gbWFrZSB0aGUgdHJhaW5zIGV2ZW5seSBkaXN0cmlidXRlZC4gWW91ciBwcm9ncmFtIHNob3VsZCBoYXZlIGFuIGFic29sdXRlIHByZWNpc2lvbiBlcnJvciBvZiBhdCBtb3N0IDEwPHN1cD4tNjxcL3N1cD4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xMDAgJmxlOyBtICZsZTsgMTAwLDAwMCwwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IG4gJmxlOyAxMDAsMDAwPFwvbGk+XHJcblx0PGxpPjAgJmxlOyB4PHN1Yj5pPFwvc3ViPiAmbGU7IG08XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 3번