ть смужок довжини i - 1, зберігати потрібно лише ці 2'192 = 384 значення. Незважаючи на малий розмір таблиці (масив total в програмі) слід зазначити, що її розмір експоненціально залежить від одного з вхідних параметрів - кількості кольорів k , а саме: 2 ' k '2 k ( k +1)/2 . Наприклад, для 8 кольорів необхідно було б зберігати 2 40 елементів, що нереально. Цим дана задача відрізняється від розглянутих раніше. p> Залишилось обговорити деякі технічні прийоми, що дозволяють написати досить просту програму, що реалізовує описаний алгоритм. Якщо ми поставимо у відповідність кожному з унікальних місць в діаграмі суміжності свій ступінь двійки від 2 0 до 2 5 (див. масив констант magic в програмі), то кожній діаграмі може бути поставлений у відповідність номер від 0 до 63, який дорівнює сумі тих ступенів двійок, які відповідають значенням "Y" (див. процедуру findcode). Якщо ми підраховуємо кількість смужок для діаграми з номером j , то сумісність додається кольору k стояв раніше останнім кольором l згідно діаграмі j можна перевірити так: magic [k, l] and j <> 0. Дане умова, побудоване за допомогою бітової операції над цілими числами and, означає наявність у j- ой діаграмі суміжності елемента "Y" на перетині k -й рядки і l -го шпальти (відповідна ступінь двійки масиву magic міститься в двійковому представленні числа j ). Вираз j - magic [k, l] відповідає заміні в діаграмі з номером j згаданого елемента "Y" на "N" (по іншому це вираз можна було б записати як j xor magic [k, l]). Докладніше про бітових операціях над цілими числами можна прочитати в [1]. Останній прийом полягає в тому, що ми не будемо на кожному кроці перепрісваівать отримані значення елементів масиву, призначеного для зберігання результатів попереднього кроку. Для цього результати для смужок парною довжини i будемо поміщати в половину масиву total з першим індексом 0, а непарні - з індексом 1. У будь-якому з цих випадків значення попереднього кроку доступні за індексом [1 - i mod 2]. Крім того, відповідь на рішення цього завдання при всіх N , задовольняють умові, вимагає самостійної організації обчислень з допомогою так званої "довгої арифметики" (див., наприклад, [1, 3]).
Наведемо програму для вирішення цього завдання, але використовує замість "довгої арифметики" тип даних extended, який зберігає максимально можливу кількість значущих цифр (спробуйте модернізувати програму самостійно). Тобто не для всіх значень N відповідь буде вирахувано точно. Але, так як для отримання результату використовується тільки додавання цілих чисел, втрати точності при проміжних обчисленнях не буде, принаймні поки відповідь не стане перевищувати 2 63 .
{$ N +}
const magic: array [1 .. 3, 1 .. 3] of byte =
((1, 2, 4),
(2, 8, 16),
(4, 16, 32));
var n, i, j, k, l, code: longint;
can: array [1 .. 3, 1 .. 3] of boolean;
total: array [0 .. 1, 1 .. 3, 0 .. 63] of extended;
answer: extended;
procedure readdata;
var s: string;
i, j: byte;
begin
readln (n);
fillchar (can, sizeof (can), false);
for i: = 1 to 3 do
begin
readln (s);
for j: = 1 to 3 do
if upcase (s [j]) = 'Y' then
begin
can [i, j]: = true;
can [i, j]: = true
end
end
end;
procedure findcode;
var i, j: byte;
begin
{переводимо діаграму суміжності до числа}
code: = 0;
for i: = 1 to 3 do
for j: = i to 3 do
if can [i, j] then
code: = code + magic [i, j]
end;
begin
assign (input, 'input.txt');
reset (input);
assign (output, 'output.txt');
rewrite (output);
readdata;
findcode;
fillchar (total, sizeof (total), 0);
{кількість смужок довжини 1}
for i: = 1 to 3 do
total [1, i, 0]: = 1;
for i: = 2 to n do
for j: = 0 to 63 do
for k: = 1 to 3 do
{cчитался смужки довжини i,
c діаграмою суміжності j
і закінчуються кольором k}
begin
total [i mod 2, k, j]: = 0;
for l: = 1 to 3 do
{цикл за кінцевим кольором
смужок довжини i - 1}
if magic [k, l] and j <> 0 then
{кольору l і ​​k можуть сусідити
згідно діаграмі суміжності j}
begin
total [i mod 2, k, j]: =
total [i mod 2, k, j] +
total [1 - i mod 2, l, j];
total [i mod 2, k, j]: =
total [i mod 2, k, j] +
total [1 - i mod 2, l, j - magic [k, l]]
end
end;
answer: = 0;
{підсумову...
