#include <iostream> #include <string> #include <sstream> using namespace std; string fib[10000]; int P[1000]; int KMP (string a, string b) { string last='#'+a+'#'+b; int t=P[0]; for (int i=2; i <=last.size(); i++) { while (t>0 && last[t+1]!=last[i]) t=P[t]; if(last[t+1]==last[i]) t++; P[i]=t; } } int main() { fib[0]='0'; fib[1]='1'; for (int k=2; k <=1000; k++) { string m, w; m=fib[k-2]; w=fib[k-1]; stringstream s; stringstream suma; for( int i = m.size() - 1; i >= 0; i-- ) s << m[ i ]; m = s.str(); s.str( "" ); for( int i = w.size() - 1; i >= 0; i-- ) s << w[ i ]; w = s.str(); int x, zap = 0; for( int i = 0; i < w.size(); i++ ) { if( m.size() > i && w.size() > i ) { x=( char ) m[i] - 48 +(char) w[i] - 48; } else { x=( (char) w[i] - 48 ); } x += zap; if( x > 9 ) { zap = 1; suma << x % 10; } else { suma << x; zap = 0; } } if( zap) { suma << zap; } string wynik = suma.str(); string g; for( int i = wynik.size() - 1; i >= 0; i-- ) { g.push_back(wynik[i]); } fib[k]=g; } // KMP //cout << fib[10]; string st; cin >>st; int sw=0; int i=0; while (st[i]=='0' && i< st.size()) { sw++; i++; } string t; for( int i =sw; i<st.size(); i++ ) { t.push_back(st[i]); } //cout << t <<endl; for (int i=0; i <10000; i++) { KMP(t,fib[i]); if(P[t.size()+fib[i].size()+1]==t.size()) { cout << i; return 0; } for(int j=0; j <1000; j ++) { P[j]=0; } } cout << "NIE"; 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 117 118 119 120 121 122 123 124 125 | #include <iostream> #include <string> #include <sstream> using namespace std; string fib[10000]; int P[1000]; int KMP (string a, string b) { string last='#'+a+'#'+b; int t=P[0]; for (int i=2; i <=last.size(); i++) { while (t>0 && last[t+1]!=last[i]) t=P[t]; if(last[t+1]==last[i]) t++; P[i]=t; } } int main() { fib[0]='0'; fib[1]='1'; for (int k=2; k <=1000; k++) { string m, w; m=fib[k-2]; w=fib[k-1]; stringstream s; stringstream suma; for( int i = m.size() - 1; i >= 0; i-- ) s << m[ i ]; m = s.str(); s.str( "" ); for( int i = w.size() - 1; i >= 0; i-- ) s << w[ i ]; w = s.str(); int x, zap = 0; for( int i = 0; i < w.size(); i++ ) { if( m.size() > i && w.size() > i ) { x=( char ) m[i] - 48 +(char) w[i] - 48; } else { x=( (char) w[i] - 48 ); } x += zap; if( x > 9 ) { zap = 1; suma << x % 10; } else { suma << x; zap = 0; } } if( zap) { suma << zap; } string wynik = suma.str(); string g; for( int i = wynik.size() - 1; i >= 0; i-- ) { g.push_back(wynik[i]); } fib[k]=g; } // KMP //cout << fib[10]; string st; cin >>st; int sw=0; int i=0; while (st[i]=='0' && i< st.size()) { sw++; i++; } string t; for( int i =sw; i<st.size(); i++ ) { t.push_back(st[i]); } //cout << t <<endl; for (int i=0; i <10000; i++) { KMP(t,fib[i]); if(P[t.size()+fib[i].size()+1]==t.size()) { cout << i; return 0; } for(int j=0; j <1000; j ++) { P[j]=0; } } cout << "NIE"; return 0; } |