Cod sursa(job #965020)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 22 iunie 2013 22:41:38
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

#define Nmax 128

struct suma
{
    int a;
    int b;
    int c;
    int val;

} sum[10000000];

int N, S, P;
int a[Nmax];

ifstream f("loto.in");
ofstream g("loto.out");

void gen()
{
    for ( int i = 1; i <= N; i++ )
        for ( int j = i; j <= N; j++ )
            for ( int k = j; k <= N; k++ )
                sum[ ++P ]= { a[i], a[j], a[k], a[i]+a[j]+a[k] };
}

void QSort( suma x[], int l, int r )
{
    int i = l, j = r, p = x[l + rand()%(r-l+1)].val;

    do
    {
        while ( x[i].val < p )
            i++;

        while ( x[j].val > p )
            j--;

        if ( i <= j )
        {
            swap( x[i], x[j] );

            i++;
            j--;
        }

    }while( i < j );

    if ( i < r )
        QSort( x, i, r );

    if ( l < j )
        QSort( x, l, j );
}

int cautare( int l, int r, int key )
{
    while( l < r )
    {
        int m = ( l + r ) / 2;

        if ( sum[m].val == key )
            return m;

        if ( sum[m].val < key )
            r = m - 1;
        else
            l = m + 1;
    }

    return -1;
}

void citire()
{
    f >> N >> S;

    for ( int i = 1; i <= N; i++ )
        f >> a[i];

    f.close();
}

void rezolva()
{
    for ( int i = 1; i <= P; i++ )
    {
        int poz = cautare( 1, P, S-sum[i].val );

        if ( poz > 0 && poz != i )
        {
            g << sum[i].a << " " << sum[i].b << " " << sum[i].c << " ";
            g << sum[poz].a << " " << sum[poz].b << " " << sum[poz].c << " ";
            g << endl;

            g.close();

            return;
        }
    }

    g << "-1";
    g.close();
}

int main()
{
    srand( time( NULL ) );

    citire();
    sort(a+1,a+N+1);
    gen();
    QSort( sum, 1, P );
    rezolva();

    return 0;
}