시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 0 0 0.000%

문제

도시에서 자전거를 탈 때, 교통 신호를 기다리는 시간은 큰 비중을 차지한다. 학교에 자전거를 타고 등교를 하려면 이 시간을 줄여야 한다.

교통 신호 때문에 낭비하는 시간은 빨간불을 기다리는 시간보다 더 많은 시간을 포함한다. 불이 초록불로 바뀌었을 때, 자전거를 가속하는 시간도 필요하기 때문이다.

자전거 여행을 아래와 같이 모델링할 수 있다.

  • 자전거는 앞으로 가거나 그 자리에 서있을 수 있다. 뒤로는 갈 수 없다. 자전거는 최대 속도가 없다. 
  • 자전거는 1초에 최대 초속 0.5미터 만큼 가속할 수 있다. (가속도가 최대 0.5m/s^2 이다)
  • 자전거는 현재 속도와 0 사이의 속도중 하나로 즉시 감속할 수 있다.
  • 자전거는 빨간불일 때 앞으로 갈 수 없다.
  • 신호등은 빨간불과 초록불이 번갈아가면서 특정 주기를 가지고 바뀐다. (노란불로 바뀌지 않는다)

위의 모델은 이론상의 모델로 실제 현상과는 많이 다르다.

상근이는 시간 T= 0에 점 X = 0에 속도 0으로 서있다. 상근이는 자전거를 타고 X=Xdest에 최대한 빨리 도착하려고 한다. 모든 신호등을 안전하게 통과하고 Xdest에 최대한 빠르게 도착하는 가속과 감속 패턴을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 도착지의 좌표 Xdest와 신호등의 개수 L이 주어진다. (1 ≤ Xdest ≤ 10000, 0 ≤ L ≤ 10)

다음 L개 줄에는 신호등의 정보가 X좌표가 증가하는 순으로 주어진다. 신호등 정보는 신호등의 위치 Xi (0 < Xi < Xdest), 빨간색이 지속되는 시간 Ri (10 ≤ Ri ≤ 500), 초록불이 지속되는 시간 Gi (10 ≤ Gi ≤ 500)로 이루어져 있다.

모든 신호등은 T = 0일때, 빨간불로 바뀌었다. 또, 신호등 i는 T = Ri일 때, 처음으로 초록불이 된다.

두 신호등이 같은 장소에 있는 경우는 없다.

출력

각 테스트 케이스에 대해서, 도착지에 도착하는 가장 빠른 시간을 소수점 셋째 짜리로 반올림해 출력한다. 

예제 입력 1

410.0 2
200.0 15.0 15.0
225.0 31.0 10.0
410.0 2
200.0 15.0 15.0
225.0 35.1 15.0
410.0 2
200.0 15.0 15.0
225.0 45.0 10.0

예제 출력 1

41.497
52.623
57.213
W3sicHJvYmxlbV9pZCI6IjM2NDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWM4MDRcdWFjNzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNjNFx1YzJkY1x1YzVkMFx1YzExYyBcdWM3OTBcdWM4MDRcdWFjNzBcdWI5N2MgXHVkMGM4IFx1YjU0YywgXHVhZDUwXHVkMWI1IFx1YzJlMFx1ZDYzOFx1Yjk3YyBcdWFlMzBcdWIyZTRcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIFx1ZDA3MCBcdWJlNDRcdWM5MTFcdWM3NDQgXHVjYzI4XHVjOWMwXHVkNTVjXHViMmU0LiBcdWQ1NTlcdWFkNTBcdWM1ZDAgXHVjNzkwXHVjODA0XHVhYzcwXHViOTdjIFx1ZDBjMFx1YWNlMCBcdWI0ZjFcdWFkNTBcdWI5N2MgXHVkNTU4XHViODI0XHViYTc0IFx1Yzc3NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjOTA0XHVjNWVjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZDUwXHVkMWI1IFx1YzJlMFx1ZDYzOCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViMGFkXHViZTQ0XHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWJlNjhcdWFjMDRcdWJkODhcdWM3NDQgXHVhZTMwXHViMmU0XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1YmNmNFx1YjJlNCBcdWIzNTQgXHViOWNlXHVjNzQwIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NWNcdWIyZTQuIFx1YmQ4OFx1Yzc3NCBcdWNkMDhcdWI4NWRcdWJkODhcdWI4NWMgXHViYzE0XHViMDBjXHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVjNzkwXHVjODA0XHVhYzcwXHViOTdjIFx1YWMwMFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWIzYzQgXHVkNTQ0XHVjNjk0XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzkwXHVjODA0XHVhYzcwIFx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YmFhOFx1YjM3OFx1YjljMVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Yzc5MFx1YzgwNFx1YWM3MFx1YjI5NCBcdWM1NWVcdWM3M2NcdWI4NWMgXHVhYzAwXHVhYzcwXHViMDk4IFx1YWRmOCBcdWM3OTBcdWI5YWNcdWM1ZDAgXHVjMTFjXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjRhNFx1Yjg1Y1x1YjI5NCBcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVjNzkwXHVjODA0XHVhYzcwXHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWMxOGRcdWIzYzRcdWFjMDAgXHVjNWM2XHViMmU0LiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5cdWM3OTBcdWM4MDRcdWFjNzBcdWIyOTQgMVx1Y2QwOFx1YzVkMCBcdWNkNWNcdWIzMDAgXHVjZDA4XHVjMThkIDAuNVx1YmJmOFx1ZDEzMCBcdWI5Y2NcdWQwN2MgXHVhYzAwXHVjMThkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWFjMDBcdWMxOGRcdWIzYzRcdWFjMDAgXHVjZDVjXHViMzAwIDAuNW1cL3M8c3BhbiBzdHlsZT1cImZvbnQtc2l6ZToxMXB4XCI+XjI8XC9zcGFuPiZuYnNwO1x1Yzc3NFx1YjJlNCk8XC9saT5cclxuXHQ8bGk+XHVjNzkwXHVjODA0XHVhYzcwXHViMjk0IFx1ZDYwNFx1YzdhYyBcdWMxOGRcdWIzYzRcdWM2NDAgMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVjMThkXHViM2M0XHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWM5ODlcdWMyZGMgXHVhYzEwXHVjMThkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1Yzc5MFx1YzgwNFx1YWM3MFx1YjI5NCBcdWJlNjhcdWFjMDRcdWJkODhcdWM3N2MgXHViNTRjIFx1YzU1ZVx1YzczY1x1Yjg1YyBcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMmUwXHVkNjM4XHViNGYxXHVjNzQwIFx1YmU2OFx1YWMwNFx1YmQ4OFx1YWNmYyBcdWNkMDhcdWI4NWRcdWJkODhcdWM3NzQgXHViYzg4XHVhYzA4XHVjNTQ0XHVhYzAwXHViYTc0XHVjMTFjIFx1ZDJiOVx1YzgxNSBcdWM4ZmNcdWFlMzBcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YmMxNFx1YjAxMFx1YjJlNC4gKFx1YjE3OFx1Yjc4MFx1YmQ4OFx1Yjg1YyBcdWJjMTRcdWIwMGNcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0KTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWJhYThcdWIzNzhcdWM3NDAgXHVjNzc0XHViODYwXHVjMGMxXHVjNzU4IFx1YmFhOFx1YjM3OFx1Yjg1YyBcdWMyZTRcdWM4MWMgXHVkNjA0XHVjMGMxXHVhY2ZjXHViMjk0IFx1YjljZVx1Yzc3NCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMyZGNcdWFjMDQgVD0gMFx1YzVkMCBcdWM4MTAgWCA9IDBcdWM1ZDAgXHVjMThkXHViM2M0IDBcdWM3M2NcdWI4NWMgXHVjMTFjXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzkwXHVjODA0XHVhYzcwXHViOTdjIFx1ZDBjMFx1YWNlMCBYPVg8c3ViPmRlc3Q8XC9zdWI+XHVjNWQwIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWJlNjhcdWI5YWMgXHViM2M0XHVjYzI5XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYWE4XHViNGUwIFx1YzJlMFx1ZDYzOFx1YjRmMVx1Yzc0NCBcdWM1NDhcdWM4MDRcdWQ1NThcdWFjOGMgXHVkMWI1XHVhY2ZjXHVkNTU4XHVhY2UwIFg8c3ViPmRlc3Q8XC9zdWI+XHVjNWQwIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWJlNjBcdWI5NzRcdWFjOGMgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0IFx1YWMwMFx1YzE4ZFx1YWNmYyBcdWFjMTBcdWMxOGQgXHVkMzI4XHVkMTM0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1Y2MyOVx1YzljMFx1Yzc1OCBcdWM4OGNcdWQ0NWMgWDxzdWI+ZGVzdDxcL3N1Yj5cdWM2NDAgXHVjMmUwXHVkNjM4XHViNGYxXHVjNzU4IFx1YWMxY1x1YzIxOCBMXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBYPHN1Yj5kZXN0PFwvc3ViPiZuYnNwOyZsZTsgMTAwMDAsIDAgJmxlOyBMICZsZTsgMTApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBMXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyZTBcdWQ2MzhcdWI0ZjFcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFhcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzJlMFx1ZDYzOFx1YjRmMSBcdWM4MTVcdWJjZjRcdWIyOTQgXHVjMmUwXHVkNjM4XHViNGYxXHVjNzU4IFx1YzcwNFx1Y2U1OCBYPHN1Yj5pPFwvc3ViPiZuYnNwOygwICZsdDsgWDxzdWI+aTxcL3N1Yj4mbmJzcDsmbHQ7IFg8c3ViPmRlc3Q8XC9zdWI+KSwgXHViZTY4XHVhYzA0XHVjMGM5XHVjNzc0IFx1YzljMFx1YzE4ZFx1YjQxOFx1YjI5NCBcdWMyZGNcdWFjMDQgUjxzdWI+aTxcL3N1Yj4mbmJzcDsoMTAgJmxlOyBSPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsgNTAwKSwgXHVjZDA4XHViODVkXHViZDg4XHVjNzc0IFx1YzljMFx1YzE4ZFx1YjQxOFx1YjI5NCBcdWMyZGNcdWFjMDQgRzxzdWI+aTxcL3N1Yj4mbmJzcDsoMTAgJmxlOyBHPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsgNTAwKVx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjMmUwXHVkNjM4XHViNGYxXHVjNzQwIFQgPSAwXHVjNzdjXHViNTRjLCBcdWJlNjhcdWFjMDRcdWJkODhcdWI4NWMgXHViYzE0XHViMDBjXHVjNWM4XHViMmU0LiBcdWI2MTAsIFx1YzJlMFx1ZDYzOFx1YjRmMSBpXHViMjk0IFQgPSBSPHN1Yj5pPFwvc3ViPlx1Yzc3YyBcdWI1NGMsIFx1Y2M5OFx1Yzc0Y1x1YzczY1x1Yjg1YyBcdWNkMDhcdWI4NWRcdWJkODhcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjMmUwXHVkNjM4XHViNGYxXHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWM3YTVcdWMxOGNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWIzYzRcdWNjMjlcdWM5YzBcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWMxNGJcdWM5ZjggXHVjOWRjXHViOWFjXHViODVjIFx1YmMxOFx1YzYyY1x1YjliY1x1ZDU3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjQyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ3ljbGluZyIsImRlc2NyaXB0aW9uIjoiPHA+T24gYSBiaWN5Y2xlIHRyaXAgdGhyb3VnaCB0aGUgY2l0eSwgYSBzaWduaVx1ZmIwMWNhbnQgYW1vdW50IG9mIHRpbWUgaXMgc3BlbnQgd2FpdGluZyBmb3IgdHJhZlx1ZmIwMWMgbGlnaHRzLiBJZiBvbmx5IHlvdSBjb3VsZCByZWR1Y2UgdGhpcyBsb3N0IHRpbWUsIG1heWJlIHlvdSB3b3VsZCBcdWZiMDFuYWxseSBtYW5hZ2UgdG8gZ2V0IHRvIGNsYXNzIGluIHRpbWUgZm9yIHRoZSBcdWZiMDFyc3QgbGVjdHVyZS48XC9wPlxyXG5cclxuPHA+Tm90ZSB0aGF0IHRoZSBhbW91bnQgb2YgdGltZSBsb3N0IG9uIGEgcmVkIHRyYWZcdWZiMDFjIGxpZ2h0IGlzIG1vcmUgdGhhbiBqdXN0IHRoZSB0aW1lIHNwZW50IHN0YW5kaW5nIHN0aWxsIGF0IHRoZSBsaWdodC4gQWZ0ZXIgdGhlIGxpZ2h0IHR1cm5zIGdyZWVuLCBhZGRpdGlvbmFsIHRpbWUgaXMgbG9zdCB3aGlsZSB0aGUgYmljeWNsZSBhY2NlbGVyYXRlcy48XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtLCB3ZSBhc3N1bWUgYSB0aGVvcmV0aWNhbCBtb2RlbCBvZiBhIGJpY3ljbGUgdHJpcCwgYmFzZWQgb24gdGhlIGZvbGxvd2luZyBydWxlczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgYmljeWNsZSBtb3ZlcyBmb3J3YXJkIG9yIHN0YW5kcyBzdGlsbCwgYnV0IGl0IG5ldmVyIG1vdmVzIGJhY2t3YXJkcy4gVGhlIGJpY3ljbGUgZG9lcyBub3QgaGF2ZSBhIG1heGltdW0gc3BlZWQsIGJ1dCB5b3UgbWF5IHJlc3QgYXNzdXJlZCB0aGF0IHJlbGF0aXZpc3RpYyBlZmZlY3RzIHdpbGwgbm90IGJlIGludm9sdmVkIGluIHRoaXMgcHJvYmxlbS48XC9saT5cclxuXHQ8bGk+VGhlIGJpY3ljbGUgY2FuIGluY3JlYXNlIHNwZWVkIGF0IGEgbWF4aW11bSBhY2NlbGVyYXRpb24gb2YgMC41IG1ldGVycyBwZXIgc2Vjb25kIHBlciBzZWNvbmQuPFwvbGk+XHJcblx0PGxpPlRoZSBiaWN5Y2xlIGNhbiBpbnN0YW50YW5lb3VzbHkgcmVkdWNlIGl0cyBzcGVlZCB0byBhbnkgdmFsdWUgYmV0d2VlbiB6ZXJvIGFuZCB0aGUgY3VycmVudCBzcGVlZC48XC9saT5cclxuXHQ8bGk+VGhlIGJpY3ljbGUgY2Fubm90IGdvIHRocm91Z2ggYSByZWQgbGlnaHQuPFwvbGk+XHJcblx0PGxpPkVhY2ggdHJhZlx1ZmIwMWMgbGlnaHQgdHVybnMgcmVkIGFuZCBncmVlbiBhY2NvcmRpbmcgdG8gYSBcdWZiMDF4ZWQsIGNvbnRpbnVvdXNseSByZXBlYXRpbmcgcmh5dGhtLiAoVGhlc2UgdHJhZlx1ZmIwMWMgbGlnaHRzIGRvbiZyc3F1bzt0IHR1cm4geWVsbG93Lik8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JdCBzaG91bGQgYmUgb2J2aW91cyB0aGF0IHRoZSB0aGVvcmV0aWNhbCBtb2RlbCBkZXZpYXRlcyBmcm9tIHJlYWxpdHkgaW4gc2V2ZXJhbCB3YXlzLiBGb3IgZXhhbXBsZSwgRHV0Y2ggY3ljbGlzdHMgaGFyZGx5IGV2ZXIgc3RvcCBmb3IgcmVkIGxpZ2h0cy4gQWxzbywgdGhlIG1vZGVsbGVkIGJpY3ljbGUgY2FuIGRlY2VsZXJhdGUgYXQgYW4gaW5cdWZiMDFuaXRlIHJhdGUsIHdoaWxlIG1vc3Qgc3R1ZGVudCZyc3F1bztzIGJpa2VzIGRvIG5vdCBoYXZlIGFueSBicmFraW5nIGNhcGFiaWxpdHkgdG8gc3BlYWsgb2YuIFdlIGlnbm9yZSB0aGVzZSBkaWZmZXJlbmNlcyBmb3Igbm93IGFuZCBmb2N1cyBvbiB0aGUgdGhlb3J5LjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHN0YW5kaW5nIHdpdGggeW91ciBiaWtlIGF0IHBvaW50IFggPSAwIGF0IHRpbWUgVCA9IDAgd2l0aCB6ZXJvIHNwZWVkLjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGluIGFuIGVub3Jtb3VzIGh1cnJ5IGFuZCB3b3VsZCBsaWtlIHRvIGFycml2ZSBhdCBwb2ludCBYID0gWDxzdWI+ZGVzdDxcL3N1Yj4gYXMgc29vbiBhcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIFx1ZmIwMW5kIGEgcGF0dGVybiBvZiBhY2NlbGVyYXRpbmcgYW5kIGJyYWtpbmcgc3VjaCB0aGF0IHlvdSBzYWZlbHkgcGFzcyBhbGwgdHJhZlx1ZmIwMWMgbGlnaHRzIGFuZCBhcnJpdmUgaW4gWDxzdWI+ZGVzdDxcL3N1Yj4gYXQgdGhlIGVhcmxpZXN0IHBvc3NpYmxlIHRpbWUuPFwvcD5cclxuXHJcbjxwPkl0IGlzIGFsbG93ZWQgdG8gYnJha2UgYW5kXC9vciBzdG9wIGF0IGFueSBwb2ludCBkdXJpbmcgdGhlIHRyaXAsIGluY2x1ZGluZyAob2YgY291cnNlKSBmb3IgcmVkIHRyYWZcdWZiMDFjIGxpZ2h0cy4gSG93ZXZlciwgaXQgbWF5IGJlIG1vcmUgZWZcdWZiMDFjaWVudCB0byBcdWZiMDFndXJlIG91dCBzb21lIHdheSBpbiB3aGljaCB5b3UgY2FuIGN5Y2xlIHBhc3QgdGhlIHRyYWZcdWZiMDFjIGxpZ2h0cyB3aGlsZSB0aGV5IGFyZSBncmVlbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmb3IgZWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgdGhlIGZvbGxvd2luZyBpdGVtczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BIGxpbmUgY29udGFpbmluZyBhIFx1ZmIwMm9hdGluZyBwb2ludCBudW1iZXIgWDxzdWI+ZGVzdDxcL3N1Yj4gYW5kIGFuIGludGVnZXIgTC4gWDxzdWI+ZGVzdDxcL3N1Yj4gaXMgdGhlIHRvdGFsIGRpc3RhbmNlIHRvIHRyYXZlbCBpbiBtZXRlcnMgKDEgJmxlOyBYPHN1Yj5kZXN0PFwvc3ViPiAmbGU7IDEwMDAwKTs8XC9saT5cclxuXHQ8bGk+TCBpcyB0aGUgbnVtYmVyIG9mIHRyYWZcdWZiMDFjIGxpZ2h0cyB0byBwYXNzICgwICZsZTsgTCAmbGU7IDEwKS48XC9saT5cclxuXHQ8bGk+TCBsaW5lcyBkZXNjcmliaW5nIHRoZSB0cmFmXHVmYjAxYyBsaWdodHMsIGxpc3RlZCBpbiBvcmRlciBvZiBpbmNyZWFzaW5nIFggcG9zaXRpb24uIEVhY2ggb2YgdGhlc2UgbGluZXMgY29udGFpbnMgMyBcdWZiMDJvYXRpbmcgcG9pbnQgbnVtYmVyczpcclxuXHQ8dWw+XHJcblx0XHQ8bGk+WDxzdWI+aTxcL3N1Yj4sIHRoZSBwb3NpdGlvbiBvZiB0aGUgdHJhZlx1ZmIwMWMgbGlnaHQgaW4gbWV0ZXJzIGZyb20gdGhlIHN0YXJ0ICgwICZsdDsgWDxzdWI+aTxcL3N1Yj4gJmx0OyBYPHN1Yj5kZXN0PFwvc3ViPik7PFwvbGk+XHJcblx0XHQ8bGk+UjxzdWI+aTxcL3N1Yj4sIHRoZSBkdXJhdGlvbiBvZiBlYWNoIHJlZC1saWdodCBwZXJpb2Qgb2YgdGhpcyB0cmFmXHVmYjAxYyBsaWdodCBpbiBzZWNvbmRzICgxMCAmbGU7IFI8c3ViPmk8XC9zdWI+ICZsZTsgNTAwKTs8XC9saT5cclxuXHRcdDxsaT5HPHN1Yj5pPFwvc3ViPiwgdGhlIGR1cmF0aW9uIG9mIGVhY2ggZ3JlZW4tbGlnaHQgcGVyaW9kIG9mIHRoaXMgdHJhZlx1ZmIwMWMgbGlnaHQgaW4gc2Vjb25kcyAoMTAgJmxlOyBHPHN1Yj5pPFwvc3ViPiAmbGU7IDUwMCkuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+QWxsIHRyYWZcdWZiMDFjIGxpZ2h0cyB0dXJuIHJlZCBhdCB0aW1lIFQgPSAwLjxcL3A+XHJcblxyXG48cD5UcmFmXHVmYjAxYyBsaWdodCBpIHR1cm5zIGdyZWVuIGZvciB0aGUgXHVmYjAxcnN0IHRpbWUgYXQgVCA9IFI8c3ViPmk8XC9zdWI+LjxcL3A+XHJcblxyXG48cD5UaGVyZSBpcyBuZXZlciBtb3JlIHRoYW4gb25lIHRyYWZcdWZiMDFjIGxpZ2h0IGluIHRoZSBzYW1lIHBvc2l0aW9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgd3JpdGUgb25lIGxpbmUgb2Ygb3V0cHV0IGNvbnRhaW5pbmcgYSBcdWZiMDJvYXRpbmcgcG9pbnQgbnVtYmVyOiB0aGUgZWFybGllc3QgdGltZSBhdCB3aGljaCB0aGUgY3ljbGlzdCBjYW4gcmVhY2ggdGhlIGRlc3RpbmF0aW9uLjxcL3A+XHJcblxyXG48cD5UaGUgYW5zd2VyIHNob3VsZCBiZSByb3VuZGVkIHRvIDMgZGlnaXRzIGFmdGVyIHRoZSBkZWNpbWFsIHBvaW50LjxcL3A+XHJcblxyXG48cD5UaGUgdGVzdCBjYXNlcyB3aWxsIGJlIHN1Y2ggdGhhdCB2ZXJ5IHNtYWxsIGluYWNjdXJhY2llcyB3aWxsIG5vdCBjYXVzZSBlcnJvcnMgaW4gdGhlIFx1ZmIwMW5hbCBhbnN3ZXIgYWZ0ZXIgcm91bmRpbmcuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2012 C번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: mgkim011