Cod sursa(job #233675)

Utilizator cotofanaCotofana Cristian cotofana Data 18 decembrie 2008 21:10:24
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>
#define dim 1000001
//#define dim 100

int n, in=0;
long v[101], m[dim], s, l[7];
char p[dim][3];

int caut_bin(long val)
{
	int i, step;  
	for (step = 1; step < n*n*n; step <<= 1);
	for (i = 0; step; step >>= 1)
		if (i + step < n*n*n && m[i + step] <= val)
		i += step;  
	return i;  	
}

void qsort(long *a, int lo, int hi)
{
    int i=lo, j=hi, h;
    long x=a[(lo+hi)/2];

    do
    {    
        while (a[i]<x) i++; 
        while (a[j]>x) j--;
        if (i<=j)
        {
            h=a[i]; a[i]=a[j]; a[j]=h;
	    h=p[i][1]; p[i][1]=p[j][1]; p[j][1]=h;
	    h=p[i][2]; p[i][2]=p[j][2]; p[j][2]=h;
	    h=p[i][3]; p[i][3]=p[j][3]; p[j][3]=h;
            i++; j--;
        }
    } while (i<=j);

    if (lo<j) qsort(a, lo, j);
    if (i<hi) qsort(a, i, hi);
}

int main()
{
	int i, j, k, ok, c;
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);
	scanf("%d %ld\n", &n, &s);
	for (i=0; i<=n; i++) scanf("%ld ", &v[i]);
	for (i=0; i<n; i++)
		for (j=0; j<n; j++)
			for (k=0; k<n; k++)
			{
				m[in]=v[i]+v[j]+v[k];
				p[in][1]=i;
				p[in][2]=j;
				p[in++][3]=k;
			}
	qsort(m, 0, n*n*n-1);
	for (i=0; i<n*n*n; i++)
	{
		c=caut_bin(s-m[i]);
		if (m[i]+m[c]==s)
		{
			l[1]=v[p[i][1]];
			l[2]=v[p[i][2]];
			l[3]=v[p[i][3]];
			l[4]=v[p[c][1]];
			l[5]=v[p[c][2]];
			l[6]=v[p[c][3]];
			qsort(l, 1, 6);
			for (i=1; i<=6; i++) printf("%ld ", l[i]);
			return 0;
		}
		if (i)
		{
                	i++;
			while (m[i]==m[i-1]) i++;
			i--;
		}
	}
	printf("-1\n");
	return 0;
}