#include using namespace std; // The main idea for the solution works in two stages: // - first: we construct a 1:1 splitter from the c:d splitter as follows // // | // /----|----\ // / / \ \ // c c d d // | / \ | // \-/| |\-/ // d c // | | // // To see that this acts as a 1:1 splitter, consider just the // output of the second layer. It produces for outputs with ratios // c^2:c*d:d*c:d^2. The middle two are equal, and if we lead the // the outer two back to the root, effectively all input is thus split // in half. // // - next: We construct the desired ratio by building a binary tree (using // the above 1:1 splitter) that sends: // a/2^n to output A // b/2^n to output B // (2^n-a-b)/2^n back to the root. // this is done by repeatedly splitting the unused leaves in half, // sending output to A, B or the root in each layer to the maximum // extent possible. Again, this works because the output is forced to // have the right ratio, and anything that doesn't is simply // reprocessed. int main() { long long a, b, c, d; cin >> c >> d >> a >> b; long long denom = a+b; long long pow2 = 1; while (pow2 < denom) pow2 *= 2; long long feedback = pow2-denom; vector> splitters; queue endpoints; // Setup initial 50-50 split splitters.push_back({1,2}); splitters.push_back({0,-5}); splitters.push_back({-5,0}); endpoints.push(2*1+1); endpoints.push(2*2); long long cur = pow2/2; while (a != 0 || b != 0 || feedback != 0) { queue nextendpoints; while (a >= cur) { a -= cur; int ep = endpoints.front(); endpoints.pop(); // Patch output of selected endpoint to -1 int idx = ep/2; if (ep % 2 == 1) splitters[idx].second = -1; else splitters[idx].first = -1; } while (b >= cur) { b -= cur; int ep = endpoints.front(); endpoints.pop(); // Patch output of selected endpoint to -2 int idx = ep/2; if (ep % 2 == 1) splitters[idx].second = -2; else splitters[idx].first = -2; } while (feedback >= cur) { feedback -= cur; int ep = endpoints.front(); endpoints.pop(); // Patch output of selected endpoint to 0 int idx = ep/2; if (ep % 2 == 1) splitters[idx].second = 0; else splitters[idx].first = 0; } // Further split remaining endpoints (there will be at most 2!) while (!endpoints.empty()) { int ep = endpoints.front(); endpoints.pop(); int nidx = splitters.size(); // Patch output of selected endpoint to nidx int idx = ep/2; if (ep % 2 == 1) splitters[idx].second = nidx; else splitters[idx].first = nidx; // Create new 50-50 splitter splitters.push_back({nidx+1,nidx+2}); splitters.push_back({nidx, -5}); splitters.push_back({-5, nidx}); nextendpoints.push(2*(nidx+1)+1); nextendpoints.push(2*(nidx+2)); } // Do bookkeeping endpoints.swap(nextendpoints); cur /= 2; } // Output all splitters cout << splitters.size() << endl; for (auto s : splitters) { cout << s.first << " " << s.second << endl; } }