Cod sursa(job #217903)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 30 octombrie 2008 20:24:47
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("loto.in");
ofstream fout ("loto.out");

struct loto
{
     int a,b,S;
};

int sir[105];
loto sume[1000010];
int n,s,k;
int nr=0;

void citire()
{
     fin>>n>>s;
     for (int i=1;i<=n;i++)
          fin>>sir[i];
     sort(sir+1,sir+n+1);
}

bool operator<(loto x,loto y)
{
     return x.S<y.S;
}

void su()
{
     nr=1;
     int x;
     for (int i=1;i<=n;i++)
          for (int j=i;j<=n;j++)
               for (int k=j;k<=n;k++)
               {
                    x=sir[i]+sir[j]+sir[k];
                    if (x<=s)
                    {
                         sume[nr].S=x;
                         sume[nr].b=sir[j];
                         sume[nr++].a=sir[i];
                    }
                    else
                         break;
               }
     sort(sume,sume+nr);
}

void calcul()
{
     for (int i=1;i<=nr;i++)
          {
          int x=s-sume[i].S;
          int s=1,d=nr,mij,val;
          while (s!=d)
          {
               mij=(s+d)>>1;
               val=sume[mij].S;
               if (val==x)
               {
                    fout<<sume[i].a<<" ";
                    fout<<sume[i].S-sume[i].a-sume[i].b<<" ";
                    fout<<sume[i].b<<" ";
                    fout<<sume[mij].b<<" ";
                    fout<<sume[mij].a<<" ";
                    fout<<sume[mij].S-sume[mij].a-sume[mij].b<<" ";
                    return ;
               }
               if (val<x)
                    s=mij+1;
               else
                    d=mij;
          }
          }
     fout<<-1;
}
int main ()
{
     citire();
     su();
     calcul();
     return 0;
}