UVA 12558: Egyptian Fractions

12558.cpp

#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
#define fori(i,s,e) for(int i = s; i < ((int)e); i++)

long long gcd(long long x, long long y) {
	return y == 0 ? x : gcd(y, x % y);
}

const int MAX_BANNED = 1008;
bool banned[MAX_BANNED];
bool isBanned(long long x) {
	return x < MAX_BANNED && banned[x];
}

typedef struct Frac {
	long long num;
	long long denom;
	Frac(long long n0, long long d0) {
		long long g = gcd(n0, d0);
		num = n0/g;
		denom = d0/g;
	}
	Frac operator-(const Frac & other) const {
		return Frac(num * other.denom - other.num * denom, denom * other.denom);
	}
	bool operator<(const Frac & other) const {
		return num * other.denom < other.num * denom;
	}
} Frac;

bool better(const vector<long long> & a, const vector<long long> & b) {
	if (b.empty()) return true;
	assert(a.size() == b.size());
	assert(a.size() > 0);
	for (size_t i = a.size(); i-- > 0; ) {
		if (a[i] != b[i]) return a[i] < b[i];
	}
	return false;
}

vector<long long> reciprocals;
vector<long long> best;

bool dfs(int depth, Frac remainder, long long lastReciprocal) {
	if (depth == 1) {
		if (remainder.num == 1 && remainder.denom > lastReciprocal && !isBanned(remainder.denom)) {
			// cerr << "[debug] found with last 1/" << remainder.denom << "\n";
			reciprocals.push_back(remainder.denom);
			if (better(reciprocals, best)) {
				best = reciprocals;
			}
			reciprocals.pop_back();
			return true;
		}
		return false;
	}

	// smallest r s.t. 1/r < n/d -> r > d/n
	long long r = max((remainder.denom / remainder.num) + 1, lastReciprocal + 1);
	while (isBanned(r)) r++;

	bool success = false;

	while (true) {
		// when do we know if all larger r are impossible?
		if (Frac(depth, r) < remainder) break;
		if (!best.empty() && r >= best.back()) break;
		reciprocals.push_back(r);
		if (dfs(depth - 1, remainder - Frac(1, r), r)) {
			success = true;
		}
		reciprocals.pop_back();
		r++;
		while (isBanned(r)) r++;
	}

	return success;
}

void doTestCase(int tcn) {
	int n0, d0, nBanned;
	cin >> n0 >> d0 >> nBanned;

	fori (i, 0, MAX_BANNED) banned[i] = false;
	fori (i, 0, nBanned) {
		int ban;
		cin >> ban;
		banned[ban] = true;
	}

	reciprocals.clear();
	best.clear();
	int depth = 1;
	while (!dfs(depth, Frac(n0, d0), 1)) {
		depth++;
	}

	cout << "Case " << tcn << ": " << n0 << "/" << d0 << "=";
	bool started = false;
	for (const long long & denom : best) {
		if (started) cout << '+';
		started = true;
		cout << "1/" << denom;
	}
	cout << "\n";
}

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) doTestCase(i);
}