#include <vector>
#include <iostream>
#include <set>
#include <cassert>
#include <iterator>
#include <limits>
#include <cmath>
#include <string>
#include <functional>
#include <map>
#include <strstream>
#include <fstream>

using namespace std;

////////////////////////////////////////////////////////////////////
// Basic Functions

bool IsInt(double x){return (double(long(x)) - x) == 0;}; 

double Sqrt(const double x){return sqrt(x);}
double Percent(const double x){return x / 100.0;};
double Negate(const double x){return -x;};
double Fact(const double x)
{
	bool bad = false;
	
	//if x is less than 0, factorial does not exist
	if (x < 0) bad = true;

	//if x is not integer, factorial does not exist
	if (!IsInt(x)) bad = true;

	//if x is too big, you probably don't want to compute Fact(x) anyway
	if (x > 20) bad = true;

	//if bad, return a bad number
	if (bad) return numeric_limits<double>::infinity();

	double res = 1;
	for(int i=1; i<=x; i++)
	{
		res *= double(i);
	}
	return res;
}

double Add(const double x, const double y){return x + y;};
double Sub(const double x, const double y){return x - y;};
double Mul(const double x, const double y){return x * y;};
double Div(const double x, const double y){return x / y;};
double Pow(const double x, const double y)
{
	if (x == 0 || y == 0) return pow(x, y);
	else
	{
		double p1 = pow(x, y);
		double p2 = pow(x, y - 1.0);

		//if this equals, a overflow occur or precision has lost
		//	either way, we don't want this result anymore
		//NOTE: this method doesn't catch all the overflow
		if (p1 == p2) return numeric_limits<double>::infinity(); 
		return p1;
	}
}

////////////////////////////////////////////////////////////////////
// Typedef

typedef double (Unary) (const double);
typedef double (Binary) (const double, const double);

typedef vector<Unary*> vUnary;
typedef vector<Binary*> vBinary;

typedef pair<Unary*, string> cUS;
typedef vector<cUS> vUS;

typedef pair<Binary*, string> cBS;
typedef vector<cBS> vBS;

////////////////////////////////////////////////////////////////////
// Initialization of all acceptable functions and their equivalent output

vUS InitUnary(vector<string> input = vector<string>())
{
	vUS all;

	all.push_back(cUS(&Fact, "fact"));
	all.push_back(cUS(&Sqrt, "sqrt"));
	all.push_back(cUS(&Percent, "percent"));
	all.push_back(cUS(&Negate, "neg"));

	vUS res;

	if (input.size() == 0)
	{
		res = all;
	}
	else
	{
		for(int a=0; a<all.size(); a++)
		{
			for(int i=0; i<input.size(); i++)
			{
				if (all[a].second == input[i])
				{
					res.push_back(all[a]);
					break;
				}
			}
		}
	}

	return res;
}

vBS InitBinary(vector<string> input = vector<string>())
{
	vBS all;

	//those with higher precedent goes first
	all.push_back(cBS(&Pow, "^"));
	all.push_back(cBS(&Mul, "*"));
	all.push_back(cBS(&Div, "/"));
	all.push_back(cBS(&Add, "+")); //put + before - to prefer + over -
	all.push_back(cBS(&Sub, "-"));

	vBS res;

	if (input.size() == 0)
	{
		res = all;
	}
	else
	{
		for(int a=0; a<all.size(); a++)
		{
			for(int i=0; i<input.size(); i++)
			{
				if (all[a].second == input[i])
				{
					res.push_back(all[a]);
					break;
				}
			}
		}
	}

	return res;
}

////////////////////////////////////////////////////////////////////
// Acylic expression tree

//this number is used to choose the tie off for the different equation. 
//  note that all the priority should be much smaller than this number
const double PRIORITY_DIV = 10000.0;

//This is used to create an acylic tree (but NOT standard binary tree since a node can have multiple parents) to represent the resulting equation
struct cNode
{
	//prior is completely optional for this function, it's only used to break tie
	//	when equal number of operations are used, cNumber has a tendency to use those with lower priority (NOTE: not always)
	
	//make number preferable, so set prior to very small
	cNode(double num, int prior = -1000)
	{
		strstream temp;
		if (IsInt(num))	temp << long(num);
		else temp << num;
		temp >> entry;

		left = NULL;
		right = NULL;
		priority = prior;
	};

	//pass in string as num, used for repeating fraction
	cNode(string num, int prior = 1)
	{
		entry = num;
		left = NULL;
		right = NULL;
		priority = prior;
	}

	cNode(string unary_op, cNode* child)
	{
		//make this number smaller than all binary op, so it would choose a more reasonable result
		//	so no bracket will ever be placed around unary_op
		priority = 3;
		entry = unary_op;
		left = NULL;
		right = child;
	};


	//the prior here will always be a positive number
	cNode(string binary_op, cNode* left_child, cNode* right_child, int prior)
	{
		priority = prior+5;
		entry = binary_op;
		left = left_child;
		right = right_child;
	};

	//this is here but not implemented because it's unclear exactly what equal should mean
	//	if this data structure is a tree, I could just copy it, but since a children often
	//	have multiple parents, it does not makes too much sense to copy.
	operator=(cNode node);

	//if you want to add any other properties here, change UpdateEqu too
	string entry;
	int priority;

	cNode* left;
	cNode* right; //unary always store on left
};


string Traverse(const cNode* node)
{
	string res;
	bool bUnary = (node->left == NULL && node->right != NULL);
	bool bBinary = (node->left != NULL && node->right != NULL);
	bool bEle = (node->left == NULL && node->right == NULL);

	//output left branch
	if (bBinary && node->left->priority > node->priority) res += "(";
	if (node->left != NULL)
	{
		res += Traverse(node->left);
	}
	if (bBinary && node->left->priority > node->priority) res += ")";

	//output the middle entry
	if (bUnary)	res += node->entry;
	if (bBinary) res += " " + node->entry + " ";
	if (bEle) res += node->entry;

	//output right branch, note that in bBinary, bracket is determine by >=, while above only needs >
	if (bUnary) res += "(";
	if (bBinary && node->right->priority >= node->priority) res += "(";
	if (node->right != NULL)
	{
		res += Traverse(node->right);
	}
	if (bBinary && node->right->priority >= node->priority) res += ")";
	if (bUnary) res += ")";

	return res;
}

//Pre Order
string PreTraverse(const cNode* node)
{
	string res;
	res += " ";
	res += node->entry;

	if (node->left != NULL)
	{
		res += PreTraverse(node->left);
	}

	if (node->right != NULL)
	{
		res += PreTraverse(node->right);
	}

	return res;
}

////////////////////////////////////////////////////////////////////
// This class takes care of all the numbers and buliding trees

class cNumber
{
public:

	//initiation
	cNumber(int digit, int numdigit, vUS unary, vBS binary);

	//computation
	void Compute(const int k); //compute up to k digits

	//check if a number is in level k, if not output an error
	bool Exist(double num, int k, bool warn = true);

	//output
	bool OutputPosInt(int k);
	bool Output(int k);
	bool OutputEqu(double num, int k);
	string GetEqu(double num, int k);
	void SetRepeat(bool repeat){bRepeat = repeat;};

private:
	
	int nDigit;
	int nNumDigit;
	int nSofar; //how many level of computation has been performed

	//vector of unary and binary function
	vUnary fUnary;
	vBinary fBinary;
	vector<string> sUnary;
	vector<string> sBinary;

	//set if repeating fraction is allowed
	bool bRepeat;

	//Possible[k] store all the possible number that can be formed with k of the digit
	vector<set<double, greater<double> > > Possible; //greater so bigger number are select first in apply binary

	//Equation[k] stores the tree for each result in Possible[k]
	//Note, Equation contains more numbers than possible
	vector<map<double, cNode*> > Equation;
	void UpdateEqu(double& num, cNode* equ, int k);

	void RecurseUnary(double value, int k);
	void ApplyElement(int k);
	void ApplyBinary(int k);

	bool Add(double newValue, int k);
};

cNumber::cNumber(int digit, int numdigit, vUS unary, vBS binary)
{
	nDigit = digit;
	nNumDigit = numdigit;
	nSofar = 0;

	for(int u=0; u<unary.size(); u++)
	{
		fUnary.push_back(unary[u].first);
		sUnary.push_back(unary[u].second);
	}

	for(int b=0; b<binary.size(); b++)
	{
		fBinary.push_back(binary[b].first);
		sBinary.push_back(binary[b].second);
	}

	Possible.resize(numdigit+1);
	Equation.resize(numdigit+1);

	bRepeat = true;

};

string cNumber::GetEqu(double num, int k)
{
	string res;

	if (Equation[k].find(num) == Equation[k].end())
	{
		res = " Not Found\n";
		return res;
	}

	//infix notation
	res += " " + Traverse(Equation[k][num]);
	//preorder notation, if you want my code to also display with preorder notation, uncomment below line
	//res += " =" + PreTraverse(Equation[k][num]);
	res += "\n";
	return res;
}

bool cNumber::Exist(double num, int k, bool warn)
{
	bool exist = true;
	if (k < 0) exist = false;
	else
	{
		if (Possible[k].find(num) == Possible[k].end())
		{
			exist = false;
		}
	}
	
	if (!exist && warn)
	{
		cout << "Info: " << num << " does not exist in " << k << " iteration." << endl;
	}

	return exist;
}

bool cNumber::Add(double newValue, int k)
{
	//bad number
	if (newValue == numeric_limits<double>::infinity()) return false;
	
	//already exist, although set automatically check repeat, I need to check because I need it to return false
	if (Possible[k].find(newValue) != Possible[k].end()) return false;

	//if it's too big, it lose accuracy and is no longer important
	if (fabs(newValue) > 1e30) return false;

	//if this is the last iteration
	//Note: this assume that unary_op will not be able to change a fraction into integer
	if (k == nNumDigit)
	{
		if (!IsInt(newValue)) return false;
		if (newValue < 0) return false;
	}

	//if not an integer, do additional check to see if I want to keep the value
	if (!IsInt(newValue))
	{
		//check if it can be represented as something / xxx

		//if too close to an int, 
		double up = ceil(newValue);
		double down = floor(newValue);
		const double fCUTOFF = 0.001;

		if (fabs(newValue - up) < fCUTOFF) return false;
		if (fabs(newValue - down) < fCUTOFF) return false;

		const int nLOW = int (1.0 / fCUTOFF);
		bool bad = true;
		for(int n=2; n<=nLOW; n++)
		{
			if (IsInt(newValue * double(n)))
			{
				bad = false;
				break;
			}
		}

		if (bad) return false;
	}

	//pass all checks, add
	Possible[k].insert(newValue);
	if (Equation[k].find(newValue) == Equation[k].end())
	{
		cout << "Warning: Equ for " << newValue << " not found!" << endl;
		cout << "Please report this to chengwen@uclink.berkeley.edu." << endl;
		UpdateEqu(newValue, new cNode(newValue), k);
	}
	

	//apply as many unary op as possible to this newValue
	RecurseUnary(newValue, k);

	return true;
};

double NumNode(cNode * node)
{
	if (node == NULL)
	{
		return 0;
	}

	int nNode = 1 + NumNode(node->left) + NumNode(node->right);

	//add the priority for tie-off, i.e, it would prefer those with lower priority
	return  double(nNode) + node->priority / PRIORITY_DIV;
}

//check if number needs to be adjusted to minimize round off error
bool Fix(double& num)
{
	const bool good = (28.4 + 4.4) / 0.4 == 71;

	//no need to run this fix
	if (good) return true;
	else
	{
		const double TOLERANCE = 0.0000000001;
		if (fabs(ceil(num) - num) < TOLERANCE && (ceil(num) != 0)) num = ceil(num);
		if (fabs(floor(num) - num) < TOLERANCE && (floor(num) != 0)) num = floor(num);
	}

	return false;
}

//NOTE: num is passed by ref for fixing round off error
void cNumber::UpdateEqu(double& num, cNode * equ, int k)
{
	Fix(num);

	if (num == numeric_limits<double>::infinity())
	{
		delete equ;
		return;
	}

	//if num is already in the list
	if (Equation[k].find(num) != Equation[k].end())
	{
		//TODO: this is a extremely slow way to break up tie
		double nNew = NumNode(equ);
		double nOld = NumNode(Equation[k][num]);

		//if the new one has fewer node, or lower precedent
		//if (nNew < nOld || (nNew == nOld && equ->priority > Equation[k][num]->priority))
		if (nNew < nOld) //just different ways to break tie
		{
			cNode* node = Equation[k][num];
			node->entry = equ->entry;
			node->left = equ->left;
			node->right = equ->right;
			node->priority = equ->priority;
		}

		delete equ;
		return;
	}

	Equation[k][num] = equ;
}
	
void cNumber::ApplyElement(int k)
{
	//I can't make anything out of nothing
	if (k == 0) return;

	//k = 1 -> first = 4; 2 -> 44; 3->444, etc
	double first = 0;
	for(int f=0; f<k; f++)
	{
		first *= 10;
		first += nDigit;
	}
	
	UpdateEqu(first, new cNode(first), k);
	Add(first, k);

	//add a decimal point at any place
	double dec = first;
	for(;;)
	{
		if (dec < 1) break;
		
		dec /= 10.0;

		UpdateEqu(dec, new cNode(dec), k);
		Add(dec, k);
	}

	if (bRepeat)
	{
		//add the repeating dec symbol
		//Note: if I want to allow for various digit set, I need to change here
		double rdec = first / (pow(10.0, k) - 1.0);

		//get the repeating fraction notation
		strstream temp;
		string num;
		temp << ".(" << long(first) << ")'";
		temp >> num;

		//update it
		UpdateEqu(rdec, new cNode(num), k);
		Add(rdec, k);
	}
}

void cNumber::RecurseUnary(double value, int k)
{
	for(int u=0; u<fUnary.size(); u++)
	{
		//compute the new value
		double newValue = fUnary[u](value);

		//Try to add the value
		UpdateEqu(newValue, new cNode(sUnary[u], Equation[k][value]), k);
		//Note that this is recursive, since Add call RecurseUnary
		Add(newValue, k);
	}
}

void cNumber::ApplyBinary(int k)
{
	//Try all possible combinations
	//Loop invariant, a+b = k
	for(int a=0; a<=k; a++)
	{
		int b = k - a;
		
		//Use Binary Op on everything in set[a] and set[b] then add the result to set[k]
		set<double, greater<double> >::iterator iterA;
		set<double, greater<double> >::iterator iterB;

		for(iterA = Possible[a].begin(); iterA != Possible[a].end(); iterA++)
		{
			for(iterB = Possible[b].begin(); iterB != Possible[b].end(); iterB++)
			{
				for(int bin=0; bin < fBinary.size(); bin++)
				{
					double newValue = fBinary[bin](*iterA, *iterB);

					UpdateEqu(newValue, new cNode(sBinary[bin], Equation[a][*iterA], Equation[b][*iterB], bin), k);
					Add(newValue, k);
				}
			}
		}
	}
}

void cNumber::Compute(const int k)
{
	//if already computed, then stop
	if (nSofar >= k) return;

	//if tha not been computed, then compute the previous level before this one
	if (nSofar < k) Compute(k-1);

	//create the first few number
	ApplyElement(k);

	//use the previous result to get binary
	ApplyBinary(k);

	//set the sofar to current level
	nSofar = k;

	return;
}

int main(int argc, char* argv[])
{
	/* Testing
	cNode* left = new cNode(3);
	cNode* right1 = new cNode(33);
	cNode* right2 = new cNode(".(3)'");
	cNode* right = new cNode("-", right1, right2, 3);
	cNode* all = new cNode("*", left, right, 2);

	cout << Traverse(all) << endl;
	return 0;
	*/

	//get the name of this command
	string command = string(argv[0]);

	int nDigit = 4;
	int nNumber = 4;

	int MaxN = 100;

	bool badinput = false;

	//check if it's valid input
	if (argc == 1)
	{
		cout << "No argument -- Default Setting Used." << endl;
	}
	else if (argc <= 3)
	{
		badinput = true;
	}
	else //argc >= 4
	{
		strstream temp;
		temp << string(argv[1]) << endl;
		temp << string(argv[2]) << endl;
		temp << string(argv[3]) << endl;

		temp >> nDigit;
		temp >> nNumber;
		temp >> MaxN;

		if (nDigit < 0 || nDigit > 9) badinput = true;

		if (temp.eof()) badinput = true;
	}
	
	if (badinput)
	{
		cout << "Invalid Command Line Options" << endl << endl;
		cout << "The program tries to equations using 'nNumber' 'nDigit's to obtain answers 1 to 'MaxN' with specified operation" << endl;
		cout << "four4 [nDigit nNumber MaxN [+] [-] [*] [/] [^] [sqrt] [percent] [fact] [neg] [repeat]]" << endl;
		cout << "0 <= nDigit <= 9" << endl;
		cout << endl;
		cout << "Example: " << endl;
		cout << "  " << command << endl;
		cout << "  " << command << " 4 4 100 (using four 4's to make 1 to 100) " << endl;
		cout << "  " << command << " 2 2 10  (using two 2's to make 1 to 10)" << endl;
		cout << "  " << command << " 3 4 100 (using four 3's to make 1 to 100)" << endl;
		cout << "  " << command << " 4 4 100 + - * / (using four 4's to make 1 to 100, allow only + - * / as operation)" << endl;
		return 0;
	}


	//read in the input
	vector<string> input;

	for(int i=4; i<argc; i++)
	{
		string temp = string(argv[i]);
		input.push_back(temp);
	}

	const int MaxK = nNumber;

	//process it
	cNumber number(nDigit, nNumber, InitUnary(input), InitBinary(input));

	//check for the special items, such as repeat, combine
	bool bRepeat = false;

	//by default, repeat is true
	if (input.size() == 0) bRepeat = true;

	//handle special input, such as bRepeat
	int nMisc = 0;
	for(i=0; i<input.size(); i++)
	{
		if (input[i] == "repeat")
		{
			bRepeat = true;
			nMisc++;
		}
	}

	//set the repeat according to input
	number.SetRepeat(bRepeat);
	
	//check if all the input operation are valid
	if (input.size() != 0 && InitUnary(input).size() + InitBinary(input).size() + nMisc != input.size())
	{
		cout << "Invalid Command Line Options -- Unrecognizable operations" << endl << endl;
		cout << "four4 [nDigit nNumber MaxN [+] [-] [*] [/] [^] [sqrt] [percent] [fact] [neg] [repeat]]" << endl;
		cout << endl;
		cout << "Example: " << endl;
		cout << "  " << command << endl;
		cout << "  " << command << " 4 4 100 (using four 4's to make 1 to 100) " << endl;
		cout << "  " << command << " 2 2 10  (using two 2's to make 1 to 10)" << endl;
		cout << "  " << command << " 3 4 100 (using four 3's to make 1 to 100)" << endl;
		cout << "  " << command << " 4 4 100 + - * / (using four 4's to make 1 to 100, allow only + - * / as operation)" << endl;
		return 0;
	}

	//output the input read by the program for confirmation
	ofstream oRes("puzzle.txt", ios::app);
	oRes << "-------------------------------------" << endl;
	
	oRes << "Input:\n  Digit = " << nDigit << "; nNumber = " << nNumber << "; MaxN = " << MaxN << endl;
	cout << "Input:\n  Digit = " << nDigit << "; nNumber = " << nNumber << "; MaxN = " << MaxN << endl;

	oRes << "  Operation: ";
	cout << "  Operation: ";
	
	if (input.size() != 0)
	{
		for(int s=0; s<input.size(); s++)
		{
			oRes << input[s] << ' ';
			cout << input[s] << ' ';
		}
/*		
		if (bRepeat)
		{
			oRes << "repeat";
			cout << "repeat";
		}
*/
		oRes << endl << endl;
		cout << endl << endl;
	}
	else
	{
		oRes << "+ - * / ^ fact percent sqrt neg repeat" << endl << endl;
		cout << "+ - * / ^ fact percent sqrt neg repeat" << endl << endl;
	}

	//output the result, iteration by iteration
	for(int k=1; k<=MaxK; k++)
	{
		cout << "Compute with only " << k << " out of " << MaxK << flush;
		oRes << "Compute with only " << k << " out of " << MaxK << flush;
		number.Compute(k);
		cout << "....Done!" << endl;
		oRes << "....Done!" << endl;

		for(int c=1; c<=MaxN; c++)
		{
			cout << "  " << c << " =";
			cout << number.GetEqu(double(c), k);

			oRes << "  " << c << " =";
			oRes << number.GetEqu(double(c), k);
		}

		cout << endl;
		oRes << endl;
	}

	oRes.close();

	return 1;
}

////////////////////////////////////////////////////////////////////
// Possible Improvements

//Implement additional function, such as gamma; decimal before any int .(4!) = .24; partial repeat fraction 9.(9)' = 10
//Let NumNode prefer those situation with fewer bracket, i.e. choose 4 * 4 * 4 over 4 * (4 * 4).  Note that order sometimes matter in binary function, such as power
//Add additional filters in Add to improve speed, or making add less likely to filter out good stuff.

////////////////////////////////////////////////////////////////////
// Known Bug

//puzzle 9 10 1 repeat, here is a section of output

/*
Compute with only 8 out of 15....Done!
  1 = .(99999999)'

Compute with only 9 out of 15....Done!
  1 = .(999999999)'

Compute with only 10 out of 15....Done!
  1 = 1
*/

//as you can see, in the case of 10, it should display .(999999999)', but it didn't
//	this is because of two reasons
//	first the fix round-off error, I consider 0.9999999999 = 1
//	second, I use long to store integer, thus, if the number exceed the range of long, bad things happen

//Add sometimes filter out good stuff, such as
//	sqrt(sqrt(sqrt(sqrt(4%)^(4!)))) = 1/125
//a solution is to keep all number as fraction, but I was afraid it would be too slow.
//	this will solve all the inprecision too, however, there is also a limit for long