선사 시대 운영체제

면접 대비

시간 제한1초메모리 제한128 MB

요약

길이 n의 이진 문자열 가운데 D가 연속으로 나오지 않는 경우의 수를 구한다. D는 DOORS, O는 다른 브랜드를 뜻하며 n은 최대 40이다.

난이도: 쉬움10점 중 3점
유형: 동적 계획법, 조합론, 수학, 배열
정답자: 아직 제출이 없습니다

문제

때는 2254년. 오하이오 스미스(Ohio Smith)는 고대 운영체제를 연구하는 전문가이다. 그는 연구를 위해 약 250년 전에 쓰이던 여러 운영체제를 한 대의 컴퓨터에 설치하려고 한다.

이전 연구에 따르면 이런 고대 운영체제들은 대부분 설치 순서가 결과에 영향을 주지 않는다. 그런데 'DOORS'라는 브랜드의 운영체제에는 독특한 제약이 있다. DOORS는 두 버전을 연속으로 설치할 수 없어서, 두 DOORS 설치 사이에는 반드시 다른 브랜드의 운영체제가 하나 이상 설치되어 있어야 한다.

오하이오는 정확히 $n$ 개의 운영체제를 설치하려고 하며, 각 설치 자리마다 DOORS 또는 다른 운영체제 중 하나를 고른다. 만들 수 있는 서로 다른 유효한 설치 순서의 개수를 구하여라.

입력

첫째 줄에 시나리오의 개수가 주어진다.

각 시나리오는 한 줄에 설치할 운영체제의 개수 $n$ ( $1 \le n \le 40$ )이 정수로 주어진다.

출력

각 시나리오마다 먼저 Scenario i: 형식의 줄을 출력한다. 여기서 $i$ 는 1부터 시작하는 시나리오 번호이다. 그다음 줄에 유효한 설치 순서의 개수를 출력한다. 연속한 두 시나리오 사이에는 빈 줄을 하나 출력한다.

힌트

$n = 3$ 일 때 운영체제를 설치하는 유효한 방법은 5가지이다 (D = DOORS, O = 다른 운영체제):

D, O, O
O, O, O
O, O, D
O, D, O
D, O, D

예제2

예제 1
입력
```
2
3
9
```
예상 출력
```
Scenario 1:
5

Scenario 2:
89
```

예제 2

입력

예상 출력

Scenario 1:
2

Scenario 2:
3

Scenario 3:
5

Scenario 4:
8