#include #include #include #include long long gcd(long long a, long long b){ return b==0 ? a : gcd(b, a%b); } struct Fraction { long long a,b; Fraction(long long a_, long long b_=1) : a(a_), b(b_) { auto g = gcd(a, b); a/=g, b/=g; if(b < 0) a = -a, b = -b; } }; Fraction operator+(const Fraction& l, const Fraction& r){ return {l.a*r.b + l.b*r.a, l.b*r.b}; } Fraction operator-(const Fraction& l, const Fraction& r){ return {l.a*r.b - l.b*r.a, l.b*r.b}; } Fraction operator*(const Fraction& l, const Fraction& r){ return {l.a*r.a, l.b*r.b}; } Fraction operator/(const Fraction& l, const Fraction& r){ return {l.a*r.b, l.b*r.a}; } bool operator<(const Fraction& l, const Fraction& r){ return l.a*r.b < l.b*r.a; } std::ostream& operator<<(std::ostream& o, const Fraction& f) { return o << f.a << " / " << f.b; } void solve(Fraction split, Fraction goal, int steps=0){ if(steps > 50){ //std::cerr << "stop\n"; return; } //std::cerr << "Solve " << goal << std::endl; if(!(split < goal) && !(goal < split)){ //std::cerr << "Goal == Split = " << goal << " done!" << std::endl; std::cout << "done!\n"; return; } bool has_best = false; Fraction best{0,0}; std::string msg; if(1-split < goal){ auto n = (goal-(1-split))/split; //std::cerr << n << std::endl; if(!has_best) has_best = true, best = n, msg = "Take inverse of"; } else { auto n = goal/(1-split); //std::cerr << n << std::endl; if(!has_best) has_best = true, best = n, msg = "Drop"; } if(split < goal){ auto n = (goal-split)/(1-split); //std::cerr << n << std::endl; if(!has_best || n.b < best.b) has_best = true, best = n, msg = "Take"; } else { auto n = goal/split; //std::cerr << n << std::endl; if(!has_best || n.b < best.b) has_best = true, best = n, msg = "Drop inverse of"; } if(!has_best){ assert(false); } //std::cerr << msg << " " << split << std::endl; solve(split, best, ++steps); } int main(){ long long a,b,c,d; std::cin >> a >> b >> c >> d; solve({a,b}, {c, d}); }