#include <cstdio> #define DEBUG #ifdef DEBUG #undef DEBUG #endif using namespace std; long long C[20]; long long c; long long n; int main() { char ch; long long i = 0; long long p; /* We read char by char, because there can be zeros on the beginning */ while (1) { scanf("%c", &ch); if (ch < '0' || ch > '9') break; C[i++] = (ch - '0'); } n = i; p = 1; for (i=n-1; i>=0; i--) { c += C[i] * p; p *= 10; } #ifdef DEBUG printf("Read: %lld, length = %lld, p = %lld\n", c, n, p); #endif long long max_n = 15000; long long min_p = p / 10; bool min_exceeded = false; if (n > 4) { max_n = p + (p >> 1); } #ifdef DEBUG printf("max_n: %lld\n", max_n); printf("min_p: %lld\n", min_p); #endif long long cur[3] = { 0, 1, 1 }; for (i=2; i<max_n+10; i++) { cur[2] = cur[1] + cur[0]; if (!min_exceeded && cur[2] >= min_p) { min_exceeded = true; } if (cur[2] > p) cur[2] -= p; cur[0] = cur[1]; cur[1] = cur[2]; if (min_exceeded && cur[2] == c) { /* We have found it */ printf("%lld\n", i); return 0; } } printf("NIE\n"); }
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 69 70 71 72 73 74 | #include <cstdio> #define DEBUG #ifdef DEBUG #undef DEBUG #endif using namespace std; long long C[20]; long long c; long long n; int main() { char ch; long long i = 0; long long p; /* We read char by char, because there can be zeros on the beginning */ while (1) { scanf("%c", &ch); if (ch < '0' || ch > '9') break; C[i++] = (ch - '0'); } n = i; p = 1; for (i=n-1; i>=0; i--) { c += C[i] * p; p *= 10; } #ifdef DEBUG printf("Read: %lld, length = %lld, p = %lld\n", c, n, p); #endif long long max_n = 15000; long long min_p = p / 10; bool min_exceeded = false; if (n > 4) { max_n = p + (p >> 1); } #ifdef DEBUG printf("max_n: %lld\n", max_n); printf("min_p: %lld\n", min_p); #endif long long cur[3] = { 0, 1, 1 }; for (i=2; i<max_n+10; i++) { cur[2] = cur[1] + cur[0]; if (!min_exceeded && cur[2] >= min_p) { min_exceeded = true; } if (cur[2] > p) cur[2] -= p; cur[0] = cur[1]; cur[1] = cur[2]; if (min_exceeded && cur[2] == c) { /* We have found it */ printf("%lld\n", i); return 0; } } printf("NIE\n"); } |