В Екатеринбурге активно развивается общественный транспорт.
В ближайшее время городские власти планируют отремонтировать около 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 г.