본문 바로가기

PKU & UVa problems/Translated problem

PKU 1953. World Cup Noise

월드컵 소음
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 5818 Accepted: 2851

설명

배경지식
"KO-RE-A, KO-RE-A" 54000명의 행복에 가득찬 축구 팬들이, 한국 팀이 조국에서 열린 FIFA 월드컵 준결승에 올랐을때 소리쳤다. 그러나 비록 그들의 그런 흥분감이 정말이었더라도, 한국 사람들은 여전히 조직적이었다. 예를 들면 그들은 배의 고동소리와 비슷하게 들릴 정도의, 큰 트럼펫들을 준비하여 경기장에서 뛰는 한국팀을 응원했다. 팬들은 경기가 진행되는 내내 소음의 수준을 유지하려 했다.
트럼펫은 압축가스로 작동되었다. 그러나 만약 트럼펫을 2초 이상 쉬지 않고 분다면 그것은 고장날 것이다. 그래서 트럼펫으로 소리를 낼 때에는, 다른 것은 전부 괜찮지만 가끔씩 쉬어서 불어야 하며, 그래서 팬들은 "KO-RE-A"! 라고 외쳐야 한다.
경기 전에 한 그룹의 팬들이 모여서 외치는 패턴을 결정하고 있다. 패턴은 0과 1들로 설명될 수 있는데, 그것들은 다음 설명에 따라 설명된다. 만약 패턴이 1을 보인다면 트럼펫을 분다. 만약 패턴이 0을 보인다면, 팬들이 "KO-RE-A" 라고 외친다. 트럼펫이 고장나지 않도록 하기 위해서, 패턴에는 두 개의 1이 연속되어 나오는 것이 허용되지 않는다.
문제
하나의 양정수 n이 주어지는데, 이 n은 정해진 길이에서 다르게 외치는 패턴이 얼마나 있는지를 결정합니다. 즉, 1들이 인접하지 않은 n-비트 수열의 개수를 결정합니다. 예를 들면, n = 3 이면 답은 5 (수열 000, 001, 010, 100, 101 들은 가능한 반면 011, 110, 111은 불가)입니다.

입력

첫 번째 줄은 시나리오의 개수를 포함합니다.
각 시나리오는, 한 줄에 45 보다 작은 하나의 양정수를 스스로 정합니다.

출력

각 시나리오의 출력은, i가 1부터 시작하여 시나리오의 개수를 나타낼 때, "Scenario #i:" 를 포함하는 줄로 시작합니다. 그러고 나서 1들이 인접하지 않은 n-비트 수열들의 개수를 한 줄에 나타냅니다. 시나리오의 출력을 종료할 때엔 빈 줄을 넣습니다.

입력 예시

2
3
1

출력 예시

Scenario #1:
5

Scenario #2:
2

Source

TUD Programming Contest 2002, Darmstadt, Germany

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 2551. Ones  (5) 2009.01.21
PKU 1904. King's Quest  (8) 2009.01.15
PKU 2845. 01000001  (0) 2009.01.02
PKU 1089. Intervals  (6) 2008.12.21
PKU 1298. The Hardest Probelm Ever  (0) 2008.12.04