Cod sursa(job #383181)

Utilizator shnakoVlad Schnakovszki shnako Data 15 ianuarie 2010 22:11:08
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
#include <string.h>
FILE *f=fopen("loto.in", "r"), *g=fopen("loto.out", "w");
long i, j, n, inj, v[105], sum, h, z, rez[10], temp;
bool s[600000010], sw;

void citeste(void)
{
	fscanf(f, "%ld%ld", &n, &sum);
	for (i=1;i<=n;i++)
		fscanf(f, "%ld", &v[i]);
	fclose(f);
}

void sort(void)
{
	inj=n;
	while(inj>1)
	{
		inj/=2;
		do{
			sw=0;
			for( i=1;i<=n-inj;i++)
				if(v[i]>v[i+inj])
				{
					v[i]=v[i]^v[i+inj];
					v[i+inj]=v[i]^v[i+inj];
					v[i]=v[i]^v[i+inj];
					sw=1;
				}
		}while(sw!=0);
	}
}

long sume(void)
{
	s[0]=1;
	for (i=1;i<=n;i++)
		for (h=1;h<=z;h++)
			for (j=sum-v[i];j>=0;j--)
				if (s[j])
					if (j+v[i]==temp)
						return v[i];
					else
						if (j+v[i]<temp)
							s[j+v[i]]=1;
	return 0;
}

void tip(void)
{
	if (rez[1]+rez[2]+rez[3]+rez[4]+rez[5]+rez[6]!=sum)
		fprintf(g, "-1");
	else
		for (i=1;i<=6;i++)
			fprintf(g, "%ld ", rez[i]);
	fclose(g);
}

int main(void)
{
	citeste();
	sort();
	temp=sum;
	for (z=5;z>=1;z--)
	{
		for (i=1;i<=temp;i++)
			s[i]=0;
		rez[z]=sume();
		temp-=rez[z];
	}
	rez[6]=temp;
	for (i=1;i<6;i++)
		for (j=i+1;j<=6;j++)
			if (rez[i]>rez[j])
			{
				rez[i]=rez[i]^rez[j];
				rez[j]=rez[i]^rez[j];
				rez[i]=rez[i]^rez[j];
			}
	tip();
	return 0;
}