Cod sursa(job #203526)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 17 august 2008 11:57:56
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
using namespace std;

#include <cstdio>
#include <algorithm>

#define IN "loto.in"
#define OUT "loto.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i) 
#define N_MAX 1<<7 


int N,S;
int v[N_MAX];
struct str{int s,p;}; 
str V[N_MAX];

void scan()
{
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d%d\n", &N,&S);
	FOR(i,1,N)
		scanf("%d", &v[i]);
}

inline int comp(const str &x,const str &y)
{
	if(x.s < y.s)
		return 1;
	return 0;
}	
		
inline int make(int x,int y,int z)
{
	int ret=0,i=4,j=7,k=10,auxv[10];
	while(i-1)
	{	
		auxv[--i] = x%10; 
		auxv[--j] = y%10;
		auxv[--k] = z%10;
		x/=10;y/=10;z/=10;
	}
	FOR(i,1,9)
		ret = ret * 10 + auxv[i];
	return ret;	
}		

void print(int x,int y)
{
	int v1[10]={0},v2[10]={0};
	while(V[x].p)
		v1[ ++v1[0] ] = V[x].p%10,V[x].p/=10;
	while(V[y].p)
		v2[ ++v2[0] ] = V[y].p%10,V[y].p/=10;
	while(v1[0] < 9)
		++v1[0];
	while(v2[0] < 9)
		++v2[0];
	
	FOR(i,1,3)
		swap( v1[(i-1)*3+1] , v1[(i-1)*3+3] );
	FOR(i,1,3)
		swap( v2[(i-1)*3+1] , v2[(i-1)*3+3] );
	
	FOR(i,1,3)
	{
		int ok=0;
		FOR(j,1,3)
		{
			if(v1[(i-1)*3+j])
				ok = 1;
			if(ok)
				printf("%d", v1[(i-1)*3+j]);
		}
		printf(" ");
	}
	
	FOR(i,1,3)
	{
		int ok=0;
		FOR(j,1,3)
		{
			if(v2[(i-1)*3+j])
				ok = 1;
			if(ok)
				printf("%d", v2[(i-1)*3+j]);
		}
		printf(" ");
	}		
}

inline int find(int val)
{
	int p=1,q=V[0].s,m;  
    while(p<q)  
    {  
        m=(p+q)>>1;  
        if(val<=V[m].s)  
            q=m;  
        else  
            p=m+1;  
    }  
    if(V[p].s==val)  
        return p;  
    return 0;  
}

void solve()
{
	FOR(i,1,N)
	FOR(j,i,N)
	FOR(k,j,N)
	{
		int sum = v[i] + v[j] + v[k];
		if(sum > S)
			continue;
		V[ ++V[0].s ].s = sum;
		V[ V[0].s ].p = make(i,j,k);
	}	
	sort(V+1, V+V[0].s+1, comp);
	FOR(i,1,V[0].s)
	{
		int j = find(S-V[i].s);
		if(j)
		{
			print(i,j);
			return;
		}
	}	
	printf("-1\n");
}

int main()
{
	scan();
	solve();
	return 0;
}