Cod sursa(job #217712)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 29 octombrie 2008 22:00:02
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 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);
}

void poz(int li,int ls,int &k)
{
     int i=li,j=ls,i1=0,j1=-1;
     int aux;
     loto aux1;
     while (i<j)
     {
          if (sume[i].S>sume[j].S)
          {
               aux1=sume[i];
               sume[i]=sume[j];
               sume[j]=aux1;
               aux=i1;
               i1=-j1;

               j1=-aux;
          }
          i+=i1;
          j+=j1;
     }
     k=i;
}

void qsort(int li,int ls)
{
     if (li<ls)
     {
          poz(li,ls,k);
          qsort(li,k);
          qsort(k+1,ls);
     }
}

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;
               }
          qsort(1,nr-1);
}

int cauta(int x)
{
     int s=1,d=nr,mij,val;
     while (s!=d)
     {
          mij=(s+d)>>1;
          val=sume[mij].S;
          if (val==x)
               return mij;
          if (val<x)
               s=mij+1;
          else
               d=mij;
     }
     return -1;
}

void calcul()
{
     int c;
     for (int i=1;i<=nr;i++)
          {
               c=cauta(s-sume[i].S);
               if (c!=-1)
               {
                    fout<<sume[i].a<<" ";
                    fout<<sume[i].S-sume[i].a-sume[i].b<<" ";
                    fout<<sume[i].b<<" ";
                    fout<<sume[c].b<<" ";
                    fout<<sume[c].a<<" ";
                    fout<<sume[c].S-sume[c].a-sume[c].b<<" ";
                    return ;
               }
          }
     fout<<-1;
}
int main ()
{
     citire();
     su();
     calcul();
     return 0;
}