시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB133594283472.270%

문제

숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10)

이미지 I는 크기가 R × C인 2차원 픽셀이다. (3 ≤ R ≤ 40, 3 ≤ C ≤ 40) 각 픽셀은 어두운 정도 V를 나타낸다. (0 ≤ V ≤ 255)

중앙 필터는 이미지에 있는 노이즈를 제거하는 필터이다. 필터의 크기는 3 × 3이고, 이미지의 중앙값을 찾으면서 잡음을 제거한다.

예를 들어, 아래와 같은 6 × 5 이미지가 있다.

필터링된 이미지의 크기는 4 × 3이고, 아래와 같다.

가장 왼쪽 윗 행에 필터를 두고, 오른쪽으로 움직이면서 중앙값을 찾는다. 한 행을 모두 이동했으면, 다음 행으로 이동해 다시 중앙값을 찾는다. 아래와 같은 순서를 가진다.

위의 그림에서 각각의 중앙값은 36, 36, 21이 된다. 이 값은 필터링된 이미지 J의 첫 행과 같다. 

이미지 I가 주어졌을 때, 필터링 된 이미지 J를 구하고, 값이 T보다 크거나 같은 픽셀의 수를 구하는 프로그램을 작성하시오.

예를 들어, T = 40일 때, 위의 예에서 정답은 7이다. 

입력

첫째 줄에 이미지의 크기 R과 C가 주어진다. 그 다음 R개의 각 줄에는 C개의 픽셀 값이 주어진다. 마지막 줄에는 T값이 주어진다.

출력

첫째 줄에 필터링 된 이미지 J의 각 픽셀 값 중에서 T보다 크거나 같은 것의 개수를 출력한다.

예제 입력 1

6 5
49 36 73 62 21
27 88 14 11 12
99 18 36 91 21
45 96 72 12 10
12 48 49 75 56
12 15 48 86 78
40

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjE4OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NDRcdWQxMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzIyYlx1Yzc5MCA5XHVhYzFjXHVhYzAwIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1Yzc3NFx1YjA5OCBcdWIwYjRcdWI5YmNcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjODE1XHViODJjXHViNDE4XHVjNWI0IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YzkxMVx1YzU1OVx1YWMxMlx1Yzc0MCBcdWIyZTRcdWMxMmYgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMSwgMywgNCwgMSwgMiwgNiwgOCwgNCwgMTBcdWM3NTggXHVjOTExXHVjNTU5XHVhYzEyXHVjNzQwIDRcdWM3NzRcdWIyZTQuICgxICZsZTsgMSAmbGU7IDIgJmxlOyAzICZsZTsgNCAmbGU7IDQgJmxlOyA2ICZsZTsgOCAmbGU7IDEwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWJiZjhcdWM5YzAgSVx1YjI5NCBcdWQwNmNcdWFlMzBcdWFjMDAgUiZuYnNwOyZ0aW1lczsgQ1x1Yzc3OCAyXHVjYzI4XHVjNmQwIFx1ZDUzZFx1YzE0MFx1Yzc3NFx1YjJlNC4gKDMgJmxlOyBSICZsZTsgNDAsIDMgJmxlOyBDICZsZTsgNDApIFx1YWMwMSBcdWQ1M2RcdWMxNDBcdWM3NDAgXHVjNWI0XHViNDUwXHVjNmI0IFx1YzgxNVx1YjNjNCBWXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gKDAgJmxlOyBWICZsZTsgMjU1KTxcL3A+XHJcblxyXG48cD5cdWM5MTFcdWM1NTkgXHVkNTQ0XHVkMTMwXHViMjk0IFx1Yzc3NFx1YmJmOFx1YzljMFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMTc4XHVjNzc0XHVjOTg4XHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YjI5NCBcdWQ1NDRcdWQxMzBcdWM3NzRcdWIyZTQuIFx1ZDU0NFx1ZDEzMFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgMyZuYnNwOyZ0aW1lczsgM1x1Yzc3NFx1YWNlMCwgXHVjNzc0XHViYmY4XHVjOWMwXHVjNzU4IFx1YzkxMVx1YzU1OVx1YWMxMlx1Yzc0NCBcdWNjM2VcdWM3M2NcdWJhNzRcdWMxMWMgXHVjN2ExXHVjNzRjXHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCA2Jm5ic3A7JnRpbWVzOyA1IFx1Yzc3NFx1YmJmOFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZmlsdGVyMS5naWZcIiBzdHlsZT1cImhlaWdodDoxNjBweDsgd2lkdGg6MjAwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkNTQ0XHVkMTMwXHViOWMxXHViNDFjIFx1Yzc3NFx1YmJmOFx1YzljMFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgNCZuYnNwOyZ0aW1lczsgM1x1Yzc3NFx1YWNlMCwgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9maWx0ZXIyLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjExMHB4OyB3aWR0aDoxNTBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YzcxNyBcdWQ1ODlcdWM1ZDAgXHVkNTQ0XHVkMTMwXHViOTdjIFx1YjQ1MFx1YWNlMCwgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YmE3NFx1YzExYyBcdWM5MTFcdWM1NTlcdWFjMTJcdWM3NDQgXHVjYzNlXHViMjk0XHViMmU0LiBcdWQ1NWMgXHVkNTg5XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM3NzRcdWIzZDlcdWQ1ODhcdWM3M2NcdWJhNzQsIFx1YjJlNFx1Yzc0YyBcdWQ1ODlcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTc0IFx1YjJlNFx1YzJkYyBcdWM5MTFcdWM1NTlcdWFjMTJcdWM3NDQgXHVjYzNlXHViMjk0XHViMmU0LiBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzIxY1x1YzExY1x1Yjk3YyBcdWFjMDBcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZmlsdGVyMy5naWZcIiBzdHlsZT1cImhlaWdodDoxNjBweDsgd2lkdGg6NDYwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWFjMDFcdWFjMDFcdWM3NTggXHVjOTExXHVjNTU5XHVhYzEyXHVjNzQwIDM2LCAzNiwgMjFcdWM3NzQgXHViNDFjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIFx1ZDU0NFx1ZDEzMFx1YjljMVx1YjQxYyBcdWM3NzRcdWJiZjhcdWM5YzAgSlx1Yzc1OCBcdWNjYWIgXHVkNTg5XHVhY2ZjIFx1YWMxOVx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViYmY4XHVjOWMwIElcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNTQ0XHVkMTMwXHViOWMxIFx1YjQxYyBcdWM3NzRcdWJiZjhcdWM5YzAgSlx1Yjk3YyBcdWFkNmNcdWQ1NThcdWFjZTAsIFx1YWMxMlx1Yzc3NCBUXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVkNTNkXHVjMTQwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgVCA9IDQwXHVjNzdjIFx1YjU0YywgXHVjNzA0XHVjNzU4IFx1YzYwOFx1YzVkMFx1YzExYyBcdWM4MTVcdWIyZjVcdWM3NDAgN1x1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzc0XHViYmY4XHVjOWMwXHVjNzU4IFx1ZDA2Y1x1YWUzMCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFJcdWFjMWNcdWM3NTggXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBDXHVhYzFjXHVjNzU4IFx1ZDUzZFx1YzE0MCBcdWFjMTJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IFRcdWFjMTJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTQ0XHVkMTMwXHViOWMxIFx1YjQxYyBcdWM3NzRcdWJiZjhcdWM5YzAgSlx1Yzc1OCBcdWFjMDEgXHVkNTNkXHVjMTQwIFx1YWMxMiBcdWM5MTFcdWM1ZDBcdWMxMWMgVFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YWM4M1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE4OTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGaWx0ZXIiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBtZWRpYW4gb2YgOSBudW1iZXJzIGlzIHRoZSBmaWZ0aCBudW1iZXIgd2hlbiB0aGUgbnVtYmVycyBhcmUgYXJyYW5nZWQgaW4gZWl0aGVyIGluY3JlYXNpbmcgb3IgZGVjcmVhc2luZyBvcmRlci4gRm9yIGV4YW1wbGUsIHRoZSBtZWRpYW4gb2YgdGhlIDkgbnVtYmVycyAxLCAzLCA0LCAxLCAyLCA2LCA4LCA0LCAxMCBpcyA0IGJlY2F1c2UgMSAmbHQ7PSAxICZsdDs9IDIgJmx0Oz0gMyAmbHQ7PSA0ICZsdDs9IDQgJmx0Oz0gNiAmbHQ7PSA4ICZsdDs9IDEwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BbiBpbWFnZSBJIGlzIGEgdHdvIGRpbWVuc2lvbmFsIFIgJnRpbWVzOyBDIGFycmF5IG9mIHBpeGVscywgMyAmbHQ7PSBSICZsdDs9IDQwLCAzICZsdDs9IEMgJmx0Oz0gNDAuIEEgcGl4ZWwgaGFzIGFuIGludGVnZXIgZ3JleSBsZXZlbCB2YWx1ZSBWLCAwICZsdDs9IFYgJmx0Oz0gMjU1LiZuYnNwOzxcL3A+XHJcblxyXG48cD5NZWRpYW4gZmlsdGVyIGlzIGFuIGltYWdlIHByb2Nlc3Npbmcgb3BlcmF0aW9uIHRvIHJlbW92ZSBub2lzZS4gVGhlIGZpbHRlciBjYW4gYmUgaW1wbGVtZW50ZWQgYnkgbW92aW5nIGEgMyAmdGltZXM7IDMgd2luZG93IG92ZXIgdGhlIGltYWdlIGFuZCBmaW5kaW5nIHRoZSBtZWRpYW4gb2YgdGhlIDkgcGl4ZWwgdmFsdWVzIGNvdmVyZWQgYnkgdGhlIDMgJnRpbWVzOyAzIHdpbmRvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGdpdmVuIHRoZSA2ICZ0aW1lczsgNSBpbWFnZSZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZpbHRlcjEuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MTYwcHg7IG9wYWNpdHk6MC45OyB3aWR0aDoyMDBweFwiIFwvPjxcL3A+XHJcblxyXG48cD50aGUgNCAmdGltZXM7IDMgZmlsdGVyZWQgaW1hZ2UgaXMmbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9maWx0ZXIyLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjExMHB4OyB3aWR0aDoxNTBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3UgY2FuIGVhc2lseSBjaGVjayB0aGF0IGFzIHRoZSAzICZ0aW1lczsgMyB3aW5kb3cgbW92ZXMgYWxvbmcgdGhlIHRvcCByb3cgZnJvbSBsZWZ0IHRvIHJpZ2h0LCB0aGUgdGhyZWUgd2luZG93IGNvbnRlbnRzIGFyZSBhcyBzaG93biBiZWxvdyAodGhlIGJvdW5kYXJpZXMgb2YgdGhlIDMgJnRpbWVzOyAzIHdpbmRvdyBhcmUgc2hvd24gdmlhIHRoaWNrIGxpbmVzKSZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZpbHRlcjMuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MTYwcHg7IHdpZHRoOjQ2MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBjb3JyZXNwb25kaW5nIG1lZGlhbnMgZm9yIHRoZXNlIHBvc2l0aW9ucyBvZiB0aGUgMyAmdGltZXM7IDMgd2luZG93cyBhcmUgMzYsIDM2IGFuZCAyMSByZXNwZWN0aXZlbHk7IGhlbmNlIHRoZXkgY29uc3RpdHV0ZSB0aGUgdG9wIHJvdyBvZiB0aGUgZmlsdGVyZWQgaW1hZ2UgSi4gVGhlIHBpeGVsIHZhbHVlcyBvZiB0aGUgb3RoZXIgcm93cyBvZiB0aGUgZmlsdGVyZWQgaW1hZ2UgSiBjYW4gYmUgZm91bmQgc2ltaWxhcmx5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8gb3V0cHV0IGFuIGludGVnZXIgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBwaXhlbHMgaW4gdGhlIGZpbHRlcmVkIGltYWdlIEogd2hvc2UgdmFsdWVzIGFyZSBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gYSB0aHJlc2hvbGQgVC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIHRoZSB0aHJlc2hvbGQgVCA9IDQwLCB0aGUgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IDcgZm9yIHRoZSBhYm92ZSBleGFtcGxlIGJlY2F1c2UgdGhlcmUgYXJlIDcgcGl4ZWxzIGluIHRoZSBmaWx0ZXJlZCBpbWFnZSBKIHdob3NlIHZhbHVlcyBhcmUgbGFyZ2VyIHRoYW4gb3IgZXF1YWwgdG8gVC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBSICsgMiBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIHR3byBpbnRlZ2VycyBSICh0aGUgbnVtYmVyIG9mIHJvd3MpIGFuZCBDICh0aGUgbnVtYmVyIG9mIGNvbHVtbnMpIHNlcGFyYXRlZCBieSBhIGJsYW5rLiBUaGUgc3Vic2VxdWVudCBSIGxpbmVzIGNvbnRhaW4gdGhlIGltYWdlOiBlYWNoIGxpbmUgY29udGFpbnMgQyBwaXhlbCB2YWx1ZXMsIHdpdGggYSBzaW5nbGUgYmxhbmsgYmV0d2VlbiB0d28gYWRqYWNlbnQgcGl4ZWwgdmFsdWVzLiBUaGUgbGFzdCBsaW5lIGNvbnRhaW5zIHRoZSBzaW5nbGUgaW50ZWdlciBULCB0aGUgdGhyZXNob2xkIHZhbHVlLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIsIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgcGl4ZWxzIGluIHRoZSBmaWx0ZXJlZCBpbWFnZSBKIHdob3NlIHZhbHVlcyBhcmUgbGFyZ2VyIHRoYW4gb3IgZXF1YWwgdG8gdGhlIHRocmVzaG9sZC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > National Olympiad in Informatics (Singapore) > NOI 2003 1번

  • 문제를 번역한 사람: author6