Cod sursa(job #1080991)

Utilizator impulseBagu Alexandru impulse Data 13 ianuarie 2014 04:22:53
Problema Loto Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
//
//  main.c
//  loto
//
//  Created by Alexandru Bâgu on 1/13/14.
//  Copyright (c) 2014 Alexandru Bâgu. All rights reserved.
//

#include <stdio.h>
#include <algorithm>
#include <memory.h>
#include <stdlib.h>
using namespace std;

typedef struct  {
    int s, a, b, c;
} mtuple;


int cmp(mtuple a, mtuple b)
{
    return a.s < b.s;
}

int main(int argc, const char * argv[])
{
    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);
    int n, s;
    scanf("%d %d", &n, &s);
    int *v = (int*)malloc(n * sizeof(int));
    int i, j, k, tx, q;
    for(i = 0; i < n; i++)
        scanf("%d", v + i);
    mtuple* T = (mtuple*)malloc((n*n*n+1) * sizeof(mtuple));
    tx = 0;
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            for(k = 0; k < n; k++)
            {
                T[tx].a = v[i];
                T[tx].b = v[j];
                T[tx].c = v[k];
                T[tx].s = v[i] + v[j] + v[k];
                tx++;
            }
        }
    }
    
    sort(T, T + tx, cmp);
    for(i = 1; i <= tx; i++)
    {
        k = 1 << 30;
        j = 0;
        while(k >>= 1 > 0)
        {
            if(j + k < tx)
            {
                q = T[j + k].s + T[i].s;
                if(q <= s)
                {
                    j += k;
                    if(q == s)
                    {
                        printf("%d %d %d %d %d %d", T[i].a, T[i].b, T[i].c, T[j].a, T[j].b, T[j].c);
                        return 0;
                    }
                }
            }
        }
    }
    printf("%d", -1);
    return 0;
}