| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 106 | 19 | 14 | 22.581% |
На кафедре пингвиноведения Южного Антарктического университета проводятся исследования популяций пингвинов. Фотографии скоплений плотно стоящих пингвинов обрабатываются студентами. Распознавание пингвинов на снимках производится следующим образом: на фотографии выбирается характерная полоса высотой в один пиксель, каждый пиксель которой входит в изображение одного из пингвинов.
У всех пингвинов исследуемой популяции живот белый, а спина и крылья --- чёрные. Таким образом, если у пингвина на фотографии видна только спина, то на характерной полосе ему соответствует отрезок из чёрных пикселей, а если только живот, то из белых. В остальных случаях, например, когда чёрные крылья видны поверх белого живота, пингвину соответствует отрезок из чёрных и белых пикселей. Для продолжения исследований необходимо, чтобы каждому пингвину соответствовал отрезок, состоящий либо только из чёрных, либо только из белых пикселей.
Для $i$-й фотографии известно максимальное количество пингвинов $k_i,ドル изображение которых могло попасть на характерную полосу. Поэтому эту полосу пикселей необходимо заменить на упрощённую полосу той же длины, которая будет состоять не более чем из $k_i$ отрезков, каждый из которых либо полностью чёрный, либо полностью белый. Из всех возможных упрощённых полос нужно выбрать оптимальную --- то есть ту, которая получается из характерной путём изменения цвета минимального числа пикселей.
Требуется написать программу, решающую поставленную задачу.
В первой строке входных данных содержится число $t$ --- количество фотографий. Далее следуют $t$ пар строк, $i$-я пара строк описывает $i$-ю фотографию.
Первая строка описания фотографии содержит два числа: $n_i$ --- длину характерной полосы $i$-й фотографии, и $k_i$ --- максимальное количество пингвинов, которые могут быть на ней изображены ($k_i \le n_i$).
Вторая строка описания состоит из $n_i$ символов 0 и 1, где 0 обозначает чёрный, а 1 --- белый пиксель.
Выходные данные должны содержать $t$ строк, где $i$-я строка состоит из $n_i$ символов 0 и 1 и описывает упрощённую полосу, полученную из характерной полосы $i$-й фотографии. Если оптимальных упрощённых полос несколько, выведите любую из них.
$n = n_1 + n_2 + \cdots + n_t$
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 11 | 1ドル \le k_i \le n_i \le 10,ドル 1ドル \le n \le 5000$ |
| 2 | 24 | 1ドル \le k_i \le n_i \le 100,ドル 1ドル \le n \le 5000$ |
| 3 | 24 | 1ドル \le k_i \le n_i \le 1000,ドル 1ドル \le n \le 50,000円$ |
| 4 | 21 | 1ドル \le k_i \le 5000,ドル 1ドル \le n \le 100,000円$ |
| 5 | 20 | 1ドル \le k_i \le 200,000円,ドル 1ドル \le n \le 200,000円$ |
3 9 3 000111000 10 3 0111011010 4 4 0001
000111000 0111111000 0001