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

1609. Трамвайная плитка

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
В Екатеринбурге активно развивается общественный транспорт. В ближайшее время городские власти планируют отремонтировать около 20 км трамвайных путей по новой технологии с применением специально разработанной плитки. Внедрение нового способа ремонта межрельсового пространства началось минувшим летом, и первые результаты видны уже сейчас.
Так, бригада Равшана и Джамшуда оснастила плиткой почти 2 перекрестка в центре города. Такая поразительная скорость работы объясняется новой хитростью, придуманной их начальником. Перед началом ремонтных работ он сам размещает между рельсами несколько плиток так, чтобы можно было продолжить выкладывать их только одним способом. В результате экономится время на проектирование плиточных узоров, которое занимает большую часть рабочего дня у других бригад.
Каждая плитка имеет размер 1 × 2. Требуется замостить плиткой прямоугольную область размером n × m. Определите минимальное число плиток, которое должен выложить начальник, чтобы итоговый узор (то есть полное замощение прямоугольника плитками) определялся однозначно. Два узора считаются одинаковыми, если расположение всех плиток в них совпадает.

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

Единственная строка содержит целые числа n и m (1 ≤ n, m ≤ 10; произведение nm четное).

Результат

Выведите в первой строке минимальное число плиток, которое должен выложить начальник. Следующие n строк должны содержать по m символов, описывающих одно из возможных начальных расположений. Символ «1» обозначает клетку, занятую плиткой, символ «0» — пустое место.

Примеры

исходные данныерезультат
4 4
2
1100
0110
0000
0000
2 5
2
11110
00000
Автор задачи: Сергей Пупырев
Источник задачи: XII чемпионат Урала по спортивному программированию, 29 марта 2008 г.