Cod sursa(job #587589)

Utilizator stef93Stefan Gilca stef93 Data 5 mai 2011 11:20:09
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;

int b[104];
struct U{ int x1,x2,x3,s;}a[1000003];
bool compare(U x,U y)
{
     return x.s<y.s;
}

int main()
{
    int n,i,j,k,s;
    fstream in,out;
    in.open("loto.in",ios::in);
    in>>n>>s;
    for(i=0;i<n;i++)
    in>>b[i];
    int nr=0;
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    for(k=0;k<n;k++)
    {
             a[nr].x1=b[i];
             a[nr].x2=b[j];
             a[nr].x3=b[k];
             a[nr++].s=b[i]+b[j]+b[k];
    }
    sort(a,a+nr,compare);    
    int log=1;
    out.open("loto.out",ios::out);
    for(;log<nr;log<<=1);   
    for(i=0;i<nr;i++)
    {
                     int step,poz;
                     for(step=log,poz=nr;step>0;step>>=1)
                     if(poz-step>0 && (a[i].s+a[poz-step].s)>=s)
                     poz-=step;
                     if(a[i].s+a[poz].s==s){out<<a[i].x1<<' '<<a[i].x2<<' '<<a[i].x3<<' '<<a[poz].x1<<' '<<a[poz].x2<<' '<<a[poz].x3<<'\n';return 0;}
    }
    out<<"-1\n";
    return 0;
}