Cod sursa(job #963720)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 18 iunie 2013 17:43:20
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <algorithm>

using namespace std;

struct numere {
    int a;
    int b;
    int c;
    int s;
};

int cmp (numere x, numere y) {
    return x.s < y.s;
}
int v[101];
numere t[1000002];

int n, dt, i, j, k, p, u, m, s, gasit = 0, sum;

int main() {
    ifstream fin("loto.in");
    ofstream fout("loto.out");
    fin>>n>>s;
    for (i=1;i<=n;i++)
        fin>>v[i];


    for (i=1;i<=n;i++)
        for (j=i;j<=n;j++)
            for (k=j;k<=n;k++) {
                dt++;
                t[dt].a = v[i];
                t[dt].b = v[j];
                t[dt].c = v[k];
                t[dt].s = v[i] + v[j] + v[k];
            }

    sort(t, t+dt+1, cmp);

    for (i=1;i<=n && !gasit;i++)
        for (j=i;j<=n && !gasit;j++)
            for (k=j;k<=n&& !gasit;k++) {
                sum = s - (v[i]+v[j]+v[k]);
                // caut binar pe sum in t
                p = 1; u = dt;
                while (p<=u) {
                    m = (p+u)/2;
                    if (sum == t[m].s) {
                        // am solutie
                        fout<<v[i]<<" "<<v[j]<<" "<<v[k]<<" "
                            <<t[m].a<<" "<<t[m].b<<" "<<t[m].c<<"\n";
                        gasit = 1;
                        break;
                    }
                    if (sum > t[m].s)
                        p = m+1;
                    else
                        u = m-1;

                }

            }

    if (!gasit)
        fout<<"-1\n";
    return 0;
}