ZOJ 8th Anniversary Contest解题报告 » ZOJ3312

ZOJ3312
ZOJ3312.txt


#include <map>
#include <string>
#include <utility>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

struct Fraction {
	int num, den;

	Fraction(int n = 0, int d = 1) {
		int g = gcd(n, d);
		n /= g;
		d /= g;
		if (d < 0) {
			n = -n;
			d = -d;
		}
		num = n;
		den = d;
	}
};

Fraction operator+(const Fraction& lhs, const Fraction& rhs) {
	return Fraction(lhs.num * rhs.den + lhs.den * rhs.num, lhs.den * rhs.den);
}

Fraction operator-(const Fraction& lhs, const Fraction& rhs) {
	return Fraction(lhs.num * rhs.den - lhs.den * rhs.num, lhs.den * rhs.den);
}

Fraction operator*(const Fraction& lhs, const Fraction& rhs) {
	return Fraction(lhs.num * rhs.num, lhs.den * rhs.den);
}

Fraction operator/(const Fraction& lhs, const Fraction& rhs) {
	return Fraction(lhs.num * rhs.den, lhs.den * rhs.num);
}

bool operator<(const Fraction& lhs, const Fraction& rhs) {
	return lhs.num == rhs.num ? lhs.den < rhs.den : lhs.num < rhs.num;
}

map<Fraction, string> mp[9];

#define GAO(op) \
	t = x->first op y->first;\
	if (mp[i].count(t) == 0) {\
		mp[i][t] = "(" + x->second + #op + y->second + ")";\
	}

int main() {
	Fraction t;
	string s = "";
	int f = 0;

	for (int i = 1; i <= 8; ++i) {
		f = f * 10 + 8;
		s += '8';
		mp[i][f] = s;
		for (int j = 1; j < i; ++j) {
			int k = i - j;
			for (map<Fraction, string>::const_iterator x = mp[j].begin(); x != mp[j].end(); ++x) {
				for (map<Fraction, string>::const_iterator y = mp[k].begin(); y != mp[k].end(); ++y) {
					if (j <= k) {
						GAO(+)
						GAO(*)
					}
					if (y->first.num != 0) {
						GAO(/)
					}
					GAO(-)
				}
			}
		}
	}

	while (scanf("%d", &f) != EOF) {
		t = Fraction(f);
		if (mp[8].count(t) == 0) {
			puts("Impossible");
		} else {
			s = mp[8][t];
			if (s[0] == '(') {
				s = s.substr(1, s.length() - 2);
			}
			puts(s.c_str());
		}
	}

	return 0;
}

/*
Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
3395 	2010-03-14 14:38:39 	Accepted 	H 	C++ 	290 	6380 	watashi@Zodiac
*/
Leave a Reply