Известно, что в книгах для слепых для обозначения различных букв используются различные комбинации выступов, которые читающий различает наощупь. Пусть для обозначения буквы используется прямоугольник шириной 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

без циклов:

2^(mn-1)+(2^(n-1)-1)*(2^(m-1)-1)*2^((m-1)*(n-1))

на Паскале (для небольших N,M):

Код

Result := 1 shl (N * M - 1) +    (1 shl (N - 1) - 1) * (1 shl (M - 1) - 1) * (1 shl ((N - 1) * (M - 1)));

Да мне НЕ решение важно!!!!!!!!!!!!!!!
Мне надо знать как это придумать!!!!!!
Извиняюсь, если раньше этого не говорил.

Более простая и понятная форма:

2^(mn) - 2^(m(n-1)) - 2^(n(m-1)) +2^((m-1)*(n-1))

Количество всех (в т.ч. недопустимых) размещений в NxM прямоугольнике минус (те, в которых первая строка пуста + те, в которых первый столбец пуст -то, что учитывается дважды)

Цитата(Fixin @ 18.3.2005, 21:35)

А это?

Это построение маски сдвига вправо.