Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
268. Шедевр
Олимпиадные задачи на русском языке| 02/07/2007 | Лето 2007 дорешивание (10G) |
| 23/07/2007 | Лето 2007 - 10 (G) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Новый футуристический шедевр, задуманный гениальным художником М. Калевичем,
представляет собой прямоугольник,
разбитый на `N\ times\ M` клеток (`N` строк по `M` клеток). Знаменитый
художник составил эскиз, на котором для каждой клетки
решил, каким цветом она должна быть в соответствии с великим
замыслом. Так как художник недавно примкнул
к движению минималистов в живописи, он использует
только два цвета — черный и белый. Калевичу уже немало лет,
поэтому за рабочий день он может сделать только один мазок — опустить кисть
в одну из двух банок с краской и провести
некоторую горизонтальную полосу высоты 1 по какой-то еще незакрашенной части холста.
Перекрашивать холст нельзя.
Калевич не хочет работать более `K` дней, так как уже наметил
для себя творческий отдых.
Какое наименьшее количество клеток окажется покрашенными
неправильно? Заметим, что исходно холст имеет серый цвет.
В первой строке входного файла записано три целых числа
`N`, `M` и `K` (`1\ ≤\ N\ ≤\ 64`, `1\ ≤\ M\ ≤\ 64`, `1\ ≤\ K\ ≤\ 4096`).
Далее в `N` строках содержится описание эскиза. Каждая строка
содержит по `M` символов.
Символ '0' обозначает, что соответствующая клетка черная, '1' —
белая.
Выведите наименьшее количество клеток, которые могут остаться
покрашенными неправильно после не более чем `K` дней работы великого мастера.
Далее в `N` строках выведите результат работы художника.
Серый цвет следует обозначать символом '2'.
Пример ввода
3 5 3 00000 00000 00110
Пример вывода
2 00000 00000 00000
