Cod sursa(job #478870)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 20 august 2010 20:24:34
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
# include <cstdio>
# include <algorithm>
# define  N  6
using  namespace  std;
    int n, S, a[1000001], v[101], i, j, k, cnt, s, caut, sc, ve[10], c2, sum=0;
	struct stu {
		int i,j;
	};
	stu sf;
    int cb (int in, int sf, int find, int a[]){
		while (in<=sf){
			int m= (in+sf) >> 1;
			if (a[m]==find) return m;
			else
			if (a[m]>find) in=m+1;
			else sf=m-1;
		}
		return 0;
	}
    int main (){
		freopen ("loto.in", "r", stdin);
		freopen ("loto.out", "w", stdout);
		scanf ("%d%d", &n, &S);
		for (i=1;i<=n;++i) scanf ("%d", &v[i]);
		sort (v+1, v+n+1);
		sum=v[n]*6;
		if (sum<S){
			printf ("-1\n");
			return 0;
		}
		for (i=1;i<=n;++i)
			for (j=1;j<=n;++j)
				for (k=1;k<=n;++k)
					a[++cnt]=v[i]+v[j]+v[k];		
        sort (a+1, a+cnt+1);
		for (i=1;i<=n;++i)
			for (j=1;j<=n;++j)
				for (k=1;k<=n;++k){
					s=v[i]+v[j]+v[k];
					sc=S-s;
					caut=cb (1, n, sc, a);
					if (caut){
						ve[1]=v[i];
						ve[2]=v[j];
						ve[3]=v[k];
						for (sf.i=1;sf.i<=n;++sf.i)
							for (sf.j=1;sf.j<=n;++sf.j){
								s=v[sf.i]+v[sf.j];
								c2=cb (1, n, sc-s, v);
								if (c2){
									ve[4]=sf.i;
									ve[5]=sf.j;
									ve[6]=c2;
									sort (ve+1, ve+N+1);
								    printf ("%d %d %d %d %d %d\n", ve[1], ve[2], ve[3], ve[4], ve[5], ve[6]);
								}
								return 0;
							}
					}
				}
		printf ("-1\n");
		return 0;
	}