Подразделы

Другие разделы

Дата и время

09/04/2025 13:37:31

Авторизация

Лето 10

A. Наименьшее общее кратное B. Noise Effect C. Сумма кубов D. Сумма двух E. Хитрый министр F. Послание к инопланетянам G. Шедевр

G. Шедевр

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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'.

Пример ввода

Пример вывода

Источник: http://neerc.ifmo.ru/school/archive/