Cod sursa(job #632003)

Utilizator sebii_cSebastian Claici sebii_c Data 10 noiembrie 2011 00:20:53
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define KMAX 102
#define NMAX 1000005

long long A[NMAX], V[KMAX], pos[7];
int nr;

int search(long long val)
{
    int lo = 1, hi = nr, mid;
    while (lo <= hi) {
	mid = lo + (hi-lo)/2;
	if (A[mid] == val)
	    return 1;
	else if (val < A[mid])
	    hi = mid - 1;
	else
	    lo = mid + 1;
    }
    return -1;
} 

int main()
{
    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);
    int N, i, j, k;
    long long S;
    scanf("%d %lld", &N, &S);
    
    for (i=1; i<=N; ++i) 
	scanf("%lld", &V[i]);

    for (i=1; i<=N; ++i)
	for (j=i; j<=N; ++j)
	    for (k=j; k<=N; ++k) 
		if (V[i] + V[j] + V[k] <= S)
		    A[++nr] = V[i] + V[j] + V[k];
    
    sort(A+1, A+nr+1);
    
    long long Sum;
    pos[0] = -1;
    for (i=1; i<=N; ++i) { 
	for (j=i; j<=N; ++j) {
	    for (k=j; k<=N; ++k) {
		if (search(S-V[i]-V[j]-V[k]) == 1) { 
		    pos[0] = i, pos[1] = j, pos[2] = k;
		    Sum = S - V[i] - V[j] - V[k];
		    break;
		}
	    }
	    if (pos[0] == i)
		break;
	}
	if (pos[0] == i)
	    break;
    }

    if (pos[0] == -1) {
	printf("-1\n");
	return 0;
    }

    for (i=1; i<=N; ++i) {
	for (j=i; j<=N; ++j) {
	    for (k=j; k<=N; ++k) {
		if (V[i]+V[j]+V[k] == Sum) {
		    pos[3] = i, pos[4] = j, pos[5] = k;
		    break;
		}
	    }
	    if (pos[3] == i)
		break;
	}
	if (pos[3] == i)
	    break;
    }

    printf("%lld %lld %lld %lld %lld %lld\n", V[pos[0]], V[pos[1]], V[pos[2]], 
	    V[pos[3]], V[pos[4]], V[pos[5]]);
    return 0;
}