Problemas
0과 1의 비트로 구성된 문자열 피보나치의 정의는 다음과 같다.
F(N) = 0 (N == 0) F(N) = 1 (N == 1) F(N) = F(N - 1) + F(N - 2) (N >= 2)
문자열 피보나치의 정의에서 ‘ + ’ 는 아래 예시와 같이 문자열을 이어 붙이는 것이다.
<예시>
N 과 비트 패턴 P 가 주어질 때, F(N)에서 패턴 P 가 몇 번 나오는지 구하는 프로그램을 작성하시오.
Entrada
첫 행에 정수 N( 0≤N≤100 ) 이 주어진다.
다음 행에 비트 패턴 P 가 주어진다. 이러한 형식으로 여러 개의 테스트 케이스(5개 이하)가 입력될 수 있다.
입력의 마지막은 파일의 끝으로 한다. 패턴 P 에는 적어도 하나의 비트가 존재하며 길이는 100,000 이하이다.
Salida
각 테스트 케이스에 대하여 패턴 P 가 F(N) 에 몇 번 나오는지 아래 예제와 같은 형식으로 출력하시오.
F(N)에서 패턴 P 는 겹쳐질 수 있다. 나올 수 있는 경우의 수는 263 이하이다.
Ejemplo
6
10
7
10
6
01
6
101
96
10110101101101
Case 1: 5
Case 2: 8
Case 3: 4
Case 4: 4
Case 5: 7540113804746346428
Fuente
ACM ICPC 2012 World Final
Debes iniciar sesión para escribir código.