Cod sursa(job #1041015)

Utilizator NitaMihaitavoidcube NitaMihaita Data 25 noiembrie 2013 13:13:37
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<fstream>
#include<iostream>
#include<vector>
#define numaru 666019
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");
vector<long long> v[numaru],v2[numaru],v3[numaru];
long long w[100];

bool cauta(vector<long long> a[],long long x)
{
    int unde=x%numaru;
    vector<long long >::iterator i;
    for(i=a[unde].begin();i!=a[unde].end();++i)
        if(*i==x)return true;
    return false;
}
void adauga(vector<long long> a[],long long x)
{
    int unde=x%numaru;
    if(cauta(a,x)==false)a[unde].push_back(x);
}
int main()
{
    int n,p,q,k;
    long long x,s[3];
    f>>n>>x;
    for(k=0;k<n;++k)
    {
        f>>w[k];
        adauga(v,w[k]);
    }
    for(p=0;p<n;++p)for(q=0;q<n;++q)adauga(v2,w[p]+w[q]);
    for(p=0;p<n;++p)for(q=0;q<n;++q)for(k=0;k<n;++k)adauga(v3,w[p]+w[q]+w[k]);
    s[0]=-1;
    for(p=0;p<n;++p)for(q=0;q<n;++q)for(k=0;k<n;++k) if(x>=w[p]+w[q]+w[k] && cauta(v3,x-w[p]-w[q]-w[k])){ s[0]=w[p]; s[1]=w[q]; s[2]=w[k]; p=q=k=n; }
    if(s[0]==-1) { g<<"-1\n"; f.close(); g.close(); return 0; }
    g<<s[0]<<" "<<s[1]<<" "<<s[2]<<" ";
    x=x-s[0]-s[1]-s[2];
    for(k=0;k<n;++k) if(x>=w[k] && cauta(v2,x-w[k])){ g<<w[k]<<" "; x-=w[k]; k=n; }
    for(k=0;k<n;++k) if(x>=w[k] && cauta(v,x-w[k])){ g<<x-w[k]<<" "<<w[k]<<"\n"; k=n; }
    f.close();
    g.close();
    return 0;
}