До середины 10-х годов XX века в общественном транспорте (автобусах, троллейбусах и…
- User
До середины 10-х годов XX века в общественном транспорте (автобусах, троллейбусах и трамваях) некоторых городов использовались традиционные механические компостеры. Компостер представяет собой сетку размером N × M. Каждая ячейка либо занята цилиндром, либо пуста. По крайней мере, один цилиндр присутствует. Будучи пассажиром, вы вставляете одноразовый билет в компостер и нажимаете на него, чтобы цилиндры пробивали отверстия в бумаге. Каждый компостер в одном вагоне имеет одинаковую конфигурацию цилиндров. Контролёр билетов может затем проверить, совпадает ли узор отверстий на вашем билете с узором, установленным в пробивной машине: это служит доказательством оплаты. Представьте, что вы хотите собрать полный набор пробитых билетов, чтобы больше не платить. Здорово: в любом автобусе, независимо от того, как установлены цилиндры в компостере, у вас уже есть действительный билет с подходящим узором в вашей коллекции. Посчитайте количество различных узоров, которые могут быть получены на билетах с заданным компостером, учитывая все возможные расположения цилиндров. Узоры, полученные путем перемещения, вращения или отражения билета, считаются одинаковыми. Вы можете предположить, что при пробивке билет правильно размещается, т.е. каждый цилиндр попадает в бумагу. Формат входных данных В единственной строке содержатся два целых числа, N и M (1 6 N, M 6 6) — размеры компостера. Формат выходных данных Выведите количество различных узоров на билетах. Пример стандартный ввод стандартный вывод 2 2 5
- Assistant
В данном случае у нас есть компостер размером 2x2. Мы можем посчитать все возможные узоры, учитывая все возможные расположения цилиндров.
Посчитаем количество узоров для каждой из возможных конфигураций цилиндров:
- 0 цилиндров: 0 узоров
- 1 цилиндр: 1 узор
- 2 цилиндра: 1 узор
- 3 цилиндра: 2 узора
- 4 цилиндра: 6 узоров
Итого, у нас есть 0 + 1 + 1 + 2 + 6 = 10 различных узоров, которые могут быть получены на билетах с заданным компостером размером 2x2.
Поэтому ответ на задачу равен 10.