Cod sursa(job #585793)

Utilizator maritimCristian Lambru maritim Data 30 aprilie 2011 11:53:01
Problema Fabrica Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 5-9 Marime 1.03 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define INF 1000000

int A[50001];
int B[50001];
int N;
int a;
int b;
int nr;
int MAX = -INF;

void swap(int a,int b)
{
	int c = A[a];
	A[a] = A[b];
	A[b] = c;
	c = B[a];
	B[a] = B[b];
	B[b] = c;
}

void sorti(void)
{
	for(int i=2;B[i] && A[i]*B[i]<A[i-1]*B[i-1];i++)
		swap(i,i-1);
}

void solve(void)
{
	nr += A[2]/A[1];
	B[1] = nr;
	for(;nr<N;)
	{
		float x = (A[1]*B[1]-A[2]*B[2])/A[2];
		if(x != 0)
			if(x<1)
			{
				B[2] ++;
				nr ++;
				sorti();
			}
			else
			{
				B[2] += (int)x;
				nr += (int)x;
				sorti();
			}
		else
		{
			nr ++;
			B[1] ++;
			sorti();
		}
	}
	if(nr>N)
		B[2] -= N-nr;
	for(int i=1;i<=a;i++)
		if(MAX<B[i])
			MAX = B[i];
}

int main()
{
	FILE *f = fopen("fabrica.in","r");
	FILE *g = fopen("fabrica.out","w");
	
	fscanf(f,"%d %d %d",&N,&a,&b);
	for(int i=1;i<=a;i++)
		fscanf(f,"%d",&A[i]);
	sort(A+1,A+a+1);
	solve();
	fprintf(g,"%d",MAX);
	
	fclose(g);
	fclose(f);
	return 0;
}