/*
 * nine.cpp : Solve the "Nine 9s" puzzle
 *
 * Copyright (c) 2002 Daniel Hartmeier <daniel@benzedrine.ch>
 * All rights reserved.
 *
 * See http://www.itasoftware.com/careers/puzzle_archive.html
 *
 *   Nine 9s
 *
 *     Combining nine 9s with any number of the operators +, -, *, /, (, ),
 *     what is the smallest positive integer that cannot be expressed?
 *
 *     Hints:
 *       1) The answer isn't zero. You can express zero like this:
 *            (9 - 9) * (9 + 9 + 9 + 9 + 9 + 9 + 9)
 *          Also, zero isn't a positive integer.
 *       2) The answer isn't one. You can express one like this:
 *            9 - (9 * 9 - 9)/9 + 9 - 9 + 9 - 9
 *       3) It's not a trick question.
 *       4) Be sure to handle parentheses correctly.
 *
 *     Notes:
 *       You cannot exponentiate.
 *       You cannot concatenate (for example, put two 9s together to make 99).
 *       The - operator can be used in either its binary or unary form.
 *       Assume base 10.
 *
 */

#include <iostream>
#include <string>
#include <set>

using namespace std;

long long gcd(long long m, long long n)
{
	while (n != 0) {
		long long t = m % n;
		m = n;
		n = t;
	}
	return m;
}

struct real {
	long long a, b;
	real(long long _a, long long _b) : a(_a), b(_b) {
		long long d = gcd(a, b);
		if (d != 0 && d != 1 && d != -1) {
			a /= d;
			b /= d;
		}
		if (b < 0) {
			a = -a;
			b = -b;
		}
	}
	real operator*(const real &o) const {
		return real(a * o.a, b * o.b);
	}
	real operator/(const real &o) const {
		return real(a * o.b, b * o.a);
	}
	real operator+(const real &o) const {
		return real(a * o.b + o.a * b, b * o.b);
	}
	real operator-(const real &o) const {
		return real(a * o.b - o.a * b, b * o.b);
	}
	bool operator<(const real &o) const {
		return a * o.b < o.a * b;
	}
};

struct expr {
	real v;
	string e;
	expr(const real &v, const string &e) : v(v), e(e) {}
	bool operator<(const struct expr &o) const { return v < o.v; }
};

void recurse(set<expr> *, unsigned);

int main()
{
	const unsigned m = 9;

	set<expr> s[m + 1];

	s[1].insert(expr(real(9, 1), "9"));
	s[1].insert(expr(real(-9, 1), "-9"));

	recurse(s, m);

	long long l = 0;
	for (set<expr>::const_iterator i = s[m].begin(); i != s[m].end(); ++i) {
		if (i->v.a > 0 && (i->v.a % i->v.b) == 0) {
			if (l && i->v.a / i->v.b != l + 1)
				break;
			l = i->v.a / i->v.b;
			cout << i->v.a / i->v.b << " == " << i->e << endl;
		}
	}
	return 0;
}

void recurse(set<expr> *s, unsigned n)
{
	for (unsigned i = 1; i < n; ++i) {
		unsigned j = n - i;

		if (s[i].empty())
			recurse(s, i);
		if (s[j].empty())
			recurse(s, j);

		for (set<expr>::const_iterator a = s[i].begin();
		    a != s[i].end(); ++a)
			for (set<expr>::const_iterator b = s[j].begin();
			    b != s[j].end(); ++b) {

				s[n].insert(expr(a->v + b->v,
				    "(" + a->e + ")+(" + b->e + ")"));

				s[n].insert(expr(a->v - b->v,
				    "(" + a->e + ")-(" + b->e + ")"));

				s[n].insert(expr(a->v * b->v,
				    "(" + a->e + ")*(" + b->e + ")"));

				if (b->v.a != 0)
					s[n].insert(expr(a->v / b->v,
					    "(" + a->e + ")/(" + b->e + ")"));

			}
	}
}