Cod sursa(job #379414)

Utilizator alexandru92alexandru alexandru92 Data 1 ianuarie 2010 18:11:55
Problema Loto Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 1, 2010, 5:35 PM
 */
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>
#define pb push_back

/*
 *
 */
using namespace std;
struct vertex
{
    int s, a, b, c;
}x;
inline ostream& operator<<( ostream& out, vertex x )
{
    out<<x.a<<' '<<x.b<<' '<<x.c;
    return out;
}
vector< int > coin;
vector< vertex > v;
int main()
{int n, S, i, j, k, left, right, middle, key;
    ifstream in("loto.in");
    in>>n>>S;
    copy( istream_iterator<int>(in), istream_iterator<int>(), back_inserter(coin) );
    sort( coin.begin(), coin.end() ); //sort
    for( i=0; i < n; ++i )  //generate all the sums
        for( j=0; j < n; ++j )
            for( k=0; k < n; ++k )
            {
                x.s=coin[i]+coin[j]+coin[k];
                x.a=coin[i]; x.b=coin[j]; x.c=coin[k];
                if( S == 2*x.s ) //we have found a result
                {
                    ofstream out("loto.out");
                    out<<x<<' '<<x;
                    return 0;
                }
                if( x.s < S )
                 v.pb(x);
            }
    if( v.empty() )
    {
        ofstream out("loto.out");
        out<<"-1";
        return 0;
    }
    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;
            if( S == key+v[middle].s )
            {
                ofstream out("loto.out");
                out<<v[i]<<' '<<v[middle];
                return 0;
            }
            if( S < key+v[middle].s )
                right=middle;
            else left=middle+1;
        }
    }
    ofstream out("loto.out");
    out<<"-1";
    return 0;
}