Cod sursa(job #1809355)

Utilizator raresm44vasile rares raresm44 Data 18 noiembrie 2016 21:02:47
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <fstream>
using namespace std;
const int K=666019;

ifstream f("loto.in");
ofstream g("loto.out");

int n,sum,v[101],val[1000001],urm[1000001],lst[K],nr;

bool exista(int x) {
    int r=x%K,p;
    p=lst[r];
    while(p!=0) {
        if(val[p]==x)
            return true;
        p=urm[p];
    }
    return false;
}

void adauga (int x) {
    if (exista(x)) return;
    int r=x%K;
    nr++;
    val[nr]=x;
    urm[nr]=lst[r];
    lst[r]=nr;
}

void scrie(int x) {
    for(int l=1; l<=n; l++)
        for(int o=l; o<=n; o++)
            for(int p=o; p<=n; p++)
                if(x-v[l]-v[o]-v[p]==0)
                {
                    g<<v[l]<<' '<<v[o]<<' '<<v[p];
                    return;
                }
}

int main() {
    f>>n>>sum;
    for (int i=1; i<=n; ++i)
        f>>v[i];

    int nr=0;
    for(int i=1; i<=n; i++)
        for(int j=i; j<=n; j++)
            for(int k=j; k<=n; k++)
                adauga(v[i]+v[j]+v[k]);
    for(int i=1; i<=n; i++)
        for(int j=i; j<=n; ++j)
            for(int k=j; k<=n; k++)
                if(v[i]+v[j]+v[k]<=sum && exista(sum-v[i]-v[j]-v[k])) {
                    g<<v[i]<<' '<<v[j]<<' '<<v[k]<<' ';
                    scrie(sum-v[i]-v[j]-v[k]);
                    return 0;
                }
                else
                g<<'-1';

    //cout << "Hello world!" << endl;
    return 0;
}