Cod sursa(job #51849)

Utilizator Bluedrop_demonPandia Gheorghe Bluedrop_demon Data 16 aprilie 2007 22:36:55
Problema Loto Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
// Problema loto
// Backtracking... so help me god!!!

#include <stdio.h>
#define MAX       102
#define MAXIM     100000001

long N[MAX];
long suma;

void InterC( int st, int m, int dr )
{
     long a[MAX], b[MAX];
     int i, j, k;
     for( i=st; i<=m; i++ ) a[i] = N[i];
     a[m+1] = -MAXIM;
     for( j=m+1; j<=dr; j++ ) b[j] = N[j];
     b[dr+1] = -MAXIM;
     
     i = st;
     j = m+1;
     
     for( k =st; k<=dr; k++ )
          if( a[i] > b[j] ) N[k] = a[i++];
              else N[k] = b[j++];
}

int MergeS( int st, int dr )
{
    if( st == dr ) return 0;
    int m = ( st + dr ) /2;
    MergeS( st, m );
    MergeS( m+1, dr );
    InterC( st, m, dr );
    return 0;
}

int main()
{
    int n, i;

    freopen( "loto.in", "rt", stdin );
             scanf( "%d %ld", &n, &suma );
             for( i=1; i<=n; i++ ) scanf( "%ld", &N[i] );
    fclose( stdin );
    
    MergeS( 1, n );
    
    freopen( "loto.out", "wt", stdout );
    if( N[1]*6 < suma ) 
        {
              printf( "-1\n" );
              fclose( stdout );
              return 0;
        }
    else
    {
    int s1, s2, s3, s4, s5, s6;
    
    for( s1=1; s1<=n; s1++ )
         for( s2=s1; s2<=n; s2++ )
              for( s3=s2; s3 <=n; s3++ )
                   for( s4=s3; s4<=n; s4++ )
                        for( s5=s4; s5<=n; s5++ )
                             for( s6=s5; s6<=n; s6++ )
                                  if( N[s1]+N[s2]+N[s3]+N[s4]+N[s5]+N[s6] == suma ) 
                                      {
                                         printf( "%ld %ld %ld %ld %ld %ld\n",
                                                 N[s1], N[s2], N[s3], N[s4], N[s5], N[s6] );
                                         fclose( stdout );
                                         return 0; 
                                      }
    }

    printf( "-1\n" );    
    fclose( stdout );
    return 0;
}