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
#include <iostream>
#include <string>
using namespace std;

#define ile_fib 3000
#define stringLength 1000

string addStringNumbers(string, string);
char addCharNumbers(char, char, bool &);
void removeLeadingZerosFromString(string &);

int main() {
	string fib[ile_fib];
	string searchedSubstring;
	
	for(int i = 0; i < stringLength; i++)
	    fib[0] += "0";
	
	for(int i = 0; i < stringLength - 1; i++)
	    fib[1] += "0";
	fib[1] += "1";
	
// 	cout << fib[0] << endl << fib[1] << endl;
	
	for(int i = 2; i < ile_fib; i++)
	{
	    fib[i] = addStringNumbers(fib[i - 2], fib[i - 1]);
	   // cout << fib[i] << endl;
	}
	
	cin >> searchedSubstring;
// 	cout << searchedSubstring;
    
    // removeLeadingZerosFromString(searchedSubstring);
    
    // cout << searchedSubstring << endl;
    
    int correctPosition = stringLength - searchedSubstring.length();
    // cout << correctPosition << endl;
    bool fibFound = false;
    for(int i = 0; i < ile_fib; i++)
    {
        // cout << fib[i].rfind(searchedSubstring) << endl;
        if (fib[i].rfind(searchedSubstring) == correctPosition)
        {
            cout << i << endl;
            fibFound = true;
            break;
        }
    }
    
    if(!fibFound)
        cout << "NIE";
    
	return 0;
}

string addStringNumbers(string num1, string num2)
{
	string sumString;
	int longestString;
	bool addOneInMemory = false;
	char d1, d2;
	
	num1.length() > num2.length() ? longestString = num1.length() : longestString = num2.length();
	
	for(int i = 0; i < longestString; i++)
	{
		d1 = num1[longestString - i - 1];
		d2 = num2[longestString - i - 1];
		sumString = addCharNumbers(d1, d2, addOneInMemory) + sumString;
	}
	
	if(addOneInMemory)
	    sumString = "1" + sumString;
	
	return sumString;
}

char addCharNumbers(char d1, char d2, bool &addOneInMemory)
{
	int result = 0;
	result = d1 - '0' + d2 - '0';
// 	cout << d1 << " " << d2 << " " << result << endl;
	if(addOneInMemory)
	    result++;
	if(result > 9)
	{
		result %= 10;
		addOneInMemory = true;
	}
	else
	    addOneInMemory = false;
	    
	return result + '0';
}

void removeLeadingZerosFromString(string & searchedSubstring)
{
    while(searchedSubstring[0] == '0')
        searchedSubstring.erase(0,1);
}