Skip to content

Instantly share code, notes, and snippets.

@betaveros
Created July 8, 2020 05:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save betaveros/221db657e6b6e1e03015cfcbc2edf21c to your computer and use it in GitHub Desktop.
Save betaveros/221db657e6b6e1e03015cfcbc2edf21c to your computer and use it in GitHub Desktop.
UVA 12558: Egyptian Fractions
#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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment