Cod sursa(job #304686)

Utilizator cosserBula Ionut cosser Data 15 aprilie 2009 01:39:41
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<iostream>
#include<fstream>

using namespace std;

#define ATR 100003

struct sir
       {
            int x,y,z,sum;
       };

int nulomuto(sir a[ATR],int s, int d)
{
  int i,j; sir t66;
  int piv=a[s].sum;
  i=s-1;
  j=d+1;

  while(i<j)
        {
            do
             j--;
                while(a[j].sum>piv);
            do
             i++;
                while(a[i].sum<piv);
        if(i<j)
            {
               t66=a[i];
               a[i]=a[j];
               a[j]=t66;
            }
          else
            return j;
        }
}



void quix(sir a[ATR],int s, int d)
{
    int m;
    if (s<d)
        {
            m=nulomuto(a,s,d);
            quix(a,s,m);
            quix(a,m+1,d);
        }
}

int main()
{
ifstream f ("loto.in");
ofstream o ("loto.out");

long n,i,j,k,S,a[101],p=1,kk=0,l;
sir b[ATR];
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++)
          {
              b[++kk].sum=a[i]+a[j]+a[k];
              b[kk].x=a[i];
              b[kk].y=a[j];
              b[kk].z=a[k];
          }
/*
for(i=1;i<=kk && p==1;i++)
    for(j=1;j<=kk && p==1;j++)
        if(b[i].sum+b[j].sum==S)
            o<<b[i].x<<" "<<b[i].y<<" "<<b[i].z<<" "<<b[j].x<<" "<<b[j].y<<" "<<b[j].z,p=0;
*/
quix(b,1,kk);

i=1;
j=kk;
while(i<j)
    {
        l=S-b[i].sum;
        while(b[j].sum>l)
                        j--;
        if(b[j].sum == l)
             {

                 o<<b[i].x<<" "<<b[i].y<<" "<<b[i].z<<" "<<b[j].x<<" "<<b[j].y<<" "<<b[j].z;
                return 0;
             }
        i++;
    }

    o<<"-1";





return 0;}