Cod sursa(job #777079)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 10 august 2012 22:29:06
Problema Loto Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <bitset>>
#include <vector>
#include <algorithm>
#define N 110
#define SM 300000010

using namespace std;

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


int n,i,j,k,A[N],S,s;
bitset<SM> M;
vector<int> ANS;

void Solve1 ()
{
    for (i=1; i<=n; i++)
        for (j=i; j<=n; j++)
            for (k=j; k<=n; k++)
                if (M[S-A[i]-A[j]-A[k]])
                {
                    S-=A[i]+A[j]+A[k];
                    ANS.push_back(A[i]);
                    ANS.push_back(A[j]);
                    ANS.push_back(A[k]);
                    return;
                }
}

void Solve2 ()
{
    for (i=1; i<=n; i++)
        for (j=i; j<=n; j++)
            for (k=j; k<=n; k++)
                if (A[i]+A[j]+A[k]==S)
                {
                    ANS.push_back(A[i]);
                    ANS.push_back(A[j]);
                    ANS.push_back(A[k]);
                    return;
                }
}


int main ()
{
    f >> n >> S;
    for (i=1; i<=n; i++)
        f >> A[i];
    for (i=1; i<=n; i++)
        for (j=i; j<=n; j++)
            for (k=j; k<=n; k++)
                M[A[i]+A[j]+A[k]]=1;
    s=S;
    Solve1();
    if (s==S)
    {
        g << -1 << '\n';
        f.close();
        g.close();
        return 0;
    }
    Solve2();
    sort(ANS.begin(),ANS.end());
    for (i=0; i<ANS.size(); i++)
        g << ANS[i] << ' ';
    g << '\n';
    f.close();
    g.close();
    return 0;
}