Cod sursa(job #304679)

Utilizator cosserBula Ionut cosser Data 15 aprilie 2009 01:02:55
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<iostream>
#include<fstream>

using namespace std;

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

int nulomuto(sir a[101],int s, int d)
{
  int i,j,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].sum;
               a[i].sum=a[j].sum;
               a[j].sum=t66;
            }
          else
            return j;
        }
}



void quix(sir a[101],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[101];
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 && p==1)
    {
        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,p=0;
        i++;
    }

return 0;}