609 . 填積木問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

smgshabc123

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

17.6% (3/17)

Tags

apcsc apcsc-recursion

Description

桌上有一盒積木，每個積木的大小都是 $1\times 2$，而旁邊有一個大小為 $n\times 3$ 的盒子，如果要用積木將盒子排滿，有幾種方法呢？

舉例來說，如果 $n=2$，你就必須輸出 $3$，因為答案有以下三種。

而當 $n=4$ 時，就必須輸出 $11$，有以下十一種排法。

  • 提示：
  1. 一個 $4\times 3$ 的盒子的最上面一排只有這三種排法

  1. 而這個區域可以分為這兩種情形

Input Format

輸入只有一行，表示題目的數字 $n$。

  • $1 \le n \le 50$，且 $n$ 為偶數。

Output Format

輸出一行一個整數，表示排滿盒子的可能數。

Sample Input 1

2

Sample Output 1

3

Sample Input 2

4

Sample Output 2

11

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~7 $1\le n\le 22$ 30
3 0~12 無額外限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3
1 1000 524288 65536 1 2 3
2 1000 524288 65536 2 3
3 1000 524288 65536 2 3
4 1000 524288 65536 2 3
5 1000 524288 65536 2 3
6 1000 524288 65536 2 3
7 1000 524288 65536 2 3
8 1000 524288 65536 3
9 1000 524288 65536 3
10 1000 524288 65536 3
11 1000 524288 65536 3
12 1000 524288 65536 3
Submit
Back to Top