Cod sursa(job #159402)

Utilizator rethosPaicu Alexandru rethos Data 14 martie 2008 09:19:36
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream.h>
#include <stdlib.h>
#define XM 1000001//100^3
#define NM 101
ofstream g("loto.out");
ifstream f("loto.in");
long v[NM],x[XM];
long n,s,nrx;
void swap(long a,long b)
{long aux=x[a];
 x[a]=x[b];
 x[b]=aux;
}
void qsort(long st,long dr)
{if(st>=dr) return;
 swap(st,rand()%(dr-st)+st);
 long i,l=st;
 for (i=st+1;i<=dr;i++)
    if(x[i]<x[st]) swap(i,++l);
 swap(st,l);
 qsort(st,l-1);
 qsort(l+1,dr);
}
void afis(long a)
{int i,j,k;
 for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
       for (k=1;k<=n;k++)
          if(v[i]+v[j]+v[k]==a)
            {g<<v[i]<<' '<<v[j]<<' '<<v[k];
             return;
            }
}
int main()
{
 int i,j,k;
 f>>n>>s;
 for (i=1;i<=n;i++) f>>v[i];
 f.close();
 for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
       for (k=1;k<=n;k++)
          {nrx++;
           x[nrx]=v[i]+v[j]+v[k];
          }
 qsort(1,nrx);
 long st=1,dr=nrx;
 while (st<=dr)
   {if(x[st]+x[dr]==s)
     {afis(x[st]);
      g<<' ';
      afis(x[dr]);
      g.close();
      return 0;
     }
    while (x[st]+x[dr]<s&&st<=nrx) st++;
    while (x[st]+x[dr]>s&&dr>=1) dr--;
   }
 g<<-1;
 g.close();
 return 0;
}