TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

72.7% (8/11)

Tags

Description

定義費氏數列 Fii=0 如下:

{F0=0F1=1Fi+2=Fi+1+Fi,iN{0}

定義一個非負整數 x 是費波納契數,若且唯若存在 iN{0} 使得 Fi=x

如果一個非負整數的任意非空子字串所形成的數字都是費波納契數的話,我們稱它為「費波路納特契石數」。舉例來說,13 是個費波路納特契石數,因為 1313 都是費波納契數。

參加過昨天比賽的你,想問說為什麼這樣的數不叫做「超級費波納契數」嗎?因為「費波路納特契石數」的子序列「波路特石」是今年IOIC的超級總召,所以「費波路納特契石數」一詞本身就有「超級」的意思了。

給定 l,rN,請問在區間 [l,r] 中,共有幾個「費波路納特契石數」?

如果答對這道問題,可以得到很好看的特製波路ㄋ(balloon)喔!

Input Format

測資的唯一一行包含以空白字元分隔的兩個正整數 l,r,表示區間的左、右界。

  • 1lr1018

Output Format

輸出一個整數,代表區間 [l,r] 間的「費波路納特契石數」個數。

Sample Input 1

6 11

Sample Output 1

1

Hints

Problem Source

IOICamp 2022 Day5 pA

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~23 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2