2013
11-10

# World Cup Noise

Background

“KO-RE-A, KO-RE-A” shout 54.000 happy football fans after their team has reached the semifinals of the FIFA World Cup in their home country. But although their excitement is real, the Korean people are still very organized by nature. For example, they have organized huge trumpets (that sound like blowing a ship’s horn) to support their team playing on the field. The fans want to keep the level of noise constant throughout the match.

The trumpets are operated by compressed gas. However, if you blow the trumpet for 2 seconds without stopping it will break. So when the trumpet makes noise, everything is okay, but in a pause of the trumpet,the fans must chant “KO-RE-A”!

Before the match, a group of fans gathers and decides on a chanting pattern. The pattern is a sequence of 0′s and 1′s which is interpreted in the following way: If the pattern shows a 1, the trumpet is blown. If it shows a 0, the fans chant “KO-RE-A”. To ensure that the trumpet will not break, the pattern is not allowed to have two consecutive 1′s in it.

Problem

Given a positive integer n, determine the number of different chanting patterns of this length, i.e., determine the number of n-bit sequences that contain no adjacent 1′s. For example, for n = 3 the answer is 5 (sequences 000, 001, 010, 100, 101 are acceptable while 011, 110, 111 are not).

The first line contains the number of scenarios.

For each scenario, you are given a single positive integer less than 45 on a line by itself.

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the number of n-bit sequences which have no adjacent 1′s. Terminate the output for the scenario with a blank line.

2
3
1

Scenario #1:
5

Scenario #2:
2

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner scan = new Scanner(new BufferedInputStream(System.in));
if (scan.hasNext()) {
long[] f = new long[46];
f[0] = 0;
f[1] = 2;
f[2] = 3;
for (int i = 3; i <= 45; i++) {
f[i] = f[i - 1] + f[i - 2];
}
int n = scan.nextInt();
for (int i = 1; i <= n; i++) {
int a = scan.nextInt();
System.out.println("Scenario #"+i+":");
System.out.println(f[a]);
System.out.println();
}

}
}
}

1. 各有所需，各位又有几个喜欢听戏曲的？片子质量如何，看了以后每个人的心情又如何，这个只有自己体会，喜剧片？老梗？能和自己产生共鸣的就是好片，至少自己开心了，强行给自己一个高台阶何必呢?我个人觉得是好片。

2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)

3. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

4. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮