2433번: The Sound of Silence

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	472	168	130	33.766%

문제

디지털 음악에서 소리는 대기압의 변화를 나타내는 숫자로 표현한다. 대기압의 변화는 일정한 시간 구간을 정해놓고, 연속되는 구간동안 얼마나 빠르게 변했는지를 측정한다. 이렇게 측정한 값을 샘플이라고 한다.

음성 처리에서 가장 중요한 단계는 녹음된 소리를 사일런스 기준으로 사일런스가 아닌 구간으로 나누는 작업이다. 너무 많은 조각이 나는 것을 방지 하기 위해서 사일런스는 최저값과 최고값의 차이가 c를 넘지않는 샘플 m개의 연속이라고 정의한다.

샘플 n개 이루어진 레코딩과 m과 c가 주어졌을 때, 사일런스를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 샘플의 수 n (1 ≤ n ≤ 1,000,000), m (1 ≤ m ≤ 10,000), c (0 ≤ c ≤ 10,000)가 주어진다.

둘째 줄에는 각 샘플의 값 a_i가 주어진다. (0 ≤ a_i ≤ 1,000,000 for 1 ≤ i ≤ n)

출력

max(a[i . . . i+m−1])−min(a[i . . . i+m−1]) ≤ c를 만족하는 모든 i를 오름차순으로 한 줄에 하나씩 출력한다.

만약, 주어진 입력에 사일런스가 없다면, NONE을 출력한다.

예제 입력 1

7 2 0
0 1 1 2 3 2 2

예제 출력 1

2
6

힌트

W3sicHJvYmxlbV9pZCI6IjI0MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJUaGUgU291bmQgb2YgU2lsZW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+XHViNTE0XHVjOWMwXHVkMTM4IFx1Yzc0Y1x1YzU0NVx1YzVkMFx1YzExYyBcdWMxOGNcdWI5YWNcdWIyOTQgXHViMzAwXHVhZTMwXHVjNTU1XHVjNzU4IFx1YmNjMFx1ZDY1NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMjJiXHVjNzkwXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1Y1x1YjJlNC4gXHViMzAwXHVhZTMwXHVjNTU1XHVjNzU4IFx1YmNjMFx1ZDY1NFx1YjI5NCBcdWM3N2NcdWM4MTVcdWQ1NWMgXHVjMmRjXHVhYzA0IFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWM4MTVcdWQ1NzRcdWIxOTNcdWFjZTAsIFx1YzVmMFx1YzE4ZFx1YjQxOFx1YjI5NCBcdWFkNmNcdWFjMDRcdWIzZDlcdWM1NDggXHVjNWJjXHViOWM4XHViMDk4IFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWJjYzBcdWQ1ODhcdWIyOTRcdWM5YzBcdWI5N2MgXHVjZTIxXHVjODE1XHVkNTVjXHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjZTIxXHVjODE1XHVkNTVjIFx1YWMxMlx1Yzc0NCBcdWMwZDhcdWQ1MGNcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NGNcdWMxMzEgXHVjYzk4XHViOWFjXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM5MTFcdWM2OTRcdWQ1NWMgXHViMmU4XHVhY2M0XHViMjk0IFx1YjE3OVx1Yzc0Y1x1YjQxYyBcdWMxOGNcdWI5YWNcdWI5N2MgXHVjMGFjXHVjNzdjXHViN2YwXHVjMmE0IFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWMwYWNcdWM3N2NcdWI3ZjBcdWMyYTRcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YWQ2Y1x1YWMwNFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzc0XHViMmU0LiBcdWIxMDhcdWJiMzQgXHViOWNlXHVjNzQwIFx1Yzg3MFx1YWMwMVx1Yzc3NCBcdWIwOThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YmMyOVx1YzljMCBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzBhY1x1Yzc3Y1x1YjdmMFx1YzJhNFx1YjI5NCBcdWNkNWNcdWM4MDBcdWFjMTJcdWFjZmMgXHVjZDVjXHVhY2UwXHVhYzEyXHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YWMwMCBjXHViOTdjIFx1YjExOFx1YzljMFx1YzU0YVx1YjI5NCBcdWMwZDhcdWQ1MGMgbVx1YWMxY1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWM3NzRcdWI3N2NcdWFjZTAgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwZDhcdWQ1MGMgblx1YWMxYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViODA4XHVjZjU0XHViNTI5XHVhY2ZjIG1cdWFjZmMgY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYWNcdWM3N2NcdWI3ZjBcdWMyYTRcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBkOFx1ZDUwY1x1Yzc1OCBcdWMyMTggbiZuYnNwOygxICZsZTsmbmJzcDtuICZsZTsgMSwwMDAsMDAwKSwgbSAoMSAmbGU7IG0gJmxlOyAxMCwwMDApLCBjICgwICZsZTsgYyAmbGU7IDEwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwZDhcdWQ1MGNcdWM3NTggXHVhYzEyIGE8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMCAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwIGZvciAxICZsZTsgaSAmbGU7IG4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+bWF4KGFbaSAuIC4gLiBpK20mbWludXM7MV0pJm1pbnVzO21pbihhW2kgLiAuIC4gaSttJm1pbnVzOzFdKSAmbGU7IGNcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YmFhOFx1YjRlMCBpXHViOTdjIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCwgXHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzc4NVx1YjgyNVx1YzVkMCBcdWMwYWNcdWM3N2NcdWI3ZjBcdWMyYTRcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0LCA8Y29kZT5OT05FPFwvY29kZT5cdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8aWZyYW1lIHdpZHRoPVwiNTYwXCIgaGVpZ2h0PVwiMzE1XCIgc3JjPVwiaHR0cHM6XC9cL3d3dy55b3V0dWJlLmNvbVwvZW1iZWRcL05BRXBwRlVXTGZjXCIgdGl0bGU9XCJZb3VUdWJlIHZpZGVvIHBsYXllclwiIGZyYW1lYm9yZGVyPVwiMFwiIGFsbG93PVwiYWNjZWxlcm9tZXRlcjsgYXV0b3BsYXk7IGNsaXBib2FyZC13cml0ZTsgZW5jcnlwdGVkLW1lZGlhOyBneXJvc2NvcGU7IHBpY3R1cmUtaW4tcGljdHVyZVwiIGFsbG93ZnVsbHNjcmVlbj48XC9pZnJhbWU+Iiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNDMzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIFNvdW5kIG9mIFNpbGVuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPkluIGRpZ2l0YWwgcmVjb3JkaW5nLCBzb3VuZCBpcyBkZXNjcmliZWQgYnkgYSBzZXF1ZW5jZSBvZiBudW1iZXJzIHJlcHJlc2VudGluZyB0aGUgYWlyIHByZXNzdXJlLCBtZWFzdXJlZCBhdCBhIHJhcGlkIHJhdGUgd2l0aCBhIGZpeGVkIHRpbWUgaW50ZXJ2YWwgYmV0d2VlbiBzdWNjZXNzaXZlIG1lYXN1cmVtZW50cy4gRWFjaCB2YWx1ZSBpbiB0aGUgc2VxdWVuY2UgaXMgY2FsbGVkIGEgc2FtcGxlLjxcL3A+XHJcblxyXG48cD5BbiBpbXBvcnRhbnQgc3RlcCBpbiBtYW55IHZvaWNlLXByb2Nlc3NpbmcgdGFza3MgaXMgYnJlYWtpbmcgdGhlIHJlY29yZGVkIHNvdW5kIGludG8gY2h1bmtzIG9mIG5vbi1zaWxlbmNlIHNlcGFyYXRlZCBieSBzaWxlbmNlLiBUbyBhdm9pZCBhY2NpZGVudGFsbHkgYnJlYWtpbmcgdGhlIHJlY29yZGluZyBpbnRvIHRvbyBmZXcgb3IgdG9vIG1hbnkgcGllY2VzLCB0aGUgc2lsZW5jZSBpcyBvZnRlbiBkZWZpbmVkIGFzIGEgc2VxdWVuY2Ugb2YgbSBzYW1wbGVzIHdoZXJlIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIGxvd2VzdCBhbmQgdGhlIGhpZ2hlc3QgdmFsdWUgZG9lcyBub3QgZXhjZWVkIGEgY2VydGFpbiB0cmVzaG9sZCBjLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8gZGV0ZWN0IHNpbGVuY2UgaW4gYSBnaXZlbiByZWNvcmRpbmcgb2YgbiBzYW1wbGVzIGFjY29yZGluZyB0byB0aGUgZ2l2ZW4gcGFyYW1ldGVyIHZhbHVlcyBtIGFuZCBjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGZpbGUgY29udGFpbnMgdGhyZWUgaW50ZWdlcnM6IG4gKDEgJmxlOyBuICZsZTsgMSwwMDAsMDAwKSwgdGhlIG51bWJlciBvZiBzYW1wbGVzIGluIHRoZSByZWNvcmRpbmc7IG0gKDEgJmxlOyBtICZsZTsgMTAsMDAwKSwgdGhlIHJlcXVpcmVkIGxlbmd0aCBvZiB0aGUgc2lsZW5jZTsgYW5kIGMgKDAgJmxlOyBjICZsZTsgMTAsMDAwKSwgdGhlIG1heGltYWwgbm9pc2UgbGV2ZWwgYWxsb3dlZCB3aXRoaW4gc2lsZW5jZS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIHRoZSBmaWxlIGNvbnRhaW5zIG4gaW50ZWdlcnMgYTxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCBmb3IgMSAmbGU7IGkgJmxlOyBuKSwgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXM6IHRoZSBzYW1wbGVzIGluIHRoZSByZWNvcmRpbmcuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBzaG91bGQgbGlzdCBhbGwgdmFsdWVzIG9mIGkgc3VjaCB0aGF0IG1heChhW2kgLiAuIC4gaSttJm1pbnVzOzFdKSAmbWludXM7IG1pbihhW2kgLiAuIC4gaSttJm1pbnVzOzFdKSBcdTAwMTQmbHQ7PSBjLiBUaGUgdmFsdWVzIHNob3VsZCBiZSBsaXN0ZWQgaW4gaW5jcmVhc2luZyBvcmRlciwgZWFjaCBvbiBhIHNlcGFyYXRlIGxpbmUuPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGlzIG5vIHNpbGVuY2UgaW4gdGhlIGlucHV0LCB3cml0ZSBOT05FIG9uIHRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIHRoZSBvdXRwdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2007 3번

문제를 번역한 사람: baekjoon

문제

문제

출처

ICPC

2433번 - The Sound of Silence 다국어

문제

입력

출력

제한

예제 입력 1

예제 출력 1

힌트

출처

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

문제

문제

출처

ICPC

2433번 - The Sound of Silence 다국어

문제

입력

출력

제한

예제 입력 1 복사

예제 출력 1 복사

힌트

출처

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

예제 입력 1

예제 출력 1