시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 247 62 51 28.022%

문제

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

  • 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+KSBcdWI0NTAgXHVjMjE4IGFcdWM2NDAgYlx1YjI5NCAwXHVjNzNjXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBhICZsZTsgZjxzdWI+aTxcL3N1Yj4gJmxlOyBiIFx1Yzc3OCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4IGY8c3ViPmk8XC9zdWI+XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjU3MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhvdyBtYW55IEZpYnM/IiwiZGVzY3JpcHRpb24iOiI8cD5SZWNhbGwgdGhlIGRlZmluaXRpb24gb2YgdGhlIEZpYm9uYWNjaSBudW1iZXJzOjxcL3A+XHJcblxyXG48cD5mPHN1Yj4xPFwvc3ViPiZuYnNwOzo9IDE8YnIgXC8+XHJcbmY8c3ViPjI8XC9zdWI+Jm5ic3A7Oj0gMjxiciBcLz5cclxuZjxzdWI+bjxcL3N1Yj4mbmJzcDs6PSBmPHN1Yj5uLTE8XC9zdWI+Jm5ic3A7KyBmPHN1Yj5uLTI8XC9zdWI+Jm5ic3A7KG4gJmdlOyAzKTxcL3A+XHJcblxyXG48cD5HaXZlbiB0d28gbnVtYmVycyBhIGFuZCBiLCBjYWxjdWxhdGUgaG93IG1hbnkgRmlib25hY2NpIG51bWJlcnMgYXJlIGluIHRoZSByYW5nZSBbYSxiXS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHR3byBub24tbmVnYXRpdmUgaW50ZWdlciBudW1iZXJzIGEgYW5kIGIuIElucHV0IGlzIHRlcm1pbmF0ZWQgYnkgYT1iPTAuIE90aGVyd2lzZSwgYSZsdDs9YiZsdDs9MTAxMDAuIFRoZSBudW1iZXJzIGEgYW5kIGIgYXJlIGdpdmVuIHdpdGggbm8gc3VwZXJmbHVvdXMgbGVhZGluZyB6ZXJvcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IG9uIGEgc2luZ2xlIGxpbmUgdGhlIG51bWJlciBvZiBGaWJvbmFjY2kgbnVtYmVycyBmaSB3aXRoIGEmbHQ7PWZpJmx0Oz1iLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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