Pagini recente » Cod sursa (job #622355) | Cod sursa (job #2887085) | Cod sursa (job #611242) | Cod sursa (job #1559178) | Cod sursa (job #51845)
Cod sursa(job #51845)
// 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, cd, i;
long max = 0;
freopen( "loto.in", "rt", stdin );
scanf( "%d %ld", &n, &suma );
for( i=1; i<=n; i++ ) { scanf( "%ld", &N[i] ); if( N[i] > max ) max = N[i]; }
fclose( stdin );
MergeS( 1, n );
freopen( "loto.out", "wt", stdout );
if( max*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;
}