Известно, что в книгах для слепых для обозначения различных букв используются различные комбинации выступов, которые читающий различает наощупь. Пусть для обозначения буквы используется прямоугольник шириной M мм и высотой N мм, причем некоторые входящие в него квадратики размера 1×1 содержат выступ.

Поскольку слепой не видит границ прямоугольника, то он не может различить комбинации, получающиеся друг из друга сдвигом. Так, он не может различить комбинации а) и б) на рисунке 1. (В то же время комбинации а) и в) являются различимыми, поскольку не могут быть получены друг из друга сдвигом)


Рисунок 1

Из-за этого при разработке алфавита для слепых появилась проблема: сколько различных букв можно представить с помощью выступов, если запрещается сопоставлять различным буквам комбинации, получающиеся друг из друга сдвигом. Прямоугольник совсем без выступов также нельзя использовать в качестве буквы (поскольку при написании слова между некоторыми буквами может появиться такой прямоугольник, например между а) и г) на рисунке 1).



Требуется подсчитать количество различных букв, которые можно представить таким способом, если прямоугольник имеет размер N×M.

В качестве примера, все буквы размера 2×2 приведены на рисунке 2. (Среди комбинаций, отвечающих одной букве, приведена только одна)


Рисунок 2

Формат входных данных

Входной файл Input.txt содержит числа M и N, разделенные пробелом. Поскольку человек одновременно не может воспринимать слишком много информации, M×N <= 30.

Формат выходных данных

Выведите в выходной файл Output.txt единственное число - количество различных букв, которые слепой сможет различить при заданном размере прямоугольника.

Примеры

input.txt
output.txt

2 2
10

3 3
400

картинки в файле.

Добавлено @ 18:11
Тут наверно мат анализ надо приложить. Кол-во расстановок как-то обыграть.

Присоединённый файл ( Кол-во скачиваний: 11 )
 image001.rar

можно попробовать пронормировать фигуры: сдвинуть влево и вверх, пока не упрутся в границу прямоугольника...

Цитата(maxim1000 @ 14.3.2005, 18:37)

можно попробовать пронормировать фигуры: сдвинуть влево и вверх, пока не упрутся в границу прямоугольника...

Т. е. просто перебрать все варианты? А может все-таки что-то подразумевается?

Ну что? Никаких соображений? Перебором всегда во время не укладывается.

для квадратных решеток (N=M), похоже, получается closed-form выражение (но числа огромные), для прямоугольных пока не видно (за исключением Nx1 ).

Вот теперь работает...

Код

xCount = 0 Mask1 = 2 ^ M - 1 Mask2 = 0 For i = 0 To N - 1     Mask2 = Mask2 + 2 ^ (i * M) Next i For i = 1 To 2 ^ (M * N) - 1     If ((i And Mask1) > 0) And ((i And Mask2) > 0) Then         xCount = xCount + 1     End If Next i Print xCount

Одно плохо - на больших M и N получается нечто слишком многобитное - впрочем никто не мешает модифицировать под работу в строковой форме...

Akina
приведи, pls , результаты для M=N=2..5

2 2: 10
2 3: 44
2 4: 184
2 5: 752
3 3: 400
3 4: 3392
3 5: 27904
4 4: 57856
4 5: 954368
5 5: 31522816

Akina
Спасибо.

Ух.... Спасибо. Сейчас посмотрю. Потом еще приду ;)
Добавлено @ 18:46
Супер. А как это придумано? Расскажи мысли, теорию и т. д. А? Мне не решение в основном интересует, а логика. К очень важной олимпиаде готовлюсь...

And тут побитовый? А что проверяем?

Код

Mask1 = 2 ^ M - 1

В Маск1 - колво всех возможных вариантов в каждой строке. -1 потому что нуль - не вариант.

Код

Mask2 = 0 For i = 0 To N - 1     Mask2 = Mask2 + 2 ^ (i * M) Next i

Тут кол-во вариантов в зависимомти от кол-ва строк. Почему 0...Н-1 непонятно.

Код

For i = 1 To 2 ^ (M * N) - 1     If ((i And Mask1) > 0) And ((i And Mask2) > 0) Then         xCount = xCount + 1     End If Next i

Интуитивно что-то там вертится, но определенных форм не приобретает...

Если символ допускает сдвиг вправо или вниз - отбросить.

Угу. А это?

Код

Mask2 = 0 For i = 0 To N - 1     Mask2 = Mask2 + 2 ^ (i * M) Next i