Cod sursa(job #154960)

Utilizator andrei.12Andrei Parvu andrei.12 Data 11 martie 2008 17:00:54
Problema Lapte Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>

using namespace std;

int n, cnt, i, rezultat;
struct ches{
	int a, b, c;
};
ches v[105], sol[105], s1[105];

inline int cmp(ches a, ches b){
	return a.c < b.c;
}
int check(int val){
	int st[105] = {0}, i, rs = cnt, x;
	for (i = 1; i <= n; i ++)
		s1[i].a = 0, s1[i].b = 0;

	for (i = 1; i <= n; i ++){
		x = min(val, rs*v[i].a);
		rs -= x / v[i].a;

		st[i] = x;
		s1[i].a = x / v[i].a;
		//printf("mai avem %d lapte, cu %d in momentul %d, x fiind %d\n", rs, st[i], i, x);
		if (rs <= 0)
			break;
	}

	if (rs > 0)
		return 0;

	rs = cnt;
	for (i = n; i; i --){
		x = min(val, rs*v[i].b);
		rs -= x / v[i].b;

		s1[i].b = x / v[i].b;
		if (st[i] + x > val)
			return 0;
		if (rs <= 0)
			break;
	}

	if (rs > 0)
		return 0;
	return 1;
}
int bs(){
	int li = 1, ls = 500, x, gs = 0;

	while (li <= ls){
		x = (li+ls) / 2;

		if (check(x)){
			gs = x;
			for (int i = 1; i <= n; i ++)
				sol[i].a = s1[i].a, sol[i].b = s1[i].b;

			ls = x-1;
		}
		else
			li = x+1;
	}

	return gs;
}
int main()
{
	freopen("lapte.in", "rt", stdin);
	freopen("lapte.out", "wt", stdout);

	scanf("%d%d", &n, &cnt);
	for (i = 1; i <= n; i ++){
		scanf("%d%d", &v[i].a, &v[i].b);
		v[i].c = v[i].a - v[i].b;
	}

	sort(v+1, v+n+1, cmp);

	rezultat = bs();

	printf("%d\n", rezultat);
	for (i = 1; i <= n; i ++)
		printf("%d %d\n", sol[i].a, sol[i].b);

	return 0;
}