//Evgenii Rudnyi, http://blog.rudnyi.ru/ 
// See http://blog.rudnyi.ru/ru/2015/01/numerologiya-s-krugom.html about the problem (in Russian)
// In English: https://www.facebook.com/video.php?v=593521430803116&set=vb.249880261833903&type=2&theater

// To compile
//  gcc -O3 360.cpp -lstdc++ -o 360.exe

#include <cstdlib>
#include <iostream>
#include <string>
#include <sstream>

char *HELP = "Usage:\n\n\
	360 [-v] n\n\n\
		-v the results will be written in stdout\n\
		n how many division should be performed\n\n\
	Example\n\n\
		360 -v 1000000\n";	

using namespace std;

int find_sum(const string &str)
{
	int sum = 0;
	for (int j = 0; j < str.size(); ++j)
	{
		sum = sum + str[j] - '0';
	}
	if (sum > 1073741824)
	{
		cout << "The sum is too big " << str << " " << sum << endl;
		exit(10);
	}
	if (sum > 9)
	{
		ostringstream os;
		os.precision(18);
  	os << sum;
		sum = find_sum(os.str());
	}
	return sum;
}

void divide_by_two(const string &str, string &res)
{
	int dig;
	int div;
	int rem;
	res.clear();
//cout << "  str " << str << endl;	
	dig = str[0] - '0';
	div = dig / 2;
	rem = dig % 2;
	if (div)
		res.append(1, char('0' + div));
	for (int i = 1; i < str.size(); ++i)
	{
		dig = rem*10 + str[i] - '0';
//cout << "  dig " << dig << endl;		
		div = dig / 2;
		rem = dig % 2;
		res.append(1, char('0' + div));	
//cout << "  res " << res << endl;	
	}
	if (rem)
		res.append(1, '5');		
//cout << "  res " << res << endl;	
}

int main(int argc, char *argv[])
{
	if (argc < 2)
  {
    cout << HELP;
    return 1;
  }
	int n = 0;
	bool verbose = false;
	int narg = 1;
	if (string(argv[narg]) == string("-v"))
	{		
		verbose = true;
		++narg;
		if (argc < 3)
	  {
  	  cout << HELP;
    	return 2;
  	}
	}
	n = atoi(argv[narg]);
	if (n < 0)
	{
		cout << "n must be positive" << endl;
		return 3;
	}
	bool failed = false;
	string str = "36";
	string tmp;
	int sum;
	for (int i = 0; i <=n; ++i) 
	{
		sum = find_sum(str);
		if (sum != 9)
		{
			cout << "Sum is not 9: " << str << " " << sum << endl;
			failed = true;
		}
		if (verbose)
			cout << str << " " << sum << endl;
		divide_by_two(str, tmp);
		str = tmp;
	}
	if (!failed)
		cout << "The rule is correct up to " << n << " divisions" << endl;
	return 0;
}