Cod sursa(job #1656054)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 18 martie 2016 17:51:42
Problema Loto Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 110

using namespace std;

int a[MAXN], n, s, nq;
struct elem
{
    int val, ind;
    elem(int val = 0, int ind = 0) : val(val), ind(ind) { }
    bool operator()(elem x, elem y) { return x.val < y.val; }
}part[MAXN*MAXN*MAXN];

void citire()
{
    scanf("%d %d\n", &n, &s);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
}

void solvePart()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                part[++nq] = elem(a[i]+a[j]+a[k], nq);
}

void print(int ind)
{
    ind--;
    printf("%d %d %d ", a[ind/(n*n)+1], a[(ind/n)%n+1], a[ind%n+1]);
}

int main()
{
    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);

    citire();
    solvePart();
    int step = 1, val, must;
    sort(part+1, part+1+nq, elem());
    for (int i = 1; i <= nq; i++) {
        for (step = 1; step < nq; step <<= 1);
        must = s-part[i].val;
        for (val = 1; step; step >>= 1)
            if (val + step <= nq && part[val+step].val <= must)
                val += step;
        if (part[val].val == must) {
            print(part[i].ind);
            print(part[val].ind);
            return 0;
        }
    }
    printf("-1");

    return 0;
}