Cod sursa(job #1170428)

Utilizator ThomasFMI Suditu Thomas Thomas Data 13 aprilie 2014 16:18:12
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define NMax 105

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

int n,s;
int M[NMax];

int sol[4];

struct solutie{int a,b,c,sum;}u;

vector<solutie> pos;

void bkt(int k)
{
    for(int i=1;i<=n;i++)
    {
        sol[k]=i;
        if(sol[k]>=sol[k-1])
        {
            if(k==3)
            {
                u.sum=M[sol[1]]+M[sol[2]]+M[sol[3]];
                u.a=M[sol[1]];
                u.b=M[sol[2]];
                u.c=M[sol[3]];
                pos.push_back(u);
            }
            else bkt(k+1);
        }
    }
}

bool Compare(solutie i,solutie j) { return i.sum<j.sum; }

int bs(int x)
{
    int j,step;
    for(step=1;step<=pos.size();step<<=1);
    for(j=1;step;step>>=1)
        if(j+step<=pos.size() && pos[j+step-1].sum<=x) j+=step;

    return j-1;
}

int main()
{
    int i,poz;

    f>>n>>s;
    for(i=1;i<=n;i++) f>>M[i];

    bkt(1);

    sort(pos.begin(),pos.end(),Compare);

    int ok=0;
    for(i=0;i<pos.size();i++)
    {
        poz=bs(s-pos[i].sum);
        if(pos[poz].sum==s-pos[i].sum)
        {
            g<<pos[i].a<<" "<<pos[i].b<<" "<<pos[i].c<<" ";
            g<<pos[poz].a<<" "<<pos[poz].b<<" "<<pos[poz].c<<"\n";
            ok=1;
            break;
        }
    }

    if(!ok) g<<"-1\n";

    f.close();
    g.close();
    return 0;
}