Cod sursa(job #1080988)

Utilizator impulseBagu Alexandru impulse Data 13 ianuarie 2014 04:04:59
Problema Loto Scor 5
Compilator c Status done
Runda Arhiva de probleme Marime 1.92 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>

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

int swap(tuple* a, tuple* b)
{
    tuple aux = *a;
    *a = *b;
    *b = aux;
    return 0;
}

int sort(tuple* T, int l, int r)
{
    if(r > l)
    {
        int s = l, d = r, w = 1;
        while(s != d)
        {
            if(T[s].s <= T[d].s)
            {
                if(w) s++;
                else d--;
            }
            else
            {
                swap(T + s, T + d);
                w ^= 1;
            }
        }
        sort(T, l, s - 1);
        sort(T, s + 1, r);
    }
    return 0;
}

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);
    tuple* T = (tuple*)malloc(n*n*n * sizeof(int));
    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 - 1, 0, tx);
    for(i = 0; 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;
}