4206번 - 피보나치 단어 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB63521012127.191%

문제

피보나치 단어 수열은 다음과 같이 정의된다.

여기서 +는 두 문자열 이어 붙이는 것을 의미한다.

n F(n)
0 0
1 1
2 10
3 101
4 10110
5 10110101
6 1011010110110
7 101101011011010110101
8 1011010110110101101011011010110110
9 1011010110110101101011011010110110101101011011010110101

비트 패턴 p와 정수 n이 주어졌을 때, F(n)에 p가 몇 번 나오는지 구하는 프로그램을 작성하시오.

입력

테스트 케이스의 첫째 줄에는 n(0 ≤ n ≤ 100)이 주어진다. 둘째 줄에는 비트 패턴 p가 주어진다. p의 길이는 최대 100,000이고 비어있지 않은 문자열이다.

출력

각각의 테스트 케이스에 대해서, 케이스 번호와 F(n)에서 비트 패턴 p가 몇 번 등장하는지 출력한다. 이런 등장은 겹칠 수 있다. 이 값은 263보다 작다.

예제 입력 1 

6
10
7
10
6
01
6
101
96
10110101101101

예제 출력 1 

Case 1: 5
Case 2: 8
Case 3: 4
Case 4: 4
Case 5: 7540113804746346428
W3sicHJvYmxlbV9pZCI6IjQyMDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHViMmU4XHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHViMmU4XHVjNWI0IFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzgxNVx1Yzc1OFx1YjQxY1x1YjJlNC48XC9wPlxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZpYm8ucG5nXCIgc3R5bGU9XCJ3aWR0aDogMjkxcHg7IGhlaWdodDogNzZweDtcIiBcLz48XC9wPlxyXG48cD5cclxuXHRcdWM1ZWNcdWFlMzBcdWMxMWMgK1x1YjI5NCBcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0IFx1Yzc3NFx1YzViNCBcdWJkOTlcdWM3NzRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZCB0YWJsZS1jb25kZW5zZWRcIiBzdHlsZT1cIndpZHRoOiA1MCU7XCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JTtcIj5cclxuXHRcdFx0XHRuPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjQ1JTtcIj5cclxuXHRcdFx0XHRGKG4pPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQwPFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDE8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0MTA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0MTAxPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDQ8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDEwMTEwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDU8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDEwMTEwMTAxPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDY8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDEwMTEwMTAxMTAxMTA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0NzxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0MTAxMTAxMDExMDExMDEwMTEwMTAxPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDg8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDEwMTEwMTAxMTAxMTAxMDExMDEwMTEwMTEwMTAxMTAxMTA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0OTxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0MTAxMTAxMDExMDExMDEwMTEwMTAxMTAxMTAxMDExMDExMDEwMTEwMTAxMTAxMTAxMDExMDEwMTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG48cD5cclxuXHRcdWJlNDRcdWQyYjggXHVkMzI4XHVkMTM0IHBcdWM2NDAgXHVjODE1XHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgRihuKVx1YzVkMCBwXHVhYzAwIFx1YmE4NyBcdWJjODggXHViMDk4XHVjNjI0XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IG4oMCAmbGU7IG4gJmxlOyAxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJlNDRcdWQyYjggXHVkMzI4XHVkMTM0IHBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwLDAwMFx1Yzc3NFx1YWNlMCBcdWJlNDRcdWM1YjRcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzhcdWM2NDAgRihuKVx1YzVkMFx1YzExYyBcdWJlNDRcdWQyYjggXHVkMzI4XHVkMTM0IHBcdWFjMDAgXHViYTg3IFx1YmM4OCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzRcdWI3ZjAgXHViNGYxXHVjN2E1XHVjNzQwIFx1YWNiOVx1Y2U2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIDI8c3VwPjYzPFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDIwNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpYm9uYWNjaSBXb3JkcyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIEZpYm9uYWNjaSB3b3JkIHNlcXVlbmNlIG9mIGJpdCBzdHJpbmdzIGlzIGRlXHVmYjAxbmVkIGFzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZpYm8ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NzZweDsgd2lkdGg6MjkxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+SGVyZSArIGRlbm90ZXMgY29uY2F0ZW5hdGlvbiBvZiBzdHJpbmdzLiBUaGUgXHVmYjAxcnN0IGZldyBlbGVtZW50cyBhcmU6PFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkIHRhYmxlLWNvbmRlbnNlZFwiIHN0eWxlPVwid2lkdGg6NTAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPm48XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NDUlXCI+RihuKTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjEwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjEwMTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD40PFwvdGQ+XHJcblx0XHRcdDx0ZD4xMDExMDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD41PFwvdGQ+XHJcblx0XHRcdDx0ZD4xMDExMDEwMTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD42PFwvdGQ+XHJcblx0XHRcdDx0ZD4xMDExMDEwMTEwMTEwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPjEwMTEwMTAxMTAxMTAxMDExMDEwMTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD44PFwvdGQ+XHJcblx0XHRcdDx0ZD4xMDExMDEwMTEwMTEwMTAxMTAxMDExMDExMDEwMTEwMTEwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjk8XC90ZD5cclxuXHRcdFx0PHRkPjEwMTEwMTAxMTAxMTAxMDExMDEwMTEwMTEwMTAxMTAxMTAxMDExMDEwMTEwMTEwMTAxMTAxMDE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPkdpdmVuIGEgYml0IHBhdHRlcm4gcCBhbmQgYSBudW1iZXIgbiwgaG93IG9mdGVuIGRvZXMgcCBvY2N1ciBpbiBGKG4pPzxcL3A+IiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgdGhlIGludGVnZXIgbiAoMCZuYnNwOyZsZTsmbmJzcDtuICZsZTsmbmJzcDsxMDApLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIGJpdCBwYXR0ZXJuIHAuIFRoZSBwYXR0ZXJuIHAgaXMgbm9uZW1wdHkgYW5kIGhhcyBhIGxlbmd0aCBvZiBhdCBtb3N0IDEwMCAwMDAgY2hhcmFjdGVycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGRpc3BsYXkgaXRzIGNhc2UgbnVtYmVyIGZvbGxvd2VkIGJ5IHRoZSBudW1iZXIgb2Ygb2NjdXJyZW5jZXMgb2YgdGhlIGJpdCBwYXR0ZXJuIHAgaW4gRihuKS4gT2NjdXJyZW5jZXMgbWF5IG92ZXJsYXAuIFRoZSBudW1iZXIgb2Ygb2NjdXJyZW5jZXMgd2lsbCBiZSBsZXNzIHRoYW4gMjxzdXA+NjM8XC9zdXA+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > World Finals > ACM-ICPC World Finals 2012 D번

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)