Cod sursa(job #3142924)

Utilizator mihai.alphamihai craciun mihai.alpha Data 25 iulie 2023 21:25:08
Problema Lapte Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("lapte.in");
ofstream fout("lapte.out");

int n, l;
int a[102], b[102];

int aa[102], bb[102];

bool ver(int t)  {
	double suma, sumb;
	suma = 0, sumb = 0;
	for(int i = 1;i <= n;i++)
		suma += 1.0 / a[i], sumb += 1.0 / b[i];
	int l1, l2;
	l1 = l, l2 = l;
	for(int i = 1;i <= n;i++)  {
		if(l1 <= 0)  {
			l2 -= t / b[i];
			continue;
		}
		if(l2 <= 0)  {
			l1 -= t / a[i];
			continue;
		}
		if(1.0 * l1 - 1.0 * t * (suma) > 1.0 * l2 - 1.0 * t * (sumb))  {
			int rest = 0;
			aa[i] = t / a[i];
			if(t / a[i] > l1)  {
				rest = t - a[i] * l1;
				aa[i] = l1;
			}
			l1 -= t / a[i], l2 -= max(rest, (t % a[i])) / b[i];
			bb[i] = max(rest, (t % a[i])) / b[i];
		}
		else  {
			int rest = 0;
			bb[i] = t / b[i];
			if(t / b[i] > l2)  {
				rest = t - b[i] * l2;
				bb[i] = l2;
			}
			l2 -= t / b[i], l1 -= max(rest, (t % b[i])) / a[i];
			aa[i] = max(rest, (t % b[i])) / a[i];
		}
		suma -= 1.0 / a[i];
		sumb -= 1.0 / b[i];
	}
	if(l1 <= 0 && l2 <= 0)
		return 1;
	return 0;
}

int main()  {
	fin >> n >> l;
	for(int i = 1;i <= n;i++)
		fin >> a[i] >> b[i];
	int pas = 128;
	int r = -1;
	while(pas)  {
		if(100 >= r + pas && ver(100 - (r + pas)))  {
			r += pas;
		}
		pas >>= 1;
	}
	fout << 100 - r << "\n";
	for(int i = 1;i <= n;i++)
		fout << aa[i] << " " << bb[i] << "\n";
	return 0;
}