Cod sursa(job #1480633)

Utilizator dnprxDan Pracsiu dnprx Data 2 septembrie 2015 22:12:46
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <bits/stdc++.h>
#define modulo 123457

using namespace std;

struct Patru
{
    int s, x, y, z;
};

int a[103], n, S, m;
Patru t[1000005];

void Citire()
{
    int i;
    ifstream fin("loto.in");
    fin >> n >> S;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    fin.close();
}

inline bool Compara(const Patru A, const Patru B)
{
    return A.s < B.s;
}

void ConstrT()
{
    int i, j, k;
    m = 0;
    for (i = 1; i <= n; i++)
        for (j = i; j <= n; j++)
            for (k = j; k <= n; k++)
            {
                t[++m].s = a[i] + a[j] + a[k];
                t[m].x = i;
                t[m].y = j;
                t[m].z = k;
            }
    sort(t + 1, t + m + 1, Compara);
}

int CautBin(int st, int dr, int x)
{
    int mij;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (t[mij].s == x) return mij;
        if (t[mij].s < x) st = mij + 1;
        else dr = mij - 1;
    }
    return -1;
}

void Rezolva()
{
    int i, j, k, suma, poz;
    ofstream fout("loto.out");
    for (i = 1; i <= n; i++)
        for (j = i; j <= n; j++)
            for (k = j; k <= n; k++)
            {
                suma = S - (a[i] + a[j] + a[k]);
                poz = CautBin(1, m, suma);
                if (poz != -1)
                {
                    fout << a[i] << " " << a[j] << " " << a[k] << " ";
                    fout << a[t[poz].x] << " " << a[t[poz].y] << " " << a[t[poz].z] << "\n";
                    fout.close();
                    return ;
                }
            }
    fout << "-1\n";
    fout.close();
}

int main()
{
    Citire();
    ConstrT();
    Rezolva();
    return 0;
}