#include using namespace std; struct Item { string name; long long q, v, m, l; }; struct Solution { vector x; long long value = 0; long long mass = 0; long long vol = 0; }; static const long long M_CAP = 20LL * 1000000LL; // 20 kg in mg static const long long L_CAP = 25LL * 1000000LL; // 25 L in µL struct Parser { string s; size_t i = 0; Parser(const string& str): s(str), i(0) {} void skipWS() { while (i < s.size() && isspace((unsigned char)s[i])) i++; } bool match(char c) { skipWS(); if (i < s.size() && s[i] == c) { i++; return true; } return false; } void expect(char c) { skipWS(); if (i >= s.size() || s[i] != c) { // invalid JSON for our purposes; just proceed } else { i++; } } string parseString() { skipWS(); string res; if (i < s.size() && s[i] == '"') { i++; while (i < s.size()) { char c = s[i++]; if (c == '"') break; if (c == '\\') { if (i < s.size()) { char esc = s[i++]; // For simplicity, handle only common escapes if (esc == '"' || esc == '\\' || esc == '/') res.push_back(esc); else if (esc == 'b') res.push_back('\b'); else if (esc == 'f') res.push_back('\f'); else if (esc == 'n') res.push_back('\n'); else if (esc == 'r') res.push_back('\r'); else if (esc == 't') res.push_back('\t'); else res.push_back(esc); } } else { res.push_back(c); } } } return res; } long long parseNumber() { skipWS(); long long sign = 1; if (i < s.size() && (s[i] == '+' || s[i] == '-')) { if (s[i] == '-') sign = -1; i++; } long long num = 0; while (i < s.size() && isdigit((unsigned char)s[i])) { num = num * 10 + (s[i] - '0'); i++; } return sign * num; } vector parseArrayNumbers() { vector arr; expect('['); while (true) { skipWS(); if (i < s.size() && s[i] == ']') { i++; break; } long long num = parseNumber(); arr.push_back(num); skipWS(); if (i < s.size() && s[i] == ',') { i++; continue; } else if (i < s.size() && s[i] == ']') { i++; break; } else { // malformed, break break; } } return arr; } vector parseObject() { vector items; expect('{'); while (true) { skipWS(); if (i < s.size() && s[i] == '}') { i++; break; } string key = parseString(); skipWS(); expect(':'); vector arr = parseArrayNumbers(); Item it; it.name = key; if (arr.size() >= 4) { it.q = arr[0]; it.v = arr[1]; it.m = arr[2]; it.l = arr[3]; } else { it.q = it.v = it.m = it.l = 0; } items.push_back(it); skipWS(); if (i < s.size() && s[i] == ',') { i++; continue; } else if (i < s.size() && s[i] == '}') { i++; break; } else { // End or malformed; break break; } } return items; } }; struct OrderDesc { int kind; // 0 = weighted sum, 1 = max norm, 2 = euclidean double alpha; // for kind 0 }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // Read entire stdin string input((istreambuf_iterator(cin)), istreambuf_iterator()); Parser parser(input); vector items = parser.parseObject(); int n = (int)items.size(); if (n == 0) { cout << "{\n}\n"; return 0; } // Limits const long long M = M_CAP; const long long L = L_CAP; vector q(n), v(n), m(n), l(n); vector names(n); for (int i = 0; i < n; ++i) { names[i] = items[i].name; q[i] = items[i].q; v[i] = items[i].v; m[i] = items[i].m; l[i] = items[i].l; } // Cap q by capacity constraints vector qCap(n); for (int i = 0; i < n; ++i) { long long byM = (m[i] > 0 ? M / m[i] : 0); long long byL = (l[i] > 0 ? L / l[i] : 0); long long cap = min(byM, byL); if (cap < 0) cap = 0; if (cap > q[i]) cap = q[i]; qCap[i] = cap; } // Precompute normalized weights vector mN(n), lN(n); for (int i = 0; i < n; ++i) { mN[i] = (double)m[i] / (double)M; lN[i] = (double)l[i] / (double)L; } auto build_order = [&](const OrderDesc& od)->vector { vector idx(n); iota(idx.begin(), idx.end(), 0); vector ratio(n, 0.0); for (int i = 0; i < n; ++i) { double cw = 0.0; if (od.kind == 0) { cw = od.alpha * mN[i] + (1.0 - od.alpha) * lN[i]; } else if (od.kind == 1) { cw = max(mN[i], lN[i]); } else { double a = mN[i], b = lN[i]; cw = sqrt(a*a + b*b); } if (cw <= 0.0) cw = 1e-18; ratio[i] = (double)v[i] / cw; } stable_sort(idx.begin(), idx.end(), [&](int a, int b) { if (ratio[a] != ratio[b]) return ratio[a] > ratio[b]; if (v[a] != v[b]) return v[a] > v[b]; // Tie-break by smaller combined weight utilization double wa = mN[a] + lN[a]; double wb = mN[b] + lN[b]; if (wa != wb) return wa < wb; return a < b; }); return idx; }; auto compute_value = [&](const vector& x)->long long { long long res = 0; for (int i = 0; i < n; ++i) res += x[i] * v[i]; return res; }; auto compute_mass = [&](const vector& x)->long long { long long res = 0; for (int i = 0; i < n; ++i) res += x[i] * m[i]; return res; }; auto compute_vol = [&](const vector& x)->long long { long long res = 0; for (int i = 0; i < n; ++i) res += x[i] * l[i]; return res; }; auto greedy_fill_order = [&](const vector& order, const vector& xStart)->Solution { Solution sol; sol.x = xStart; long long massUsed = 0, volUsed = 0; for (int i = 0; i < n; ++i) { if (sol.x[i] < 0) sol.x[i] = 0; if (sol.x[i] > qCap[i]) sol.x[i] = qCap[i]; massUsed += sol.x[i] * m[i]; volUsed += sol.x[i] * l[i]; } if (massUsed > M || volUsed > L) { // If invalid, clamp down everything (should not happen) sol.x.assign(n, 0); massUsed = volUsed = 0; } for (int idx : order) { if (qCap[idx] <= sol.x[idx]) continue; if (m[idx] == 0 || l[idx] == 0) continue; // should not happen if (massUsed >= M || volUsed >= L) break; long long mm = M - massUsed; long long vv = L - volUsed; long long t1 = mm / m[idx]; long long t2 = vv / l[idx]; long long t = min({t1, t2, qCap[idx] - sol.x[idx]}); if (t > 0) { sol.x[idx] += t; massUsed += t * m[idx]; volUsed += t * l[idx]; } } sol.mass = massUsed; sol.vol = volUsed; sol.value = compute_value(sol.x); return sol; }; // Build orders vector ordersDesc; // Weighted sums over a spread of alphas vector alphas = {0.0, 0.15, 0.25, 0.35, 0.5, 0.65, 0.75, 0.85, 1.0}; for (double a : alphas) ordersDesc.push_back({0, a}); // Additional norms ordersDesc.push_back({1, 0.0}); // max norm ordersDesc.push_back({2, 0.0}); // euclidean vector> orders; for (auto& od : ordersDesc) orders.push_back(build_order(od)); // Initial solutions vector candidates; vector zero(n, 0); for (auto &ord : orders) { Solution s = greedy_fill_order(ord, zero); candidates.push_back(s); } // Get the best candidate Solution best = candidates[0]; for (auto &s : candidates) { if (s.value > best.value) best = s; } // Local improvement by small removals and refill auto improve = [&](Solution sol)->Solution { // Use first-improvement hill climbing with small removals const int MAX_PASS = 3; for (int pass = 0; pass < MAX_PASS; ++pass) { bool improved = false; for (int i = 0; i < n && !improved; ++i) { if (sol.x[i] <= 0) continue; long long maxD = min(8LL, sol.x[i]); for (long long d = 1; d <= maxD && !improved; ++d) { vector x2 = sol.x; x2[i] -= d; long long mass2 = sol.mass - d * m[i]; long long vol2 = sol.vol - d * l[i]; if (mass2 < 0 || vol2 < 0) continue; // shouldn't happen // Try refilling using several orders for (auto &ord : orders) { Solution s3 = greedy_fill_order(ord, x2); if (s3.value > sol.value) { sol = s3; improved = true; break; } } } } if (!improved) break; } return sol; }; best = improve(best); // Output result JSON with same keys order cout << "{\n"; for (int i = 0; i < n; ++i) { long long chosen = 0; if (i < (int)best.x.size()) chosen = best.x[i]; if (chosen < 0) chosen = 0; if (chosen > q[i]) chosen = q[i]; cout << " \"" << names[i] << "\": " << chosen; if (i + 1 < n) cout << ",\n"; else cout << "\n"; } cout << "}\n"; return 0; }