Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2341. Прорыв
Задачи на построениеОлимпиадные задачи на русском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 6) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Мориарти скрылся в коридоре. Шерлок выстрелил ему вслед, но пуля только оставила трещины в пуленепробиваемом
стекле. Шерлок решил обдумать ситуацию. Стекло состоит из `N` рядов по `M` клеток, при выстреле добавляется
по одной трещине в пораженной клетке и в соседних с ней клетках (соседними считаются клетки, имеющие общую
сторону или угол). Чтобы стекло разрушилось целиком, каждый раз нужно стрелять в клетки, имеющие
наименьшее количество трещин. Если существует несколько клеток с минимальным количеством трещин, то
можно стрелять по любой из этих клеток. Как только в какой-то из клеток появится ровно `K` трещин, стекло
разрушится. Сколько потребуется выстрелов, чтобы разрушить стекло?
Формат ввода
Первая строка ввода содержит три целых числа – размеры стекла `N`, `M` (`1\ ≤\ N,M\ ≤\ 20`) и предел прочности
стекла `K` (`1\ ≤\ K\ ≤\ 20`).
Формат вывода
В первой строке вывести одно целое число `S` – минимальное количество выстрелов.
Далее вывести `S` строк – последовательность выстрелов, в каждой строке два целых числа `r` (`1\ ≤\ r\ ≤\ N`)
и `c` (`1\ ≤\ c\ ≤\ M`) – координаты поражаемой выстрелом клетки. Если существует несколько
минимальных вариантов, то можно вывести любой из них.
Пример ввода
4 5 4
Вывод программы
4 2 2 2 4 4 2 4 4
