Cod sursa(job #379446)

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

/*
 *
 */
using namespace std;
vector< int > v;
int number[110], n;
void output( int s, int s2 )
{bool ok=false, ok2=false;
 int i, j, k, sum;
    ofstream out("loto.out");
    for( i=0; i < n; ++i )
        for( j=0; j < n; ++j )
            for( k=0; k < n; ++k )
            {
                sum=number[i]+number[j]+number[k];
                if( !ok && sum == s )
                  ok=true, out<<number[i]<<' '<<number[j]<<' '<<number[k]<<' ';
                if( !ok2 && sum == s2 )
                    ok2=true, out<<number[i]<<' '<<number[j]<<' '<<number[k]<<' ';
                if( ok && ok2 )
                   return;                
            }
}
int main()
{int S, sum, i, j, k, left, right, middle, key, nr;
    ifstream in("loto.in");
    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 )
            {sum=number[i]+number[j]+number[k];
                if( S == 2*sum )
                {
                    ofstream out("loto.out");
                    out<<number[i]<<' '<<number[j]<<' '<<number[k]<<' '<<number[i]<<' '<<number[j]<<' '<<number[k];
                    return 0;
                }
                if( sum < S )
                    v.pb(sum);
            }
    if( v.empty() )
    {
        ofstream out("loto.out");
        out<<"-1";
        return 0;
    }
    sort( v.begin(), v.end() );
    nr=v.size();
    for( i=0; i < nr ;++i )
    {key=v[i];
        left=0; right=nr-1;
        while( left < right )
        {
            middle=left+(right-left)/2;
            sum=key+v[middle];
            if( S == sum )
            {
                output( key, v[middle] );
                return 0;
            }
            if( S > sum )
                left=middle+1;
            else right=middle-1;
        }
    }
    ofstream out("loto.out");
    out<<"-1";
    return 0;
}