collen7873   4년 전

문제

"대~한민국, 대~한민국!!" 2002년, 한국이 월드컵 4강에 오른 후 붉은 악마들의 응원이 울려 퍼진다.
사람들의 흥분은 아직 가시지 않았지만, 한국인들은 천성이 매우 조직적이다.
팬들은 선수들을 응원하기 위해 거대한 응원용 트럼펫을 연주할 계획 중이다.
사람들은 경기가 진행되는 동안 응원이 계속되기를 원한다.

고압가스로 연주되는 초고가 트럼펫은 연속해서 2초 이상 불 경우 망가지고 만다.
때문에 트럼펫이 소리를 한 번 내고 축구 팬들은 "대~한민국"을 외치고 또다시 트럼펫을 연주해야 한다.

경기 시작 전, 응원단은 모두 모여 응원 패턴을 결정하였다.
패턴은 0과 1로 이루어져 있다.
1은 트럼펫의 연주를 의미하고 0은 응원단이 "대~한민국" 외치는 것을 의미한다.
하지만 트럼펫이 망가지면 안 되기 때문에 1이 연이어 연속되어서는 안 된다.

이제 양수 N이 주어진다. N 자리에 들어갈 수 있는 서로 다른 패턴의 경우의 수를 구하여라.
예를 들어 N = 3일 경우 답은 5이다. [000, 001, 010, 110, 101] 은 가능한 패턴의 집합이고, [001, 110, 111] 의 집합은 답이 될 수 없다.

입력

첫 번째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 45 미만인 하나의 양의 정수가 주어진다.

출력

모든 시나리오 출력의 첫 번째 줄에는 "Scenario #i:" 을 포함하며 i는 1부터 시작한다.
그 다음 줄에는 연속된 1을 포함하지 않는 응원 패턴의 숫자를 출력한다.
각 시나리오의 종료는 한 줄의 공백을 이용한다.

댓글을 작성하려면 로그인해야 합니다.