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

문제

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

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

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

  • 자전거는 앞으로 가거나 그 자리에 서있을 수 있다. 뒤로는 갈 수 없다. 자전거는 최대 속도가 없다. 
  • 자전거는 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+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWIzYzRcdWNjMjlcdWM5YzBcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWMxNGJcdWM5ZjggXHVjOWRjXHViOWFjXHViODVjIFx1YmMxOFx1YzYyY1x1YjliY1x1ZDU3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzY0MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkN5Y2xpbmciLCJkZXNjcmlwdGlvbiI6IjxwPk9uIGEgYmljeWNsZSB0cmlwIHRocm91Z2ggdGhlIGNpdHksIGEgc2lnbmlcdWZiMDFjYW50IGFtb3VudCBvZiB0aW1lIGlzIHNwZW50IHdhaXRpbmcgZm9yIHRyYWZcdWZiMDFjIGxpZ2h0cy4gSWYgb25seSB5b3UgY291bGQgcmVkdWNlIHRoaXMgbG9zdCB0aW1lLCBtYXliZSB5b3Ugd291bGQgXHVmYjAxbmFsbHkgbWFuYWdlIHRvIGdldCB0byBjbGFzcyBpbiB0aW1lIGZvciB0aGUgXHVmYjAxcnN0IGxlY3R1cmUuPFwvcD5cclxuXHJcbjxwPk5vdGUgdGhhdCB0aGUgYW1vdW50IG9mIHRpbWUgbG9zdCBvbiBhIHJlZCB0cmFmXHVmYjAxYyBsaWdodCBpcyBtb3JlIHRoYW4ganVzdCB0aGUgdGltZSBzcGVudCBzdGFuZGluZyBzdGlsbCBhdCB0aGUgbGlnaHQuIEFmdGVyIHRoZSBsaWdodCB0dXJucyBncmVlbiwgYWRkaXRpb25hbCB0aW1lIGlzIGxvc3Qgd2hpbGUgdGhlIGJpY3ljbGUgYWNjZWxlcmF0ZXMuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgcHJvYmxlbSwgd2UgYXNzdW1lIGEgdGhlb3JldGljYWwgbW9kZWwgb2YgYSBiaWN5Y2xlIHRyaXAsIGJhc2VkIG9uIHRoZSBmb2xsb3dpbmcgcnVsZXM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIGJpY3ljbGUgbW92ZXMgZm9yd2FyZCBvciBzdGFuZHMgc3RpbGwsIGJ1dCBpdCBuZXZlciBtb3ZlcyBiYWNrd2FyZHMuIFRoZSBiaWN5Y2xlIGRvZXMgbm90IGhhdmUgYSBtYXhpbXVtIHNwZWVkLCBidXQgeW91IG1heSByZXN0IGFzc3VyZWQgdGhhdCByZWxhdGl2aXN0aWMgZWZmZWN0cyB3aWxsIG5vdCBiZSBpbnZvbHZlZCBpbiB0aGlzIHByb2JsZW0uPFwvbGk+XHJcblx0PGxpPlRoZSBiaWN5Y2xlIGNhbiBpbmNyZWFzZSBzcGVlZCBhdCBhIG1heGltdW0gYWNjZWxlcmF0aW9uIG9mIDAuNSBtZXRlcnMgcGVyIHNlY29uZCBwZXIgc2Vjb25kLjxcL2xpPlxyXG5cdDxsaT5UaGUgYmljeWNsZSBjYW4gaW5zdGFudGFuZW91c2x5IHJlZHVjZSBpdHMgc3BlZWQgdG8gYW55IHZhbHVlIGJldHdlZW4gemVybyBhbmQgdGhlIGN1cnJlbnQgc3BlZWQuPFwvbGk+XHJcblx0PGxpPlRoZSBiaWN5Y2xlIGNhbm5vdCBnbyB0aHJvdWdoIGEgcmVkIGxpZ2h0LjxcL2xpPlxyXG5cdDxsaT5FYWNoIHRyYWZcdWZiMDFjIGxpZ2h0IHR1cm5zIHJlZCBhbmQgZ3JlZW4gYWNjb3JkaW5nIHRvIGEgXHVmYjAxeGVkLCBjb250aW51b3VzbHkgcmVwZWF0aW5nIHJoeXRobS4gKFRoZXNlIHRyYWZcdWZiMDFjIGxpZ2h0cyBkb24mcnNxdW87dCB0dXJuIHllbGxvdy4pPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SXQgc2hvdWxkIGJlIG9idmlvdXMgdGhhdCB0aGUgdGhlb3JldGljYWwgbW9kZWwgZGV2aWF0ZXMgZnJvbSByZWFsaXR5IGluIHNldmVyYWwgd2F5cy4gRm9yIGV4YW1wbGUsIER1dGNoIGN5Y2xpc3RzIGhhcmRseSBldmVyIHN0b3AgZm9yIHJlZCBsaWdodHMuIEFsc28sIHRoZSBtb2RlbGxlZCBiaWN5Y2xlIGNhbiBkZWNlbGVyYXRlIGF0IGFuIGluXHVmYjAxbml0ZSByYXRlLCB3aGlsZSBtb3N0IHN0dWRlbnQmcnNxdW87cyBiaWtlcyBkbyBub3QgaGF2ZSBhbnkgYnJha2luZyBjYXBhYmlsaXR5IHRvIHNwZWFrIG9mLiBXZSBpZ25vcmUgdGhlc2UgZGlmZmVyZW5jZXMgZm9yIG5vdyBhbmQgZm9jdXMgb24gdGhlIHRoZW9yeS48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBzdGFuZGluZyB3aXRoIHlvdXIgYmlrZSBhdCBwb2ludCBYID0gMCBhdCB0aW1lIFQgPSAwIHdpdGggemVybyBzcGVlZC48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBpbiBhbiBlbm9ybW91cyBodXJyeSBhbmQgd291bGQgbGlrZSB0byBhcnJpdmUgYXQgcG9pbnQgWCA9IFg8c3ViPmRlc3Q8XC9zdWI+IGFzIHNvb24gYXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBcdWZiMDFuZCBhIHBhdHRlcm4gb2YgYWNjZWxlcmF0aW5nIGFuZCBicmFraW5nIHN1Y2ggdGhhdCB5b3Ugc2FmZWx5IHBhc3MgYWxsIHRyYWZcdWZiMDFjIGxpZ2h0cyBhbmQgYXJyaXZlIGluIFg8c3ViPmRlc3Q8XC9zdWI+IGF0IHRoZSBlYXJsaWVzdCBwb3NzaWJsZSB0aW1lLjxcL3A+XHJcblxyXG48cD5JdCBpcyBhbGxvd2VkIHRvIGJyYWtlIGFuZFwvb3Igc3RvcCBhdCBhbnkgcG9pbnQgZHVyaW5nIHRoZSB0cmlwLCBpbmNsdWRpbmcgKG9mIGNvdXJzZSkgZm9yIHJlZCB0cmFmXHVmYjAxYyBsaWdodHMuIEhvd2V2ZXIsIGl0IG1heSBiZSBtb3JlIGVmXHVmYjAxY2llbnQgdG8gXHVmYjAxZ3VyZSBvdXQgc29tZSB3YXkgaW4gd2hpY2ggeW91IGNhbiBjeWNsZSBwYXN0IHRoZSB0cmFmXHVmYjAxYyBsaWdodHMgd2hpbGUgdGhleSBhcmUgZ3JlZW4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgZm9yIGVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHRoZSBmb2xsb3dpbmcgaXRlbXM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QSBsaW5lIGNvbnRhaW5pbmcgYSBcdWZiMDJvYXRpbmcgcG9pbnQgbnVtYmVyIFg8c3ViPmRlc3Q8XC9zdWI+IGFuZCBhbiBpbnRlZ2VyIEwuIFg8c3ViPmRlc3Q8XC9zdWI+IGlzIHRoZSB0b3RhbCBkaXN0YW5jZSB0byB0cmF2ZWwgaW4gbWV0ZXJzICgxICZsZTsgWDxzdWI+ZGVzdDxcL3N1Yj4gJmxlOyAxMDAwMCk7PFwvbGk+XHJcblx0PGxpPkwgaXMgdGhlIG51bWJlciBvZiB0cmFmXHVmYjAxYyBsaWdodHMgdG8gcGFzcyAoMCAmbGU7IEwgJmxlOyAxMCkuPFwvbGk+XHJcblx0PGxpPkwgbGluZXMgZGVzY3JpYmluZyB0aGUgdHJhZlx1ZmIwMWMgbGlnaHRzLCBsaXN0ZWQgaW4gb3JkZXIgb2YgaW5jcmVhc2luZyBYIHBvc2l0aW9uLiBFYWNoIG9mIHRoZXNlIGxpbmVzIGNvbnRhaW5zIDMgXHVmYjAyb2F0aW5nIHBvaW50IG51bWJlcnM6XHJcblx0PHVsPlxyXG5cdFx0PGxpPlg8c3ViPmk8XC9zdWI+LCB0aGUgcG9zaXRpb24gb2YgdGhlIHRyYWZcdWZiMDFjIGxpZ2h0IGluIG1ldGVycyBmcm9tIHRoZSBzdGFydCAoMCAmbHQ7IFg8c3ViPmk8XC9zdWI+ICZsdDsgWDxzdWI+ZGVzdDxcL3N1Yj4pOzxcL2xpPlxyXG5cdFx0PGxpPlI8c3ViPmk8XC9zdWI+LCB0aGUgZHVyYXRpb24gb2YgZWFjaCByZWQtbGlnaHQgcGVyaW9kIG9mIHRoaXMgdHJhZlx1ZmIwMWMgbGlnaHQgaW4gc2Vjb25kcyAoMTAgJmxlOyBSPHN1Yj5pPFwvc3ViPiAmbGU7IDUwMCk7PFwvbGk+XHJcblx0XHQ8bGk+RzxzdWI+aTxcL3N1Yj4sIHRoZSBkdXJhdGlvbiBvZiBlYWNoIGdyZWVuLWxpZ2h0IHBlcmlvZCBvZiB0aGlzIHRyYWZcdWZiMDFjIGxpZ2h0IGluIHNlY29uZHMgKDEwICZsZTsgRzxzdWI+aTxcL3N1Yj4gJmxlOyA1MDApLjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkFsbCB0cmFmXHVmYjAxYyBsaWdodHMgdHVybiByZWQgYXQgdGltZSBUID0gMC48XC9wPlxyXG5cclxuPHA+VHJhZlx1ZmIwMWMgbGlnaHQgaSB0dXJucyBncmVlbiBmb3IgdGhlIFx1ZmIwMXJzdCB0aW1lIGF0IFQgPSBSPHN1Yj5pPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+VGhlcmUgaXMgbmV2ZXIgbW9yZSB0aGFuIG9uZSB0cmFmXHVmYjAxYyBsaWdodCBpbiB0aGUgc2FtZSBwb3NpdGlvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHdyaXRlIG9uZSBsaW5lIG9mIG91dHB1dCBjb250YWluaW5nIGEgXHVmYjAyb2F0aW5nIHBvaW50IG51bWJlcjogdGhlIGVhcmxpZXN0IHRpbWUgYXQgd2hpY2ggdGhlIGN5Y2xpc3QgY2FuIHJlYWNoIHRoZSBkZXN0aW5hdGlvbi48XC9wPlxyXG5cclxuPHA+VGhlIGFuc3dlciBzaG91bGQgYmUgcm91bmRlZCB0byAzIGRpZ2l0cyBhZnRlciB0aGUgZGVjaW1hbCBwb2ludC48XC9wPlxyXG5cclxuPHA+VGhlIHRlc3QgY2FzZXMgd2lsbCBiZSBzdWNoIHRoYXQgdmVyeSBzbWFsbCBpbmFjY3VyYWNpZXMgd2lsbCBub3QgY2F1c2UgZXJyb3JzIGluIHRoZSBcdWZiMDFuYWwgYW5zd2VyIGFmdGVyIHJvdW5kaW5nLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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

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