Cod sursa(job #1315881)

Utilizator ThomasFMI Suditu Thomas Thomas Data 13 ianuarie 2015 11:25:22
Problema Loto Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.44 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;
}