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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/* 2015
 * Maciej Szeptuch
 * II UWr
 */
#include <cstdio>
#include <cstring>
#include <unordered_set>

char current[32],
     next[32],
     previous[32],
     suffix[32];
int suffixLength;
std::unordered_set<std::string> seen;

void sum(char *result, const char *A, const char *B, const int size);

int main(void)
{
    scanf("%s", suffix);
    suffixLength = strlen(suffix);
    memset(previous, '0', suffixLength);
    previous[suffixLength - 1] = '0';
    memset(current, '0', suffixLength);
    current[suffixLength - 1] = '1';
    if(suffixLength == 1 && suffix[0] == '0')
    {
        puts("0");
        return 0;
    }

    for(long long unsigned int s = 1; s; ++ s)
    {
        if(!strcmp(current, suffix))
        {
            printf("%llu\n", s);
            return 0;
        }

        std::string key = previous;
        key += current;
        if(seen.find(key) != seen.end())
            break;

        seen.insert(key);
        sum(next, current, previous, suffixLength);
        memcpy(previous, current, suffixLength);
        memcpy(current, next, suffixLength);
    }

    puts("NIE");
    return 0;
}

void sum(char *result, const char *A, const char *B, const int size)
{
    int mov = 0;
    for(int s = size - 1; s >= 0; -- s)
    {
        result[s] = mov + A[s] - '0' + B[s] - '0';
        mov = result[s] / 10;
        result[s] = (result[s] % 10) + '0';
    }
}