시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 240 140 127 58.796%

문제

농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고를 방지하기 위해 존은 각 횡단보도에 신호등을 설치해 놓았다. 그러던 어느 날, 강력한 뇌우로 인해 몇몇 신호등이 망가졌다. 존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다. 이번에도 우리가 존을 도와주자.

입력

첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.

출력

정상적으로 작동하는 연속 K개의 신호등이 존재하려면 최소 몇 개의 신호등을 수리해야 하는지 출력한다.

예제 입력 1

10 6 5
2
10
1
5
9

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjE0NDY1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDUiLCJkZXNjcmlwdGlvbiI6IjxwPjxhIGhyZWY9XCJodHRwczpcL1wvd3d3LmFjbWljcGMubmV0XC9wcm9ibGVtXC8xNDQ2OFwiPlx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NTggXHViMThkXHVjN2E1XHVjNWQwIFx1YzZkMFx1ZDYxNSBcdWFlMzhcdWM3NzQgXHVjNzg4XHViMmU0PFwvYT5cdWFjZTAgXHVkNTg4XHVjOWMwXHViOWNjLCBcdWFlMzhcdWM3NDAgXHVhZGY4XHViZmQwXHViOWNjXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVhZGY4IFx1YzYwNlx1YzVkMCBcdWM3N2NcdWM3OTBcdWQ2MTUgXHVhZTM4XHVjNzc0IFx1Yzc4OFx1YjI5NFx1YjM3MCwgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM3NDAgXHVkNmExXHViMmU4XHViY2Y0XHViM2M0IE4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMClcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhZDUwXHVkMWI1XHVjMGFjXHVhY2UwXHViOTdjIFx1YmMyOVx1YzljMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODc0XHVjNzQwIFx1YWMwMSBcdWQ2YTFcdWIyZThcdWJjZjRcdWIzYzRcdWM1ZDAgXHVjMmUwXHVkNjM4XHViNGYxXHVjNzQ0IFx1YzEyNFx1Y2U1OFx1ZDU3NCBcdWIxOTNcdWM1NThcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjM1OCBcdWM1YjRcdWIyOTAgXHViMGEwLCBcdWFjMTVcdWI4MjVcdWQ1NWMgXHViMWNjXHVjNmIwXHViODVjIFx1Yzc3OFx1ZDU3NCBcdWJhODdcdWJhODcgXHVjMmUwXHVkNjM4XHViNGYxXHVjNzc0IFx1YjlkZFx1YWMwMFx1Yzg0Y1x1YjJlNC4gXHVjODc0XHVjNzQwIFx1YzVmMFx1YzE4ZFx1ZDU1YyBLXHVhYzFjXHVjNzU4IFx1YzJlMFx1ZDYzOFx1YjRmMVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIzYzRcdWI4NWQgXHVjMmUwXHVkNjM4XHViNGYxXHVjNzQ0IFx1YzIxOFx1YjlhY1x1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1Yzc3NFx1YmM4OFx1YzVkMFx1YjNjNCBcdWM2YjBcdWI5YWNcdWFjMDAgXHVjODc0XHVjNzQ0IFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgTiwgSywgQiAoMSAmbGU7IEIsSyAmbGU7IE4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBCXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNlMFx1YzdhNVx1YjA5YyBcdWMyZTBcdWQ2MzhcdWI0ZjFcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjODE1XHVjMGMxXHVjODAxXHVjNzNjXHViODVjIFx1Yzc5MVx1YjNkOVx1ZDU1OFx1YjI5NCBcdWM1ZjBcdWMxOGQgS1x1YWMxY1x1Yzc1OCBcdWMyZTBcdWQ2MzhcdWI0ZjFcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViODI0XHViYTc0IFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YzJlMFx1ZDYzOFx1YjRmMVx1Yzc0NCBcdWMyMThcdWI5YWNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNDQ2NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldoeSBEaWQgdGhlIENvdyBDcm9zcyB0aGUgUm9hZCBJSSAoU2lsdmVyKSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGxvbmcgcm9hZCB0aHJvdWdoIEZhcm1lciBKb2huJiMzOTtzIGZhcm0gaGFzJm5ic3A7TiZuYnNwO2Nyb3Nzd2Fsa3MgYWNyb3NzIGl0LCBjb252ZW5pZW50bHkgbnVtYmVyZWQmbmJzcDsxJmhlbGxpcDtOJm5ic3A7KDEgJmxlOyBOICZsZTsgMTAwLDAwMCkuIFRvIGFsbG93IGNvd3MgdG8gY3Jvc3MgYXQgdGhlc2UgY3Jvc3N3YWxrcywgRkogaW5zdGFsbHMgZWxlY3RyaWMgY3Jvc3Npbmcgc2lnbmFscywgd2hpY2ggbGlnaHQgdXAgd2l0aCBhIGdyZWVuIGNvdyBpY29uIHdoZW4gaXQgaXMgb2sgZm9yIHRoZSBjb3cgdG8gY3Jvc3MsIGFuZCByZWQgb3RoZXJ3aXNlLiBVbmZvcnR1bmF0ZWx5LCBhIGxhcmdlIGVsZWN0cmljYWwgc3Rvcm0gaGFzIGRhbWFnZWQgc29tZSBvZiBoaXMgc2lnbmFscy4gR2l2ZW4gYSBsaXN0IG9mIHRoZSBkYW1hZ2VkIHNpZ25hbHMsIHBsZWFzZSBjb21wdXRlIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzaWduYWxzIHRoYXQgRkogbmVlZHMgdG8gcmVwYWlyIGluIG9yZGVyIGZvciB0aGVyZSB0byBleGlzdCBzb21lIGNvbnRpZ3VvdXMgYmxvY2sgb2YgYXQgbGVhc3QmbmJzcDtLJm5ic3A7d29ya2luZyBzaWduYWxzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMmbmJzcDtOLCZuYnNwO0ssIGFuZCZuYnNwO0ImbmJzcDsoMSAmbGU7IEIsSyAmbGU7IE4pLiBUaGUgbmV4dCZuYnNwO0ImbmJzcDtsaW5lcyBlYWNoIGRlc2NyaWJlIHRoZSBJRCBudW1iZXIgb2YgYSBicm9rZW4gc2lnbmFsLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBsZWFzZSBjb21wdXRlIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzaWduYWxzIHRoYXQgbmVlZCB0byBiZSByZXBhaXJlZCBpbiBvcmRlciBmb3IgdGhlcmUgdG8gYmUgYSBjb250aWd1b3VzIGJsb2NrIG9mJm5ic3A7SyB3b3JraW5nIHNpZ25hbHMgc29tZXdoZXJlIGFsb25nIHRoZSByb2FkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2016-2017 Season > USACO 2017 February Contest > Silver 2번

  • 문제의 오타를 찾은 사람: jason9319
  • 문제를 번역한 사람: jh05013