На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
Как и обещал, вот разбор задач =)
Решения по 1,3,4 задачам полнобальные. Решение второй задачи, судя по всему, имеет правильную ассимптотику (по крайней мере, идейная часть решения), но достаточно большую константу, посему выполняется за время, очень близкое к тайм-лимиту и некоторые тесты проходит "через раз". Впрочем, следует отметить, что при проверке того же решения по уже упомянутой ранее "подобной" задаче с другого соревнования на codeforces.ru (которую я осуществлял уже после того, как "окончательно" отправил своё решение), максимальное время работы было 140 мс и решение полностью засчитывалось.
Предполагаемое мной решение по 5-ой задаче оказалось неправильным, поэтому хотел бы попросить у решивших её выложить здесь идею правильного решения.
1. Hanoysoft
Первым делом рассмотрим, какие действия надо совершать, чтобы полностью переложить все диски. Здесь следует отдельно рассматривать ситуации, когда диски должны быть переложены между первым и третим столбом и когда между вторым и соседними.
Для начала рассмотрим перекладывание дисков между первым и третьим столбом. Для случая, когда дисков 1, надо сделать 2 перекладывания. Когда же дисков 2, надо сначала переложить два раза верхний диск, продвинуть на один столбец нижний, снова два раза передвинуть верхний, продвинуть нижний на крайний столбец и снова передвинуть дважды верхний. Легко заметить, что при любом N, нам надо сначала передвинуть на два столба вперёд N-1 дисков, потом продвинуть на один вперёд самый нижний диск, переложить на начальную позицию N-1 дисков, снова передвинуть самый нижний диск и, наконец, снова переложить остальные диски вперёд. Таким образом, если мы обозначим количество действий, которые необходимо будет совершить для перекладывания n дисков от столба 1 к столбу 3 или от столба 3 к столбу 1, за A(n), то получим, что:
A(n)=A(n-1)+1+A(n-1)+1+A(n-1)=3*A(n-1)+2;
Вычислив несколько первых значений, можно обратить внимание, что эта формула преобразуется в:
A(n)=3^n-1;
Доказать это можно, например, методом мат. индукции. Мы знаем, что для n=1 нам необходимо совершить два перекладывания, что соответствует нашему предположению.
Теперь из допущения, что A(k)=3^n-1, докажем, что A(k+1)=3^(k+1)-1.
A(k+1)=3*A(k)+2=3*(3^k-1)+2=3^(k+1)-3+2=3^(k+1)-1;
Что и требовалось доказать.
Теперь рассмотрим случай когда перемещение идёт между средним и крайним столбами. Очевидно, что для n=1 ответом будет 1. Теперь посмотрим, как выглядит решение для n>1. При n=2 мы:
1. Перекладываем верхний диск на соседний столб.
2. Перекладываем нижний диск.
3. Перекладываем верхний диск на противоположный столб.
Таким образом, можно заметить, что для n=k нам надо будет выполнить следующие действия:
1. Перекладываем n-1 дисков на соседний столб.
2. Перекладываем нижний диск на другой соседний столб.
3. Перекладываем n-1 дисков на противоположный столб.
Определим функцию B(n), которая возвращает число, необходимое для перенесения дисков между центральным и крайними столбами. Из описанной выше схемы видно, что:
B(n)=B(n-1)+1+A(n-1)=B(n-1)+1+3^(n-1)-1=B(n-1)+3^(n-1);
Проведя начальные вычисления для небольших n можно, равно как и для функции A, заметить некоторую закономерность. Возвращаемые значения похожи на A(n)/2. Попытаемся доказать это утверждение с помощью всё той же мат. индукции. Для n=1:
(3^n-1)/2=1
Это равенство выполняется. Теперь из допущения, что оно выполняется для k, докажем, что оно выполняется для k+1, то есть, что если B(k)=(3^k-1)/2, то B(k+1)=(3^(k+1)-1)/2.
B(k+1)=(3^k-1)/2+3^k=(3^k-1+2*3^k)/2=((1+2)*3^k-1)/2=(3^(k+1)-1)/2;
Что и требовалось доказать.
Итоговые формулы:
A(n)=3^n-1;
B(n)=A(n)/2;
Есть также несколько аспектов, связанных с реализацией программы. Если для случая, когда нам надо вызывать A(n), всё более понятно, то с B(n) начинаются проблемы, так как на участках 1-1000000007, 2000000014-3000000021 и так далее, остаток от деления A(n) на 1000000007 - число чётное и его можно смело делить на два. А вот на участках 1000000007-2000000014, 3000000021-4000000028 и так далее, этот остаток будет нечётным и так просто взять и поделить его на два не получится. Однако, решение есть! Мы должны просто прежде, чем делить, добавить к этому остатку 1000000007 и тогда он станет чётным, но при делении сохранит свои свойства и правильно выдаст нужное число.
Исходный код по задаче:
#include <cstdlib>
#include <iostream>
using namespace std;
int bin(int N)
{
long long a=1;
for(int i=0;i<N;i++)
{
a*=3;
a%=1000000007;
}
return a-1;
}
int main(int argc, char *argv[])
{
long long N,A,B;
cin>>N>>A>>B;
if((A==1 && B==3) || (A==3 && B==1))
{
cout<<bin(N)<<endl;
}
else if(A==2 || B==2)
{
int a=bin(N);
if(a%2)
{
cout<<(a+1000000007)/2<<endl;
}
else
cout<<a/2<<endl;
}
return EXIT_SUCCESS;
}Ассимптотика такого решения - O(N);
2. Upgrade
Достаточно легко заметить, что при таких условиях, школы могут собираться в группы только двух видов. Первый - это "открытая" ломаная, для которой единственный возможный вариант замены - это заменить ВСЕ соединения ("элементарный путь"). Второй - замкнутая ломаная, то есть, многоугольник ("элементарный цикл"), для которого существует n вариантов замены, где n — количество рёбер в нём. В этой задаче, в отличие от остальных, реализация является немного более сложной задачей, чем придумывание решения. Нужно сначала удалить из графа, который получается из входных данных все элементарные пути, а затем во втором обходе разбить элементарные циклы, которые остались после удаления элементарных путей, по отдельным контейнерам, после чего ответом будет:
ans=(a[0].size()*a[1].size()*a[2].size()*...*a[n].size()) mod 1000000007;
Где ans - ответ, a[][] - двумерный контейнер, хранящий в i-том одномерном контейнеры все рёбра элементарного цикла №i. То есть, в ответе будет произведение количества рёбер в каждом элементарном цикле.
Исходный код по задаче:
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char *argv[])
{
int n,m;
cin>>n>>m;
vector< vector<int> > node;
for(int i=0;i<n;i++)
{
vector<int> tmp;
node.push_back(tmp);
}
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
node[a-1].push_back(b-1);
node[b-1].push_back(a-1);
}
for(int i=0;i<n;i++)
{
if(node[i].size()==1)
{
int j=i;
vector<int> em;
int p=j;
do
{
int k=j;
if(node[j][0]!=p)
j=node[j][0];
else
j=node[j][1];
p=k;
node[k]=em;
}
while(node[j].size()!=1);
node[j]=em;
}
}
vector< vector<int> > ea;
for(int i=0;i<n;i++)
{
if(node[i].size()==2)
{
vector<int> em;
vector<int> tmp;
tmp.push_back(i);
int j=node[i][0];
int p=i;
do
{
node[j]=em;
tmp.push_back(j);
int p1=j;
if(node[j][0]!=p)
j=node[j][0];
else
j=node[j][1];
p=p1;
}
while(j!=i);
ea.push_back(tmp);
}
}
long long ans=1;
for(int i=0;i<ea.size();i++)
{
ans*=ea[i].size();
ans%=1000000007;
}
cout<<ans<<endl;
return EXIT_SUCCESS;
}Ассимптотика такого решения — O(2*N);
3. Digits2
Задача, над которой я по некоторым причинам думал больше всего. Решением может быть ленивая динамика или оптимизированный перебор. Первое в данной задаче будет не очень удобной, посколько речь здесь идёт ещё и об отрицательных числах, для которых правила игры немного другие. Рассмотрим поближе переборное решение. Объявим контейнер, в котором будем хранить все найденные числа. После этого отдельной рекурсивной функцией вычисляем их. Простой перебор будет иметь ассимптотику, близку к O(2^N). Однако очень простая оптимизация может в разы ускорить решение и, возможно, даже превратить его в линейное. Мы добавляем в функцию проверку на то, вызывалась ли она ранее с такими же входными данными и получаем вполне быстрое решение.
Исходный код по задаче:
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
vector<double> anses;
bool**table;
void se(int cur,int to)
{
if(table[cur+3000][to])
{
table[cur+3000][to]=false;
if(to==0)
{
anses.push_back(cur);
}
else if(cur%2)
se(cur-1,to-1);
else
{
se(cur/2,to-1);
se(cur-1,to-1);
}
}
}
int main()
{
int n,k;
cin>>n>>k;
n*=2;
table=new bool*[6001];
for(int i=0;i<6001;i++)
{
table[i]=new bool[k+1];
for(int j=0;j<k+1;j++)
table[i][j]=true;
}
se(n,k);
cout<<anses.size()<<endl;
return EXIT_SUCCESS;
}Ассимптотику оценить достаточно сложно, но, как мне кажется, решение работает приблизительно за O(N^2);
4. Chocolate
Задача, оказавшаяся для меня самой интересной и имеющей наиболее красивое решение, как мне кажется. Достаточно быстро можно заметить, что функция, возвращающая ответ имеет следующий вид:
A(M,N,K)=A(M-1,N,K)+A(M,N-1,K)+A(M,N,K-1);
Но если в двух или более функциях аргументы совпадают, то они считаются не как два (три) отдельных слагаемых, а как одно. Возможно, кому-то, как и мне сейчас это кое-что напомнило. Помните такую вещь, как треугольник Паскаля? Для него формула имеет вид
A(M,N)=A(M-1,N)+A(M,N-1);
Здесь же мы имеем дело с подобным объектом, только это ПИРАМИДА. Мы просто создаём трёхмерный массив и проставляем крайним граням значение 1, а затем просчитываем по указанным выше правилам число в клетке A[x,y,z].
Исходный код по задаче:
#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
long long m,n,k;
cin>>m>>n>>k;
long long***table=new long long**[m];
for(int i=0;i<m;i++)
{
table[i]=new long long*[n];
for(int j=0;j<n;j++)
table[i][j]=new long long[k];
}
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
table[i][j][0]=1;
for(int i=0;i<m;i++)
for(int j=0;j<k;j++)
table[i][0][j]=1;
for(int i=0;i<n;i++)
for(int j=0;j<k;j++)
table[0][i][j]=1;
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
for(int l=1;l<k;l++)
{
if(i==j && j==l)
table[i][j][l]=(table[i-1][j][l])%1000007;
else if(i==j)
table[i][j][l]=(table[i][j][l-1]+table[i-1][j][l])%1000007;
else if(j==l)
table[i][j][l]=(table[i][j][l-1]+table[i-1][j][l])%1000007;
else if(i==l)
table[i][j][l]=(table[i][j][l-1]+table[i][j-1][l])%1000007;
else
table[i][j][l]=(table[i][j][l-1]+table[i-1][j][l]+table[i][j-1][l])%1000007;
}
cout<<table[m-1][n-1][k-1]<<endl;
return EXIT_SUCCESS;
}Ассимптотика решения: O(M*N*K);
И да, счастливого Нового Года всем и удачи на следующих турах =)
Відредаговано adamant (2012-12-28 19:09:25)
Поза форумом
Обновлено. Прошу предоставить разбор решивших Trimino.
Поза форумом
Тримино
Динамика
Множество способов обозначим S(n)
Тогда считаем в цикле до n:
S(n)=4S(n-3)+2T(n-2)
T(k)=S(k-4)+2A(k-2)
A(m)=2T(m-1)+2A(m-3)
Опытным путём находим:
S(3)=4
T(4)=1
A(5)=2
S - T- A-
######## ######## ##########
######## ######## ##########
######## ###### #########
######## ###### #########
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
if (!(n % 3))
{
long long s1 = 4;
long long t1 = 1,a1 = 2;
long long s = 4,t = 1,a = 2;
for (int i = 6;i <= n;i++)
{
if (!(i % 3)) {
s1 = s;
s = (4*s + 2*t) % 1000000007; }
if (i % 3 == 1){
t1 = t;
t = (2*a + s1) % 1000000007;}
if (i % 3 == 2)
{
a1 = a;
a = (2*t + 2*a1) % 1000000007;
}
} cout<<s;
}
else
cout<<0;
return 0;
}
Відредаговано SBerezovaya (2012-12-28 19:44:42)
Поза форумом
И каким образом выводятся такие формулы?.. Можете подробнее расписать, что каждая из них значит?
Поза форумом
adamant написав:
Обновлено. Прошу предоставить разбор решивших Trimino.
Думаю задача не нова, ссылка к ее разбору http://arxiv.org/pdf/math/9905012v1
Поза форумом
Чи можна побачити тести і відповіді до них до задачі Trimino
Дивно, чому мій розв'язок не набрав ні одного бала...
Можливо, я не правильно зрозумів задачу...
Буду дуже вдячний.
Поза форумом
Taras_Z написав:
Чи можна побачити тести і відповіді до них до задачі Trimino
Дивно, чому мій розв'язок не набрав ні одного бала...
Можливо, я не правильно зрозумів задачу...
Буду дуже вдячний.
Тести будуть Вам доступні після завершення усіх турів олімпіади.
А дана задача є гарною ілюстрацією:
1. Як до анекдота, який завершується словами: "...Изя, лучше бы ты вообще ничего не рисовал..." (стосується малюнку-ілюстрації, який багатьох направив на хибний шлях роздумів),
2. Так і до класичного принципу з теорії алгоритмів та їх практичної реалізації: "Пример входных и выходных данных дается в задаче для того, чтобы Вы могли видеть, что иногда Ваше неверное решение даёт верные ответы."
А взагалі (це вже адресується тому, хто цю задачу запропонував), як на мою думку, то хоча б один тест з відповіддю "0" (крім тестів з умови) у тестовому наборі до задачі повинен був бути присутнім, причому такий, який ще раз підтвержував би вище сформульовану тезу 2.
Набрані 2-3 бали по цій задачі на одному тесті нічого принципово не вирішували б, але давали б авторам хибних розв'язків більше мотивації для подальшого осмислення чинників, які призвели до взагалі їх помилкового підходу у способі її розв'язання.
Відредаговано Присяжнюк А.В. (2012-12-29 15:11:59)
Поза форумом
Tarasu_Z
Подивіться, прошу, наступні тести:
3 -> 4
6 -> 18
9 -> 88
33 -> 173093760
36 -> 129796921
99999 -> 870118843
100000 -> 0
Бажаю успіхів!
Поза форумом
Alex_Bulany, дякую.
Значить, що мій метод тут не підійшов.. Жаль((
Я його опишу тут, можливо хтось мені підкаже мою помилку...
Якщо число не ділиться на 3 то вивести 0 інакше
Я рахував кількість пар триміно (фігура 2x3)
можливих випадків для кожної такої пари тільки два -
#%% %%#
##% або % ##
пронумеруємо випадок перший - 0
а другий - 1
в нас получається двійкова послідовність
для першого прикладу вона має 4 символи(чотири пари)
і може бути такою
0000
0001
0010
...
1111
тобто кількість способів 2^к-сть пар
Поза форумом
Taras_Z написав:
Alex_Bulany, дякую.
Значить, що мій метод тут не підійшов.. Жаль((
Я його опишу тут, можливо хтось мені підкаже мою помилку...
Якщо число не ділиться на 3 то вивести 0 інакше
Я рахував кількість пар триміно (фігура 2x3)
можливих випадків для кожної такої пари тільки два -
#%% %%#
##% або % ##
пронумеруємо випадок перший - 0
а другий - 1
в нас получається двійкова послідовність
для першого прикладу вона має 4 символи(чотири пари)
і може бути такою
0000
0001
0010
...
1111
тобто кількість способів 2^к-сть пар
Помилка в тому, що можливі ще інші випадки розміщення триміно.
Наприклад, для 4х6: ## @@ ##
#% @%%#
@%%#%@
@@ ## @@
Поза форумом
victor18, дуже дякую!
Зрозумів свою помилку...
Поза форумом
Trimino
Розв`яжемо задачу за допомогою ДП по профілю. Профілем будемо вважати поле розміром 4*1, тобто стовпець розміру 4. У профілі використовуватимемо такі позначення:
1) два нулі, що розташовані у стовпці підряд, означають частину триміно розміру 2*1, що має бути "замкнена" до повного елемента триміно зліва. У такому випадку говоритимемо "орієнтована наліво двійка".
2) два числа 1, розташовані у стовпці підряд, означають частину триміно розміру 2*1, що має бути "замкена" до повного елемента триміно справа. У такому випадку говоритимемо "орієнтована направо двійка".
3) число 2 у профілі означає частину триміно 1*1, що має бути "замкнена" орієнтованою направо двійкою зліва. У такому випадку говоритимемо "орієнтована наліво одиниця".
4) число 3 у профілі означає частину триміно 1*1, що має бути "замкнена" орієнтованою наліво двійкою справа. У такому випадку говоритимемо "орієнтована направо одиниця".
Усього можливих профілів такого вигляду 24. Їх можна знайти вручну.
Будь-яке заповнення поля 4*n елементами триміно можна розглядати як набір n профілів, що йдуть у певному порядку. Проте не будь-які профілі можуть слідувати один за одним. Наприклад профіль (0,0,0,0) не може йти за (1,1,1,1). Тому для кожної орієнтованої пари (i,j) профілів необхідно визначити, чи може профіль j слідувати за профілем i(процедура check роз'язку).
dp[i,j] - кількість способів коректно заповнити поле 4*i профілями, щоб останній профіль був j-тий (такі заповнення можуть і не бути коректиними заповненнями поля елементами триміно, проте вони будуть коректними у тому сенсі, що послідовність профілів у них буде можливою).
dp[1,1] = 1 - база динаміки, бо будь-яке заповнення поля елементами триміно може починатися лише з профілю з номером 1 - (1, 1, 1, 1).
Для оптимізації програми запишемо всі орієнтовані пари профілів, що можуть слідувати один за одним у масиви s та f, де в s - номери перших профілів у парі, а в t - других.
Тоді розв'язки обчислюються таким чином:
for i := 2 to n do
for j := 1 to all do dp[i,s[j]]:=(dp[i,s[j]]+dp[i-1,f[j]]) ;
Відповідь - dp[n,2], бо будь-яке заповнення поля елементами триміно може закінчуватись лише профілем 2 (0, 0, 0, 0)
{$APPTYPE CONSOLE}
mask:array[1..24,1..4] of byte = ((1,1,1,1),(0,0,0,0),(1,1,0,0),(0,0,1,1),
(2,3,2,3),(2,3,3,2),(3,2,2,3),(3,2,3,2),(0,0,2,3),(0,0,3,2),(1,1,2,3),(1,1,3,2),
(2,0,0,2),(3,0,0,3),(3,0,0,2),(2,0,0,3),(2,1,1,2),(3,1,1,3),(3,1,1,2),(2,1,1,3),
(2,3,0,0),(3,2,0,0),(2,3,1,1),(3,2,1,1));
//список профілів
var
dp:array[1..100001,1..24] of longint;
//масив для динаміки
f,s:array[1..700] of byte;
//масиви для переходів
all,n,i,j:longint;
Function check(l,r:longint):boolean;
var
i:longint;
ok:boolean;
begin
i:=1;
ok:=true;
//припустимо профілі сумісні
while (i<=4) and (ok) do
//перевіка лівого профілю
begin
if (mask[l][i]=1) then
begin
ok:=((mask[r][i]=2) and (mask[r][i+1]<>2)) or ((mask[r][i+1]=2) and (mask[r][i]<>2));
//подвійний блок лівого профілю, орієнтований направо,
//справа має замикати одиничний орієнтований наліво
inc(i);
end;
if (mask[l][i]=3) then ok:=mask[r][i]=0;
//одиничний блок лівого профілю, орієнтований направо, справа має замикати
//подвійний орієнтований наліво
inc(i);
end;
i:=1;
while (i<=4) and (ok) do
//аналогічна перевірка правого провілю
begin
if (mask[r][i]=0) then
begin
ok:=((mask[l][i]=3) and (mask[l][i+1]<>3)) or ((mask[l][i]<>3) and (mask[l][i+1]=3));
inc(i);
end;
if (mask[r][i]=2) then ok:=mask[l][i]=1;
inc(i);
end;
check:=ok;
end;
begin
all:=0;
//формування масиву переходів
for i := 1 to 24 do
for j := 1 to 24 do if check(i,j) then
begin
inc(all);
f[all]:=i;
s[all]:=j;
end;
readln(n);
fillchar(dp,sizeof(dp),0);
//база динаміки
dp[1,1]:=1;
//динаміка
for i := 2 to n do
for j := 1 to all do dp[i,s[j]]:=(dp[i,s[j]]+dp[i-1,f[j]]) mod md;
//будь-який спосіб розміщення триміно закінчується профілем номер 2
writeln(dp[n,2]);
end.Відредаговано Depool.R (2012-12-30 22:54:37)
Поза форумом
Depool.R написав:
Trimino
Розв`яжемо задачу за допомогою ДП по профілю. Профілем будемо вважати поле розміром 4*1, тобто стовпець розміру 4. У профілі використовуватимемо такі позначення:
1) два нулі, що розташовані у стовпці підряд, означають частину триміно розміру 2*1, що має бути "замкнена" до повного елемента триміно зліва. У такому випадку говоритимемо "орієнтована наліво двійка".
2) два числа 1, розташовані у стовпці підряд, означають частину триміно розміру 2*1, що має бути "замкена" до повного елемента триміно справа. У такому випадку говоритимемо "орієнтована направо двійка".
3) число 2 у профілі означає частину триміно 1*1, що має бути "замкнена" орієнтованою направо двійкою зліва. У такому випадку говоритимемо "орієнтована наліво одиниця".
4) число 3 у профілі означає частину триміно 1*1, що має бути "замкнена" орієнтованою наліво двійкою справа. У такому випадку говоритимемо "орієнтована направо одиниця".
Усього можливих профілів такого вигляду 24. Їх можна знайти вручну.
Будь-яке заповнення поля 4*n елементами триміно можна розглядати як набір n профілів, що йдуть у певному порядку. Проте не будь-які профілі можуть слідувати один за одним. Наприклад профіль (0,0,0,0) не може йти за (1,1,1,1). Тому для кожної орієнтованої пари (i,j) профілів необхідно визначити, чи може профіль j слідувати за профілем i(процедура check роз'язку).
dp[i,j] - кількість способів коректно заповнити поле 4*i профілями, щоб останній профіль був j-тий (такі заповнення можуть і не бути коректиними заповненнями поля елементами триміно, проте вони будуть коректними у тому сенсі, що послідовність профілів у них буде можливою).
dp[1,1] = 1 - база динаміки, бо будь-яке заповнення поля елементами триміно може починатися лише з профілю з номером 1 - (1, 1, 1, 1).
Для оптимізації програми запишемо всі орієнтовані пари профілів, що можуть слідувати один за одним у масиви s та f, де в s - номери перших профілів у парі, а в t - других.
Тоді розв'язки обчислюються таким чином:
for i := 2 to n do
for j := 1 to all do dp[i,s[j]]:=(dp[i,s[j]]+dp[i-1,f[j]]) ;
Відповідь - dp[n,2], бо будь-яке заповнення поля елементами триміно може закінчуватись лише профілем 2 (0, 0, 0, 0)Код:
{$APPTYPE CONSOLE} mask:array[1..24,1..4] of byte = ((1,1,1,1),(0,0,0,0),(1,1,0,0),(0,0,1,1), (2,3,2,3),(2,3,3,2),(3,2,2,3),(3,2,3,2),(0,0,2,3),(0,0,3,2),(1,1,2,3),(1,1,3,2), (2,0,0,2),(3,0,0,3),(3,0,0,2),(2,0,0,3),(2,1,1,2),(3,1,1,3),(3,1,1,2),(2,1,1,3), (2,3,0,0),(3,2,0,0),(2,3,1,1),(3,2,1,1)); //список профілів var dp:array[1..100001,1..24] of longint; //масив для динаміки f,s:array[1..700] of byte; //масиви для переходів all,n,i,j:longint; Function check(l,r:longint):boolean; var i:longint; ok:boolean; begin i:=1; ok:=true; //припустимо профілі сумісні while (i<=4) and (ok) do //перевіка лівого профілю begin if (mask[l][i]=1) then begin ok:=((mask[r][i]=2) and (mask[r][i+1]<>2)) or ((mask[r][i+1]=2) and (mask[r][i]<>2)); //подвійний блок лівого профілю, орієнтований направо, //справа має замикати одиничний орієнтований наліво inc(i); end; if (mask[l][i]=3) then ok:=mask[r][i]=0; //одиничний блок лівого профілю, орієнтований направо, справа має замикати //подвійний орієнтований наліво inc(i); end; i:=1; while (i<=4) and (ok) do //аналогічна перевірка правого провілю begin if (mask[r][i]=0) then begin ok:=((mask[l][i]=3) and (mask[l][i+1]<>3)) or ((mask[l][i]<>3) and (mask[l][i+1]=3)); inc(i); end; if (mask[r][i]=2) then ok:=mask[l][i]=1; inc(i); end; check:=ok; end; begin all:=0; //формування масиву переходів for i := 1 to 24 do for j := 1 to 24 do if check(i,j) then begin inc(all); f[all]:=i; s[all]:=j; end; readln(n); fillchar(dp,sizeof(dp),0); //база динаміки dp[1,1]:=1; //динаміка for i := 2 to n do for j := 1 to all do dp[i,s[j]]:=(dp[i,s[j]]+dp[i-1,f[j]]) mod md; //будь-який спосіб розміщення триміно закінчується профілем номер 2 writeln(dp[n,2]); end.
Я робив так само, тільки прогавив два профіля. У мене їх було 22...
Поза форумом