ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU and Orel STU contest. Petrozavodsk training camp. Summer 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Лунокод

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В ходе оборонительной войны против марсиан лунные программисты придумали новый способ кодирования информации. Вся информация представляется в виде матрицы A размером M × N, состоящей из нулей и единиц. Верхняя левая клетка такой полоски имеет координаты (1, 1), нижняя правая — (M, N). Чтобы передавать информацию без искажений, был разработан любопытный механизм. Перед передачей информации полоска заполняется нулями и единицами таким образом, чтобы для любого i от 1 до N − 1 выполнялось следующее условие: во множестве {j | (A[j][i]=0 и A[j][i+1]=1)} не более K элементов. После приёма информации проверяется выполнение данного условия, и в случае, если для какого-то i оно не выполняется, то полученной информации доверять нельзя. Механизм стал широко распространён и получил название "контрольное условие лунатиков".

Исходные данные

3 целых числа M, N, K. 1 ≤ M, N ≤ 40. 0 ≤ KM.

Результат

Целое число — количество заполненных матриц, удовлетворяющих контрольному условию лунатиков.

Примеры

исходные данныерезультат
2 1 0
4
2 2 1
15

Замечания

Матрицы, удовлетворяющие примеру 2:
10   11   10   11   10   10   11   11   00   01   00   01   00   01   00
10   10   11   11   00   01   00   01   10   10   11   11   00   00   01
Автор задачи: Александр Ипатов (идея — Александр Торопов)
Источник задачи: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1476. Лунокод