시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 57 18 12 28.571%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

0.5

힌트

W3sicHJvYmxlbV9pZCI6IjI0MzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZTBcdWQ2MzggXHVjN2E1XHVjNTYwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyYTRcdWQxYTFcdWQ2NDBcdWI4NmMgXHVjOWMwXHVkNTU4XHVjY2EwXHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViMTc4XHVjMTIwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWIyOTQgXHViMTc4XHVjMTIwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM3ODhcdWFjZTAsIFx1Yzc5MFx1YzhmYyBcdWJjMWNcdWMwZGRcdWQ1NThcdWIyOTQgXHViYjM4XHVjODFjXHVjNzc4IFx1YzJlMFx1ZDYzOCBcdWM3YTVcdWM1NjBcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YjJlNFx1YjhlY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWMwXHVkNTU4XHVjY2EwIFx1YjE3OFx1YzEyMFx1Yzc0MCBcdWM1OTEgXHViMDVkXHVjODEwXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWQzYzlcdWQ1ODlcdWQ1NWMgXHViNDUwIFx1YjgwOFx1Yzc3Y1x1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzA0XHVjYWJkIFx1YjgwOFx1Yzc3Y1x1YzVkMFx1YzExYyBcdWM1ZjRcdWNjMjhcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwXHVjMTFjIFx1YzY3Y1x1Y2FiZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWJhNzAsIFx1YzU0NFx1Yjc5OFx1Y2FiZCBcdWI4MDhcdWM3N2NcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NWNcdWIyZTQuIFx1YzVmNFx1Y2MyOFx1YWMwMCBcdWIwNWQgXHVjODEwXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU4OFx1Yzc0NCBcdWI1NGNcdWIyOTQsIFx1YmMxOFx1YjMwMFx1ZDNiOCBcdWI4MDhcdWM3N2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjIFx1YjJlNFx1Yzc0YywgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YmMxNFx1YWZkNFx1YzExYyBcdWIyZTRcdWMyZGMgXHVjOWM0XHVkNTg5XHVkNTVjXHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YmMxNFx1YWZiOFx1YWNlMCBcdWJjMThcdWIzMDBcdWQzYjggXHViODA4XHVjNzdjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkM2M5XHVjMThjXHVjNWQwIFx1YWQ1MFx1ZDFiNSBcdWQ3NTBcdWI5ODRcdWM3NDAgXHVjNWYwXHVjMThkXHVjODAxXHVjNzc0XHVhY2UwLCBcdWM1ZjRcdWNjMjhcdWIyOTQgXHVkNTZkXHVjMGMxIFx1Yzc3Y1x1YzgxNVx1ZDU1YyBcdWMxOGRcdWIzYzRcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0LiAoMVx1YmQ4NFx1YzVkMCAxXHVjZTc4KSBcdWM1ZjRcdWNjMjhcdWIyOTQgXHVhZGUwXHViNGYxXHVkNTU4XHVhYzhjJm5ic3A7XHViZDg0XHVkM2VjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWI4MDhcdWM3N2NcdWM3NTggXHVkNTVjIFx1YzgxMFx1Yzc0NCBcdWM5YzBcdWIwOThcdWFjMDBcdWIyOTQgXHVjNWY0XHVjYzI4XHViMjk0IFx1YzhmY1x1YWUzMFx1YzgwMVx1Yzc3NFx1YjJlNC4gXHVjNWY0XHVjYzI4XHVhYzAwIFx1YzVlZFx1YzVkMCBcdWM4MTVcdWNjMjhcdWQ1NThcdWFjZTAsIFx1YzJiOVx1YWMxZFx1Yzc0NCBcdWQwZGNcdWM2YjBcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWJiMzRcdWMyZGNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJlMFx1ZDYzOCBcdWM3YTVcdWM1NjBcdWFjMDAgXHViYzFjXHVjMGRkXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjNWY0XHVjYzI4XHViMjk0IFx1YjgwOFx1Yzc3YyBcdWM3MDRcdWM1ZDAgXHViNzljXHViMzY0XHVkNTU4XHVhYzhjIFx1YmQ4NFx1ZDNlY1x1YjQxY1x1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM5YzBcdWQ1NThcdWNjYTAgXHVhZDAwXHVjODFjIFx1YzEzY1x1ZDEzMFx1YzVkMFx1YzExY1x1YjI5NCBcdWM1ZjRcdWNjMjhcdWI5N2MgXHVjN2FjXHViZTYwXHViOTc0XHVhYzhjIFx1YWRlMFx1YjRmMVx1ZDU1OFx1YWM4YyBcdWJkODRcdWQzZWNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVjNWY0XHVjYzI4XHVjNzU4IFx1ZDYwNFx1YzdhYyBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNWJjXHViOWM4XHViMDk4IFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWFkZTBcdWI0ZjFcdWQ1NThcdWFjOGMgXHViZDg0XHVkM2VjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFkMDBcdWM4MWMgXHVjMTNjXHVkMTMwXHVjNWQwXHVjMTFjXHViMjk0IFx1YzVmNFx1Y2MyOFx1Yjk3YyBcdWM3YTBcdWMyZGMgXHViYTQ4XHVjZDk0XHVhYzhjIFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwLCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYzE4XHViMzAwXHViODVjIFx1YmMxNFx1YWZjMCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYzE0XHVhZmI4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM1ZjRcdWNjMjhcdWIyOTQgXHViYzE4XHViMzAwXHVkM2I4IFx1Yjc3Y1x1Yzc3OFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA4XC9zcy5wbmdcIiBzdHlsZT1cImhlaWdodDoxNjZweDsgd2lkdGg6NDI2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWFlMzhcdWM3NzRcdWFjMDAgMTAwXHVjNzc4IFx1YjgwOFx1Yzc3Y1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YzcwNFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM1ZDAgXHVjNWY0XHVjYzI4XHViMjk0IDUoXHVjNjI0XHViOTc4XHVjYWJkKSwgMzUoXHVjNjdjXHVjYWJkKSwgNDYoXHVjNjdjXHVjYWJkKSwgNzUoXHVjNjdjXHVjYWJkKSwgODUoXHVjNjI0XHViOTc4XHVjYWJkKVx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1YzVmNFx1Y2MyOFx1Yjk3YyBcdWFkZTBcdWI0ZjFcdWQ1NThcdWFjOGMgXHViYzMwXHVjZTU4XHVkNTU4XHViMjk0IFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1XHVjNzQwIDQ2XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM1ZjRcdWNjMjhcdWI5N2MgXHVkNTVjIFx1Y2U3OCBcdWM2YzBcdWM5YzFcdWM3NzRcdWFjOGMgXHVkNTU4XHVhY2UwLCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYzE4XHViMzAwXHViODVjIFx1YmMxNFx1YWZiOFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjNzc0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjgwOFx1Yzc3Y1x1Yzc1OCBcdWFlMzhcdWM3NzQgbSwgXHVjNWY0XHVjYzI4XHVjNzU4IFx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWQ2MDRcdWM3YWMgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNWY0XHVjYzI4XHVjNzU4IFx1YzcwNFx1Y2U1OCB4PHN1Yj5pPFwvc3ViPlx1YzY0MCBcdWQ1NjhcdWFlZDggXHViYzI5XHVkNWE1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgTFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNjdjXHVjYWJkLCBSXHVjNzc4IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNWY0XHVjYzI4XHVhYzAwIFx1ZDVhNVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuICgxMDAgJmxlOyBtICZsZTsgMTAwLDAwMCwwMDAsIDEgJmxlOyBuICZsZTsgMTAwLDAwMCAwICZsZTsgeDxzdWI+aTxcL3N1Yj4gJmxlOyBtKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzVmNFx1Y2MyOFx1Yjk3YyBcdWFkZTBcdWI0ZjFcdWQ1NThcdWFjOGMgXHViYzMwXHVjZTU4XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWM2MjRcdWNjMjhcdWIyOTQgMTA8c3VwPi02PFwvc3VwPlx1YWU0Y1x1YzljMCBcdWQ1YzhcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjQzMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN1YndheSBTaWduYWxsaW5nIEVycm9yIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgc3Vid2F5IGluIFN0b2NraG9sbSBjb25zaXN0cyBvZiBzZXZlcmFsIHN1YndheSBsaW5lcy4gSW4gdGhpcyBwcm9ibGVtIHdlIHdpbGwgY29uc2lkZXIgb25lIGxpbmUgaW4gcGFydGljdWxhciwgYW5kIHRoZSBwcm9ibGVtcyB0aGF0IHF1aXRlIG9mdGVuIGhhcHBlbnMgb24gaXQgd2hlbiB0aGVyZSZyc3F1bztzIGJlZW4gYSAmbGRxdW87c2lnbmFsbGluZyBlcnJvciZyZHF1bzsuPFwvcD5cclxuXHJcbjxwPkEgc3Vid2F5IGxpbmUgY2FuIGJlIHNlZW4gYXMgdHdvIHBhcmFsbGVsIHJhaWxzIGNvbm5lY3RlZCBhdCB0aGUgZW5kcG9pbnRzLiBJbiB0aGUgdXBwZXIgcmFpbCB0aGUgdHJhaW5zIGFyZSBnb2luZyBmcm9tIHJpZ2h0IHRvIGxlZnQgYW5kIGluIHRoZSBsb3dlciByYWlsIHRoZSB0cmFpbnMgYXJlIGdvaW5nIGZyb20gbGVmdCB0byByaWdodC4gV2hlbiBhIHRyYWluIHJlYWNoZXMgYW4gZW5kcG9pbnQgb2YgYSByYWlsLCBpdCBzd2l0Y2hlcyB0byB0aGUgb3Bwb3NpdGUgcmFpbCBhbmQgY2hhbmdlcyBkaXJlY3Rpb24uIFRoaXMgc3dpdGNoIGlzIGluc3RhbnRhbmVvdXMgYW5kIHRha2VzIG5vIHRpbWUuPFwvcD5cclxuXHJcbjxwPkR1cmluZyBub3JtYWwgdHJhZlx1ZmIwMWMsIHRoZSB0cmFmXHVmYjAxYyBcdWZiMDJvdyBpcyBjb250aW51b3VzIGFuZCB0aGUgdHJhaW5zIGFyZSBtb3ZpbmcgYXQgYSBjb25zdGFudCBzcGVlZCAoMSBsZW5ndGggdW5pdCBwZXIgdGltZSB1bml0KS4gVGhlIHRyYWlucyBhcmUgZXZlbmx5IGRpc3RyaWJ1dGVkOyB0aGF0IGlzLCBhdCBhbnkgZ2l2ZW4gcG9zaXRpb24gb24gYSByYWlsLCB0aGUgdHJhaW5zIHdpbGwgYXBwZWFyIHBlcmlvZGljYWxseS4gV2Ugd2lsbCBhc3N1bWUgdGhhdCB0aGUgdGltZSBpdCB0YWtlcyBmb3IgYSB0cmFpbiB0byBzdG9wIGFuZCBwaWNrIHVwIHBhc3NlbmdlcnMgaXMgbmVnbGlnaWJsZS48XC9wPlxyXG5cclxuPHA+Tm93LCBiZWNhdXNlIG9mIHNpZ25hbGxpbmcgZXJyb3JzLCB0aGUgdHJhaW5zIGhhdmUgYmVlbiByYW5kb21seSBkaXN0cmlidXRlZCBhbG9uZyB0aGUgbGluZS4gWW91ciBqb2IgYXMgdGhlIHRyYWZcdWZiMDFjIG1hbmFnZXIgaXMgdG8sIGFzIGZhc3QgYXMgcG9zc2libGUsIGVuc3VyZSB0aGF0IHRoZSB0cmFpbnMgd2lsbCBiZSBldmVubHkgZGlzdHJpYnV0ZWQgYWxvbmcgdGhlIGxpbmUgYWdhaW4uIFdyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgY3VycmVudCB0cmFpbiBwb3NpdGlvbnMsIGNhbGN1bGF0ZXMgaG93IGZhc3QgdGhpcyBjYW4gYmUgYWNoaWV2ZWQuIFlvdSBhcmUgYWxsb3dlZCB0byBvcmRlciB0aGUgdHJhaW5zIHRvIHRlbXBvcmFyaWx5IHN0b3AsIGFuZFwvb3IgY2hhbmdlIGRpcmVjdGlvbiBhbnl3aGVyZSBhbG9uZyB0aGUgbGluZS4gSWYgYSB0cmFpbiBjaGFuZ2VzIGRpcmVjdGlvbiwgaXQgd2lsbCBtb3ZlIGZyb20gb25lIHJhaWwgdG8gdGhlIG90aGVyLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA4XC9zcy5wbmdcIiBzdHlsZT1cImhlaWdodDoxNjZweDsgd2lkdGg6NDI2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDE6IEJvdGggcmFpbHMgaGF2ZSB0aGUgbGVuZ3RoIDEwMC4gSW4gdGhlIHVwcGVyIGV4YW1wbGUgdGhlIHRyYWlucyBhcmUgcG9zaXRpb25lZCBhdCA1IChkaXJlY3Rpb24gcmlnaHQpLCAzNSAobGVmdCksIDQ2IChsZWZ0KSwgNzUgKGxlZnQpIGFuZCA4NSAocmlnaHQpLiBPbmUgd2F5IHRvIG1ha2UgdGhlIHRyYWlucyBldmVubHkgZGlzdHJpYnV0ZWQgaXMgZm9yIHRoZSB0cmFpbiBhdCBwb3NpdGlvbiA0NiB0byB0cmF2ZWwgb25lIHVuaXQgdG8gdGhlIGxlZnQgYW5kIHRoZW4gY2hhbmdlIGRpcmVjdGlvbi4gVGhpcyB0YWtlcyBvbmUgdGltZSB1bml0LiBIb3dldmVyLCB0aGlzIGlzIG5vdCB0aGUgb3B0aW1hbCBzb2x1dGlvbjsgc2VlIEV4YW1wbGUmbmJzcDtiZWxvdy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBpbiB0aGUgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSwgdGhlIGxlbmd0aCBtIG9mIHRoZSBzdWJ3YXkgcmFpbHMsIGFuZCB0aGUgbnVtYmVyIG4gb2YgdHJhaW5zIG9uIHRoZSBsaW5lLiBUaGVuIGZvbGxvd3MgbiBsaW5lcyBlYWNoIGRlc2NyaWJpbmcgdGhlIGN1cnJlbnQgcG9zaXRpb24gb2YgYSB0cmFpbi4gVGhpcyB3aWxsIGJlIGdpdmVuIGFzIGFuIGludGVnZXIgeDxzdWI+aTxcL3N1Yj4gYW5kIGEgZGlyZWN0aW9uIChMIGZvciBsZWZ0LCBSIGZvciByaWdodCksIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4mbmJzcDsoMTAwICZsZTsgbSAmbGU7IDEwMCwwMDAsMDAwLCAxICZsZTsgbiAmbGU7IDEwMCwwMDAgMCAmbGU7IHg8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyBtKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IGEgc2luZ2xlIGxpbmUgdG8gc3RhbmRhcmQgb3V0cHV0LCBjb250YWluaW5nIHRoZSBzaG9ydGVzdCB0aW1lIGl0IHRha2VzIHRvIG1ha2UgdGhlIHRyYWlucyBldmVubHkgZGlzdHJpYnV0ZWQuIFlvdXIgcHJvZ3JhbSBzaG91bGQgaGF2ZSBhbiBhYnNvbHV0ZSBwcmVjaXNpb24gZXJyb3Igb2YgYXQgbW9zdCAxMDxzdXA+LTY8XC9zdXA+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 3번