1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 18;
const int MAXK = 1350000;
const long long MOD = 1000000000000000000LL;

char word[MAXN + 5];
long long f[2];
string pattern;

inline bool match(long long num);

int main() {
    scanf("%s", word);  
    pattern = string(word);
    reverse(pattern.begin(), pattern.end());
    f[0] = f[1] = 1LL;
    for(int i = 2; i < MAXK; ++i) {
        int ind = i & 1 ? 1 : 0;
        f[ind] = (f[0] + f[1]) % MOD;
        if(match(f[ind])) {
            printf("%d\n", i + 1);
            return 0;
        }
    }
    printf("NIE\n");
    return 0;
}

inline bool match(long long num) {
    char cnum[20];
    sprintf(cnum, "%lld", num);
    string snum = string(cnum);
    reverse(snum.begin(), snum.end());
    if(pattern.size() > snum.size()) {
        return false;
    }
    for(int i = 0; i < pattern.size(); ++i) {
        if(pattern[i] != snum[i]) return false;
    }
    return true;
}