p> table [i, 1]: = 1
end;
{невизначені елементи мітимо -1}
for i: = 2 to n do
for j: = 2 to i-1 do
table [i, j]: = -1;
sum: = 0;
for i: = 1 to n do
sum: = sum + t (n, i);
writeln ('sum =', sum)
end.
В
Задача 10 . Плитки ( Чемпіонат школярів з програмування, Санкт-Петербург, 1999 р. ). p> У Петі є необмежений набір червоних, синіх і зелених плиток розміром 1'1. Він вибирає рівно N плиток і викладає їх в смужку. Наприклад, при N = 10 вона може виглядати наступним чином:
К
К
К
З
З
К
К
З
К
З
(Буквою До позначена червона плитка, С - синя, З - зелена)
Після цього Петя заповнює наступну таблицю, яка в даному прикладі виглядає так:
Червоний
Синій
Зелений
Червоний
Y
Y
Y
Синій
Y
N
Y
Зелений
Y
Y
N
У клітці на перетині рядка, що відповідає кольору А, і стовпця, що відповідає кольору Б, він записує "Y", якщо в його смужці знайдеться місце, де поруч лежать плитки квітів А і Б і "N" в іншому випадку. Вважається, що плитки лежать поруч, якщо у них є спільна сторона. (Очевидно, що таблиця симетрична щодо головної діагоналі - якщо плитки квітів А і Б лежали поруч, то поруч лежали і плитки квітів Б і А.) Назвемо таку таблицю діаграмою суміжності даної смужки.
Так, дана таблиця являє собою діаграму суміжності наведеної вище смужки.
Допоможіть Петі дізнатися, скільки різних смужок має певну діаграму суміжності (зауважте, що смужки, які є відображенням один одного, але не збігаються, вважаються різними. Так, смужка
З
К
З
К
К
З
З
К
К
К
не співпадає з смужкою, наведеної на початку умови.)
Перший рядок вхідного файлу містить число N . (). Наступні три рядки вхідного файлу, що містять по три символи з набору {"Y", "N"}, відповідають трьом рядкам діаграми суміжності. Інших символів, включаючи пробіли, у вхідному файлі не міститься. Вхідні дані коректні, тобто діаграма суміжності симетрична.
Виведіть у вихідний файл кількість смужок довжини N , мають наведену у вхідному файлі діаграму суміжності. Нижче дано приклад вхідного і вихідного файлів. br/>
Input.txt
Output.txt
10
YYY
YNY
YYN
4596
В
Рішення. Очевидно, що перебір всіх можливих смужок в даній задачі неможливий, так як їх кількість може скласти 2 100 , тому слід спробувати знайти динамічну схему рішення. Зрозуміло, що для того щоб підрахувати кількість смужок довжини N , що задовольняють заданій діаграмі суміжності, необхідно знати кількість допустимих смужок довжини N - 1, а також кількість смужок, в діаграмі суміжності яких один діагональний елемент або два симетричних недіагональних елемента дорівнюють "N" замість "Y" у вихідній діаграмі. Далі, при розгляді смужок довжини N - 2, буде потрібно знати кількість смужок, що задовольняють ще більшій кількості діаграм суміжності і т. д. У результаті на якому то кроці нам може знадобитися інформація про кількість смужок практично з усіма можливими діаграмами. Загальна кількість останніх становить 2 6 = 64 (унікальними, тобто не повторюються, а, значить, визначальними кількість різних діаграм, є тільки 6 елементів). Так як при збільшенні довжини смужки діаграма може змінитися в залежності від поєднання кольорів в останньому (новому) і передостанньому елементах, підраховувати смужки слід окремо для трьох різних кінцевих елементів. Таким чином кількість збереженої інформації зростає до 64'3 = 192 значень. Стільки ж значень буде отримано в результаті перерахунку. Але завдяки тому, що кількість смужок довжини i виражається тільки через кількіс...
