Cod sursa(job #1810268)

Utilizator toniobFMI - Barbalau Antonio toniob Data 19 noiembrie 2016 20:23:03
Problema Lapte Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <iostream>
#include <cmath>
using namespace std;

const int nMax = 110;
int n, l;
struct litrii {
	int a, b;
} v[nMax];
int a[nMax][nMax], abaut[nMax][nMax];
ifstream in("lapte.in");
ofstream out("lapte.out");

void citire() {
	in >> n >> l;
	for (int i = 1; i <= n; ++i) {
		in >> v[i].a >> v[i].b;
	}
}

bool ok(int t) {
	// a[i][j] = nr maxim de litrii de b care pot fii bauti de primii i oameni 
	// avand in vedere ca sau baut j litrii de a
	for (int lc = 1; lc <= l; ++lc) {
		a[0][lc] = -2000000;
	}
	for (int i = 1; i <= n; ++i) {
		for (int lc = 0; lc <= l; ++lc) {
			// vreau sa calculez a[i][lc]
			// iau pa rand cati litrii de a vreau sa bea i
			a[i][lc] = -1;
			for (int k = 0; k <= lc; ++k) {
				// i bea k litrii de a
				if (k * v[i].a > t) {
					continue;
				}
				int lb = (t - k * v[i].a) / v[i].b + a[i-1][lc - k];
				if (a[i][lc] < lb) {
					a[i][lc] = lb;
					abaut[i][lc] = k;
				}
			}
		}
	}
	return a[n][l] >= l;
}

int bs() {
	int i, step = 1 << 7;
	for (i = 0; step; step >>= 1) {
		if ( !ok(i+step) ) {
			i += step;
		}
	}
	return i + 1;
}

void reconstruieste(int t, int i, int lc) {
	if (i != 1) {
		reconstruieste(t, i - 1, lc - abaut[i][lc]);
	}
	out << abaut[i][lc] << ' ' << (t - abaut[i][lc] * v[i].a) / v[i].b << '\n';
}

int main() {

	citire();

	int timp = bs();

	out << timp << '\n';

	ok(timp);
	reconstruieste(timp, n, l);

	return 0;
}