Cod sursa(job #1073062)

Utilizator PetreFlorinaFMI Petre Florina PetreFlorina Data 5 ianuarie 2014 17:03:50
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

struct sum {
    long SumT; // suma pe care o am
    int x, y, z; // numerele care alcatuiesc suma
} v[1000001];

int a[101];

ifstream f("loto.in");
ofstream g("loto.out");


void quicksort(sum v[], long left, long right)
 {
     long i = left, j = right;
      float pivot=v[(left+right)/2].SumT;

         while (i<=j)
          {
              while (v[i].SumT<pivot)
                i++;
                while (v[j].SumT>pivot)
                 j--;

               if (i<=j)
                {
                    swap(v[i].SumT, v [j].SumT);
                    swap(v[i].x, v [j].x);
                    swap(v[i].y, v [j].y);
                    swap(v[i].z, v [j].z);
                    i++;j--;
                }
          }
          if (left<j)
              quicksort(v, left,j);
              if (right>i)
              quicksort(v, i,right);
 }

bool cmp(const sum &a1, const sum &b1)
{
    return(a1.SumT < b1.SumT);
}

int main()
{
   int S, i, j, k, n, p, dr, mid, st, s1;
    bool ok;
    p=0;

    f >> n >> S ;

    for ( i=1; i<=n; i++ )
        f >> a[i];

    for ( i=1; i<=n; i++)
     for ( j=1; j<=n; j++ )
      for ( k=1; k<=n; k++ )
           {
             ++p;
             s = a[i] + a[j] + a[k];
             v[p].SumT = s;
             v[p].x = a[i];
             v[p].y = a[j];
             v[p].z = a[k];
           } // se calculeaza sumele existente


 //   quicksort(v, 1, p); // se ordoneaza crescator sumele care trebuiesc
    sort(v+1, v+p+1, cmp);
    ok = 1;
    s1 = 0;

    for(i=1;i<=n && ok;i++)
        for(j=i;j<=n && ok;j++)
            for(k=j;k<=n && ok;k++)
             {
               s1 = S - a[i] - a[j] - a[k];

               st=1;
               dr=p;

                while(st <= dr && ok)
                {

                    mid = (st + dr) / 2;

                    if(v[mid].SumT > s1)
                        dr = mid-1;
                    else

                    if(v[mid].SumT < s1)
                        st = mid + 1;
                    else
                       ok=0; // daca gasim suma cautata, ok = 0

                }

                if(!ok)
                {
                    g<<a[i]<<" "<<a[j]<<" "<<a[k]<<" "<<v[mid].x<<" "<<v[mid].y<<" "<<v[mid].z<<"\n";

                }
            }
            if (ok)
            g << "-1";

         return 0;
}