Cod sursa(job #1294195)

Utilizator jordasIordache Andrei Alexandru jordas Data 17 decembrie 2014 02:34:05
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <cstdlib>

using namespace std;

 ifstream x ("loto.in");
 ofstream y ("loto.out");

 int n,s;
 int v[101];
 int bilet[6];

 void quicksort(int a[], int l, int r)
 {
     int i,j;
     int p,pivot;
     int aux;

     p=rand()%(r-l+1)+l;

     aux=a[p];
     a[p]=a[l];
     a[l]=aux;

     pivot=a[l];
     p=l;
     i=l+1;

     for(j=l;j<=r;j++)
        if(pivot>a[j])
        {
            aux=a[j];
            a[j]=a[i];
            a[i]=aux;
            i++;
        }

     aux=a[p];
     a[p]=a[i-1];
     a[i-1]=aux;

     if(l<i-2)
        quicksort(a,l,i-2);
     if(i<r)
        quicksort(a,i,r);
 }

int main()
{
    int i,j;

    x>>n>>s;

    for(i=1;i<=n;i++)
       x>>v[i];

    quicksort(v,1,n);
/*
    for(i=1;i<=n;i++)
       y<<v[i]<<' ';
*/

//BKT

    int sum;
    bool flag=false;

    for(i=0;i<=5;i++)
       bilet[i]=n;

    while(bilet[0]>-1)
    {
        bilet[5]--;
        for(i=5;i>0;i--)
           if(bilet[i]==0)
           {
               bilet[i-1]--;
               bilet[i]=n;
           }

        sum=0;

        for(i=0;i<=5;i++)
           sum+=v[bilet[i]];

        if(sum==s)
        {
            for(i=0;i<=5;i++)
               y<<v[bilet[i]]<<' ';
            y<<'\n';
            flag=true;
            break;
        }
    }

    if(flag==false)
       y<<"-1\n";


    return 0;
}