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
65
66
67
68
//
//  Created by Kamil Borzym on 30/09/15.
//  Copyright © 2015 kam800. All rights reserved.
//

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

static long long tenPow(long p) {
    if (p<1) {
        return 1;
    }
    long long result = 1;
    while (p) {
        --p;
        result *= 10;
    }
    return result;
}

static long long periodForN(long n) {
    if (n == 0) {
        abort();
    }
    if (n == 1) {
        return 60;
    }
    if (n == 2) {
        return 300;
    }
    return 15 * tenPow(n-1);
}

int main () {
    char input[19] = { 0 };
    scanf("%18[0-9]", input);
//    char *input = "123456789012345678";
//    char *input = "025";
//    char *input = "222";

    long n = strlen(input);
    long long c = atoll(input);

    long long period = periodForN(n);
    long long limit = tenPow(n);

//    fprintf(stderr, "n=%ld c=%lld period=%lld limit=%lld\n", n, c, period, limit);
    long long ttl = period;
    long long current = 1;
    long long prev = 0;
    while (ttl) {
        long long next = current + prev;
        if (next > limit) {
            next -= limit;
        }
        if (next == c) {
            long long k = period + period + 2 - ttl;
            printf("%lld\n", k);
            return 0;
        }
        prev = current;
        current = next;
        --ttl;
    }
    printf("NIE\n");
    return 0;
}