#undef RUBY #ifdef RUBY # Helpful Ruby helper used to find border values used by this algorithm # Run it with: ruby fibonacci.cpp k = 2; p = 0; q = 1; r = 1 next_pow = 10 loop do if r > next_pow puts next_pow, k puts next_pow *= 10 exit if next_pow > 10**18 end k+=1 p, q, r = [q, r, (p+q)] end __END__ #endif #include <iostream> #include <string> #include <math.h> using namespace std; const string INVALID("NIE"); typedef unsigned long long F; typedef pair<F, int> SUFFIX_PAIR; SUFFIX_PAIR read_suffix() { char input_buff; SUFFIX_PAIR retval; F suffix = 0; int len = 0; while (cin >> input_buff) { if (input_buff >= '0' && input_buff <= '9') { suffix = suffix * 10 + (input_buff - '0'); len++; } } return SUFFIX_PAIR(suffix, len); } void output(F k) { cout << k; exit(0); } void special_cases(SUFFIX_PAIR sp) { if (sp.second == 1 && (sp.first == 0 || sp.first == 1)) { output(sp.first); } } int main(int argc, char **argv) { F k, min_k = 0; SUFFIX_PAIR suffix_pair = read_suffix(); int len = suffix_pair.second; F suffix = suffix_pair.first; F modulo = pow(10, len); special_cases(suffix_pair); switch(len) { case 1: min_k = 7; break; case 2: min_k = 12; break; case 3: min_k = 17; break; case 4: min_k = 21; break; case 5: min_k = 26; break; case 6: min_k = 31; break; case 7: min_k = 36; break; case 8: min_k = 40; break; case 9: min_k = 45; break; case 10: min_k = 50; break; case 11: min_k = 55; break; case 12: min_k = 60; break; case 13: min_k = 64; break; case 14: min_k = 69; break; case 15: min_k = 74; break; case 16: min_k = 79; break; case 17: min_k = 84; break; case 18: min_k = 88; break; } F p = 0, q = 1, r = 1, new_r; for (k = 2; k < pow(10, len+1) ; k++) { if (r == suffix && k >= min_k) { output(k); } new_r = (q+r) % modulo; p = q; q = r; r = new_r; } cout << INVALID; return 0; }
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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #undef RUBY #ifdef RUBY # Helpful Ruby helper used to find border values used by this algorithm # Run it with: ruby fibonacci.cpp k = 2; p = 0; q = 1; r = 1 next_pow = 10 loop do if r > next_pow puts next_pow, k puts next_pow *= 10 exit if next_pow > 10**18 end k+=1 p, q, r = [q, r, (p+q)] end __END__ #endif #include <iostream> #include <string> #include <math.h> using namespace std; const string INVALID("NIE"); typedef unsigned long long F; typedef pair<F, int> SUFFIX_PAIR; SUFFIX_PAIR read_suffix() { char input_buff; SUFFIX_PAIR retval; F suffix = 0; int len = 0; while (cin >> input_buff) { if (input_buff >= '0' && input_buff <= '9') { suffix = suffix * 10 + (input_buff - '0'); len++; } } return SUFFIX_PAIR(suffix, len); } void output(F k) { cout << k; exit(0); } void special_cases(SUFFIX_PAIR sp) { if (sp.second == 1 && (sp.first == 0 || sp.first == 1)) { output(sp.first); } } int main(int argc, char **argv) { F k, min_k = 0; SUFFIX_PAIR suffix_pair = read_suffix(); int len = suffix_pair.second; F suffix = suffix_pair.first; F modulo = pow(10, len); special_cases(suffix_pair); switch(len) { case 1: min_k = 7; break; case 2: min_k = 12; break; case 3: min_k = 17; break; case 4: min_k = 21; break; case 5: min_k = 26; break; case 6: min_k = 31; break; case 7: min_k = 36; break; case 8: min_k = 40; break; case 9: min_k = 45; break; case 10: min_k = 50; break; case 11: min_k = 55; break; case 12: min_k = 60; break; case 13: min_k = 64; break; case 14: min_k = 69; break; case 15: min_k = 74; break; case 16: min_k = 79; break; case 17: min_k = 84; break; case 18: min_k = 88; break; } F p = 0, q = 1, r = 1, new_r; for (k = 2; k < pow(10, len+1) ; k++) { if (r == suffix && k >= min_k) { output(k); } new_r = (q+r) % modulo; p = q; q = r; r = new_r; } cout << INVALID; return 0; } |