Мощення коридору

Подивіться, як покриті клітинки останнього стовпця підлоги, і введіть $2$ кількості: повні підлоги та підлоги без однієї кутової клітинки.

1. Нехай $a(n)$ — кількість вимощень підлоги $3$ на $n$, а $b(n)$ — кількість вимощень такої підлоги, з якої вилучено нижню клітинку останнього стовпця. Плитка вздовж підлоги накриває $2$ клітинки одного рядка, а плитка впоперек — $2$ клітинки одного стовпця.
2. В останньому стовпці повної підлоги або верхні $2$ клітинки накриває плитка впоперек, що змушує нижню клітинку взяти плитку вздовж і лишає підлогу з $n-1$ стовпців без нижньої кутової клітинки, або те саме стається з нижніми $2$ клітинками, або всі $3$ клітинки беруть плитки вздовж, що покривають останні $2$ стовпці; отже $a(n)=a(n-2)+2b(n-1)$.
3. Для підлоги без нижньої клітинки останнього стовпця верхні $2$ клітинки цього стовпця або накриває одна плитка впоперек, і лишається повна підлога з $n-1$ стовпців, або кожна бере плитку вздовж, що змушує нижню клітинку стовпця $n-1$ теж узяти її й лишає підлогу з $n-2$ стовпців без кутової клітинки; отже $b(n)=a(n-1)+b(n-2)$.
4. Починаючи з $a(0)=1$ і $b(1)=1$, отримуємо $a(2)=3$, $b(3)=4$, $a(4)=11$, $b(5)=15$, $a(6)=41$, $b(7)=56$, $a(8)=153$, $b(9)=209$ і нарешті $a(10)=153+2\times 209=571$.

Відповідь: $571$