Cod sursa(job #3309113)

Utilizator raluca1977Raluca zanfir raluca1977 Data 1 septembrie 2025 13:09:00
Problema Lapte Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.36 kb
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;

const int MAXN = 105;
const double EPS = 1e-12;

int N, L;
int a[MAXN], b[MAXN];     // minute pe litru (A si B)
double ratio_[MAXN];      // b[i] / a[i]
int ord[MAXN];            // indici sortati dupa ratio

void sort_by_ratio() {    // selection sort simplu (fara STL)
    for (int i = 0; i < N; i++) ord[i] = i;
    for (int i = 0; i < N; i++) {
        int best = i;
        for (int j = i+1; j < N; j++)
            if (ratio_[ord[j]] < ratio_[ord[best]]) best = j;
        int t = ord[i]; ord[i] = ord[best]; ord[best] = t;
    }
}

// testam daca in T minute putem obtine ≥L litri A si ≥L litri B
bool feasible(int T) {
    double sumA = 0.0, sumB = 0.0;
    for (int i = 0; i < N; i++) {
        sumA += (double)T / a[i];
        sumB += (double)T / b[i];
    }
    if (sumA + EPS < L || sumB + EPS < L) return false;

    sort_by_ratio();

    double A_left = sumA;
    double B_need = (double)L;
    for (int k = 0; k < N && B_need > EPS; k++) {
        int i = ord[k];
        double capB_lit = (double)T / b[i];
        double take = (capB_lit < B_need ? capB_lit : B_need);
        A_left -= ratio_[i] * take;   // pierdem A cand mutam timp la B
        B_need -= take;
    }
    return (B_need <= EPS && A_left + EPS >= L);
}

int main() {
    freopen("lapte.in", "r", stdin);
    freopen("lapte.out", "w", stdout);

    if (!(cin >> N >> L)) return 0;
    for (int i = 0; i < N; i++) {
        cin >> a[i] >> b[i];
        ratio_[i] = (double)b[i] / a[i];
    }

    // 1) cautare binara pe T
    int lo = 0, hi = 1;
    while (!feasible(hi)) hi <<= 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }
    int T = lo;

    // 2) reconstruim timpii (minute) tA[i], tB[i] pentru T
    sort_by_ratio();

    // alocare reala: cati litri B dam fiecaruia (apoi convertim la minute)
    double tB_real[MAXN];        // minute reale pe B (double)
    for (int i = 0; i < N; i++) tB_real[i] = 0.0;

    double B_need = (double)L;
    for (int k = 0; k < N && B_need > EPS; k++) {
        int i = ord[k];
        double capB_lit = (double)T / b[i];
        double take = (capB_lit < B_need ? capB_lit : B_need);
        tB_real[i] = take * b[i];          // minute pe B pentru i
        B_need -= take;
    }

    // rotunjim minutele in jos si calculam litrii obtinuti
    int tA[MAXN], tB[MAXN];
    double sumA = 0.0, sumB = 0.0;
    for (int i = 0; i < N; i++) {
        tB[i] = (int)floor(tB_real[i] + 1e-9);  // minute intregi pe B
        if (tB[i] > T) tB[i] = T;
        tA[i] = T - tB[i];
        sumA += (double)tA[i] / a[i];
        sumB += (double)tB[i] / b[i];
    }

    // daca lipseste putin pe B (din cauza floor), mai adaugam minute la B la rapoarte mici
    if (sumB + EPS < L) {
        for (int k = 0; k < N && sumB + EPS < L; k++) {
            int i = ord[k];
            if (tB[i] == T) continue;
            // cate minute ar trebui in cel mai rau caz doar la i
            double needLit = (double)L - sumB;
            double needMin = needLit * b[i];
            int add = (int)ceil(needMin - EPS);
            if (add < 0) add = 0;
            if (tB[i] + add > T) add = T - tB[i];
            if (add > 0) {
                tB[i] += add;
                tA[i] -= add;
                sumB += (double)add / b[i];
                sumA -= (double)add / a[i];
            }
        }
    }

    // (optional) daca cumva A a scazut sub L (rar), reechilibram dinspre rapoarte mari
    if (sumA + EPS < L) {
        for (int k = N-1; k >= 0 && sumA + EPS < L; k--) {
            int i = ord[k];
            if (tB[i] == 0) continue;
            double needA = (double)L - sumA;
            int give = (int)ceil(needA * a[i] - EPS);
            if (give < 0) give = 0;
            if (give > tB[i]) give = tB[i];
            if (give > 0) {
                tB[i] -= give;
                tA[i] += give;
                sumB -= (double)give / b[i];
                sumA += (double)give / a[i];
            }
        }
    }

    // 3) afisare EXACT cum cere infoarena: T, apoi pe fiecare linie tA[i] tB[i] (minute)
    cout << T << "\n";
    for (int i = 0; i < N; i++) {
        cout << tA[i] << " " << tB[i] << "\n";
    }
    return 0;
}