Cod sursa(job #1019345)

Utilizator Dayanna000Amegica Dayanna Dayanna000 Data 30 octombrie 2013 22:53:59
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;
long as[1000000],a1[1000000],a2[1000000];
void qs(long stanga, long dreapta)
    {
       long i, j, piv, aux,x,y,z,mi,ma;
       i=stanga;
       j=dreapta;
       x=as[rand()%(j-i+1)+i];
       srand(time(0));
       y=as[rand()%(j-i+1)+i];
       srand(time(0));
       z=as[rand()%(j-i+1)+i];
       srand(time(0));
       if(x<=y && x<=z)
          mi=x;
       if(y<=x && y<=z)
          mi=y;
       if(z<=x && z<=y)
          mi=z;
       if(x>=y && x>=z)
          ma=x;
       if(y>=x && y>=z)
          ma=y;
       if(z>=x && z>=y)
          ma=z;
       if(ma==x)
         {
             if(mi==y)
             piv=z;
             else
             piv=y;
         }
         else
        if(ma==y)
           {
               if(mi==x)
                 piv=z;
                 else
                 piv=x;
           }
           else
           {
               if(mi==x)
                 piv=y;
                 else
                 piv=x;
           }
      while(i<=j)
      {
       while(as[i]<piv)
          i++;
       while(as[j]>piv)
          j--;
        if(i<=j)
        {
           aux=as[i];
           as[i]=as[j];
           as[j]=aux;
           aux=a1[i];
           a1[i]=a1[j];
           a1[j]=aux;
           aux=a2[i];
           a2[i]=a2[j];
           a2[j]=aux;
           i++;
           j--;
         }
      }
    if(stanga<j)
       qs(stanga,j);
    if(i<dreapta)
       qs(i,dreapta);
    }
main()
{
    long n,a[101];
    long i,j,k,s,nr=0,p1,p2;
    p1=p2=-1;
    ifstream f("loto.in");
    ofstream g("loto.out");
    f>>n>>s;
    for(i=1;i<=n;i++)
      f>>a[i];
    for(i=1;i<=n;i++)
       for(j=i;j<=n;j++)
          for(k=j;k<=n;k++)
             {
                 nr++;
                 as[nr]=a[i]+a[j]+a[k];
                 a1[nr]=a[i];
                 a2[nr]=a[j];
             }
    qs(1,nr);
    i=1;
    j=nr;
    while(i<=j)
      {
         if(as[i]+as[j]==s)
            {
                p1=i;
                p2=j;
                i=j+1;
            }
            else
         if(as[i]+as[j]>s && i<=j)
            {
                while(as[i]+as[j]>s && i<=j)
                   j--;
                if(as[i]+as[j]==s)
                   {
                       p1=i;
                       p2=j;
                       i=j+1;
                   }
                i++;
                j++;

            }
            else
            i++;
      }
    if(p1!=-1 && p2!=-1)
       g<<a1[p1]<<" "<<a2[p1]<<"  "<<as[p1]-a1[p1]-a2[p1]<<"  "<<a1[p2]<<"  "<<a2[p2]<<"  "<<as[p2]-a1[p2]-a2[p2];
       else
       g<<p1;
    f.close();
    g.close();
    return 0;
}