Cod sursa(job #379437)

Utilizator alexandru92alexandru alexandru92 Data 1 ianuarie 2010 19:55:42
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 1, 2010, 7:35 PM
 */
#include <cstdio>
#include <algorithm>
#define Nmax 1000010

/*
 *
 */
using namespace std;
struct vertex
{
    int s, a, b, c;
}x;
inline bool operator<( vertex A, vertex B )
{
    return A.s < B.s;
}
int main()
{vertex v[Nmax];
 int number[110];
 int n, S, i, j, k, left, right, middle, key, sum, nr=0;
    freopen("loto.in", "rt", stdin );
    freopen( "loto.out", "wt", stdout );
    scanf("%d%d",&n, &S );
    for( i=0; i < n; ++i )
        scanf("%d", number+i );
    for( i=0; i < n; ++i )
        for( j=0; j < n; ++j )
            for( k=0; k < n; ++k )
            {
                v[nr].s=number[i]+number[j]+number[k];
                v[nr].a=number[i]; v[nr].b=number[j]; v[nr].c=number[k];
                ++nr;
            }
   sort( v, v+nr );
   for( i=0; i < nr; ++i )
   {
       key=v[i].s;
       left=0; right=nr-1;
       while( left < right )
       {
           middle=left+(right-left)/2;
           sum=key+v[middle].s;
           if( sum == S )
           {
               printf("%d %d %d %d %d %d" , v[i].a, v[i].b, v[i].c, v[middle].a, v[middle].b, v[middle].c );
               return 0;
           }
           if( S < sum )
               right=middle-1;
           else left=middle+1;
       }
   }
   printf("-1");
   return 0;
}