Skip to content

Instantly share code, notes, and snippets.

@amsimoes

amsimoes/math.cpp

Created November 10, 2017 23:09
Show Gist options
  • Save amsimoes/1b1ee5be0c6fa32e73f166805b59c05c to your computer and use it in GitHub Desktop.
Save amsimoes/1b1ee5be0c6fa32e73f166805b59c05c to your computer and use it in GitHub Desktop.
Download ZIP
Solution for the Elementary Math Problem (E) of NWERC 2015
Raw
math.cpp
// solution using standard max-flow
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cfloat>
#include <climits>
#include <numeric>
#include <iomanip>
using namespace std;
const int oo = 0x3f3f3f3f;
const double eps = 1e-9;
const double PI = 2.0 * acos(0.0);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
#define sz(c) int((c).size())
#define all(c) (c).begin(), (c).end()
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define FORS(i,a,b,s) for (int i = (a); i < (b); i=i+(s))
#define FORD(i,a,b) for (int i = int(b)-1; i >= (a); i--)
#define FORIT(i,c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); i++)
struct edge {
int to, cap, flow, oi;
};
#define MAXN 12502
vector<edge> e[MAXN];
int aug[MAXN];
int pa[MAXN];
void addEdge(int u, int v, int capUV, int capVU) {
edge uv, vu;
uv.to = v;
uv.cap = capUV;
uv.flow = 0;
uv.oi = e[v].size();
vu.to = u;
vu.cap = capVU;
vu.flow = 0;
vu.oi = e[u].size();
e[u].push_back(uv);
e[v].push_back(vu);
}
bool findAugPathEK(int src, int sink, int n) {
static int qu[MAXN]; // pseudo-queue
FOR(i,0,n)
pa[i] = -1;
aug[src] = oo;
int start = 0, end = 0;
qu[end++] = src;
while (start != end) {
int u = qu[start++];
FOR(i,0,sz(e[u])) {
int v = e[u][i].to;
int curaug = e[u][i].cap - e[u][i].flow;
if (pa[v] == -1 && curaug > 0) {
qu[end++] = v;
aug[v] = min(aug[u], curaug);
pa[v] = e[u][i].oi;
if (v == sink)
return true;
}
}
}
return false;
}
int calcMaxFlow(int src, int sink, int n) {
int ret = 0;
FOR(i,0,n)
FOR(j,0,sz(e[i]))
e[i][j].flow = 0;
while (findAugPathEK(src, sink, n)) {
int v = sink;
while (v != src) {
e[e[v][pa[v]].to][e[v][pa[v]].oi].flow += aug[sink];
e[v][pa[v]].flow -= aug[sink];
v = e[v][pa[v]].to;
}
ret += aug[sink];
if (ret >= oo)
break;
}
return ret;
}
map<ll,int> rightT;
int getRight(ll i){
if (!rightT.count(i)) rightT[i] = sz(rightT)-1;
return rightT[i];
}
ll as[2500];
ll bs[2500];
int main(){
int n; cin >> n;
FOR(i,0,n){
cin >> as[i] >> bs[i];
addEdge(0,2+i,1,0);
addEdge(2+i,2+n+getRight(as[i]+bs[i]),1,0);
addEdge(2+i,2+n+getRight(as[i]-bs[i]),1,0);
addEdge(2+i,2+n+getRight(as[i]*bs[i]),1,0);
}
FORIT(i,rightT) addEdge(2+n+i->second,1,1,0);
int mf = calcMaxFlow(0,1,2+n+sz(rightT));
if (mf != n) cout << "impossible" << endl;
else
FOR(i,0,n) FOR(j,0,sz(e[i+2]))
if (e[i+2][j].flow) {
if (e[i+2][j].to == 2+n+getRight(as[i]+bs[i]))
cout << as[i] << '+' << bs[i] << '=' << as[i]+bs[i] << endl;
else if (e[i+2][j].to == 2+n+getRight(as[i]-bs[i]))
cout << as[i] << '-' << bs[i] << '=' << as[i]-bs[i] << endl;
else if (e[i+2][j].to == 2+n+getRight(as[i]*bs[i]))
cout << as[i] << '*' << bs[i] << '=' << as[i]*bs[i] << endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment