Cod sursa(job #379432)

Utilizator alexandru92alexandru alexandru92 Data 1 ianuarie 2010 19:47:35
Problema Loto Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 1, 2010, 7:35 PM
 */
#include <vector>
#include <fstream>
#include <algorithm>


/*
 *
 */
using namespace std;
struct vertex
{
    int s, a, b, c;
}x;
inline bool operator<( vertex A, vertex B )
{
    return A.s < B.s;
}
vector< vertex > v;
int main()
{int number[110];
int n, S, i, j, k, left, right, middle, key, sum;
    ifstream in("loto.in");
    ofstream out("loto.out");
    in>>n>>S;
    for( i=0; i < n; ++i )
        in>>number[i];
    for( i=0; i < n; ++i )
        for( j=0; j < n; ++j )
            for( k=0; k < n; ++k )
            {
                x.s=number[i]+number[j]+number[k];
                if( x.s > S )
                    break;
                if( S == 2*x.s )
                {
                    out<<number[i]<<' '<<number[j]<<' '<<number[k]<<' '<<number[i]<<' '<<number[j]<<' '<<number[k];
                    return 0;
                }
                x.a=number[i]; x.b=number[j]; x.c=number[k];
                v.push_back(x);
            }
   if( v.empty() )
   {
       out<<"-1";
       return 0;
   }
   sort( v.begin(), v.end() );
   for( i=0, n=v.size(); i < n; ++i )
   {
       key=v[i].s;
       left=0; right=n-1;
       while( left < right )
       {
           middle=left+(right-left)/2;
           sum=key+v[middle].s;
           if( sum == S )
           {
               out<<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;
       }
   }
   out<<"-1";
   return 0;
}