시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB179150037728.889%

문제

피보나치 수의 정의는 다음과 같다.

  • f1 := 1
  • f2 := 2
  • fn := fn-1 + fn-2 (n ≥ 3)

두 수 a와 b가 주어졌을 때, 구간 [a, b]에 포함되는 피보나치 수의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 음이 아닌 두 정수 a와 b로 이루어져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다. (a ≤ b ≤ 10100) 두 수 a와 b는 불필요한 0으로 시작하지 않는다.

출력

각 테스트 케이스에 대해서, a ≤ fi ≤ b 인 피보나치 수 fi의 개수를 출력한다.

예제 입력 1

10 100
1234567890 9876543210
0 0

예제 출력 1

5
4
W3sicHJvYmxlbV9pZCI6IjY1NzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1Yzc1OCBcdWM4MTVcdWM3NThcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5mPHN1Yj4xPFwvc3ViPiA6PSAxPFwvbGk+XHJcblx0PGxpPmY8c3ViPjI8XC9zdWI+IDo9IDI8XC9saT5cclxuXHQ8bGk+ZjxzdWI+bjxcL3N1Yj4gOj0gZjxzdWI+bi0xPFwvc3ViPiArIGY8c3ViPm4tMjxcL3N1Yj4gKG4gJmdlOyAzKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjQ1MCBcdWMyMTggYVx1YzY0MCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWQ2Y1x1YWMwNCBbYSwgYl1cdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViMjk0IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YjQ1MCBcdWM4MTVcdWMyMTggYVx1YzY0MCBiXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChhICZsZTsgYiAmbGU7IDEwPHN1cD4xMDA8XC9zdXA+KSBcdWI0NTAgXHVjMjE4IGFcdWM2NDAgYlx1YjI5NCBcdWJkODhcdWQ1NDRcdWM2OTRcdWQ1NWMgMFx1YzczY1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgYSAmbGU7IGY8c3ViPmk8XC9zdWI+ICZsZTsgYiBcdWM3NzggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOCBmPHN1Yj5pPFwvc3ViPlx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjY1NzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIb3cgbWFueSBGaWJzPyIsImRlc2NyaXB0aW9uIjoiPHA+UmVjYWxsIHRoZSBkZWZpbml0aW9uIG9mIHRoZSBGaWJvbmFjY2kgbnVtYmVyczo8XC9wPlxyXG5cclxuPHA+ZjxzdWI+MTxcL3N1Yj4mbmJzcDs6PSAxPGJyIFwvPlxyXG5mPHN1Yj4yPFwvc3ViPiZuYnNwOzo9IDI8YnIgXC8+XHJcbmY8c3ViPm48XC9zdWI+Jm5ic3A7Oj0gZjxzdWI+bi0xPFwvc3ViPiZuYnNwOysgZjxzdWI+bi0yPFwvc3ViPiZuYnNwOyhuICZnZTsgMyk8XC9wPlxyXG5cclxuPHA+R2l2ZW4gdHdvIG51bWJlcnMgYSBhbmQgYiwgY2FsY3VsYXRlIGhvdyBtYW55IEZpYm9uYWNjaSBudW1iZXJzIGFyZSBpbiB0aGUgcmFuZ2UgW2EsYl0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiB0d28gbm9uLW5lZ2F0aXZlIGludGVnZXIgbnVtYmVycyBhIGFuZCBiLiBJbnB1dCBpcyB0ZXJtaW5hdGVkIGJ5IGE9Yj0wLiBPdGhlcndpc2UsIGEmbHQ7PWImbHQ7PTEwMTAwLiBUaGUgbnVtYmVycyBhIGFuZCBiIGFyZSBnaXZlbiB3aXRoIG5vIHN1cGVyZmx1b3VzIGxlYWRpbmcgemVyb3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCBvbiBhIHNpbmdsZSBsaW5lIHRoZSBudW1iZXIgb2YgRmlib25hY2NpIG51bWJlcnMgZmkgd2l0aCBhJmx0Oz1maSZsdDs9Yi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > University of Ulm Local Contest > University of Ulm Local Contest 2000 F번