#include <iostream>
using namespace std;

static
int const fibonacci_numbers[47] = {
	1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
	610, 987, 1597, 2584, 4181, 6765, 10946, 17711,
	28657, 46368, 75025, 121393, 196418, 317811, 514229,
	832040, 1346269, 2178309, 3524578, 5702887, 9227465,
	14930352, 24157817, 39088169, 63245986, 102334155,
	165580141, 267914296, 433494437, 701408733,
	1134903170, 1836311903, 2147483647
};

static
int find_fibonacci_number( int n ) {
	for ( int i = 1; true; ++i ) {
		if ( fibonacci_numbers[i] >= n ) {
			return fibonacci_numbers[i - 1];
		}
	}
}

template <typename Type>
static
int search( Type obj, Type *array, int a, int c, int count ) {
	if ( c < a ) {
		return -10000;
	} else if ( a == c ) {
		if ( array[a] == array[c] ) {
			return count + 1;
		} else {
			return -10000;
		}
	}

	int fib = find_fibonacci_number( c - a + 1 );

	int b;

	if ( obj - array[a] > array[c] - obj ) {
		b = a + fib;
	} else {
		b = c - fib;
	}

	// cout << "\t" << fib << ":  " << a << " " << b << " " << c << endl;

	if ( array[b] == obj ) {
		return count + 1;
	} else if ( obj < array[b] ) {
		return search( obj, array, a, b - 1, count + 1 );
	} else {
		return search( obj, array, b + 1, c, count + 1 );
	}
}

int search( int obj, int *array, int n ) {
	// cout << "Searching for " << obj << " in an array of size " << n << endl;
	int s = search( obj, array, 0, n - 1, 0 );
	// cout << " -- found in " << s << endl;
	return s;
}

int main() {
	int array[128];

	for ( int i = 0; i < 128; ++i ) {
		array[i] = i;
	}

	for ( int i = 1; i < 128; ++i ) {
		int sum = 0;
		int mx = 0;

		for ( int j = 0; j < i; ++j ) {
			int s = search( j, array, i );
			sum += s;
			mx = std::max( mx, s );
		}

		cout << i << ":\t" << sum << "\t" << "\t" << mx << "\t" << static_cast<double>( sum )/i << endl;
	}

	return 0;
}