Cod sursa(job #771256)

Utilizator veleanduAlex Velea veleandu Data 25 iulie 2012 12:42:50
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

    #define pb push_back
    #define mod 666017
    #define maxn 101

    typedef struct { long val, E[5]; } my_type;
    vector <my_type> T;
    my_type new_el;

    long n,i,j,l,o;
    long s,sum;
    long P[mod+5];

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

    bool my_type_sort ( my_type a, my_type b )
    {
        return a.val<b.val;
    }
int main()
{
    in>>n>>sum;
    for ( i=1; i<=n; i++ )
        in>>P[i];

    /*for ( i=1; i<=n; i++ )
        for ( j=i; j<=n; j++ )
            for ( l=j; l<=n; l++ )
            {
                new_el.val=P[i]+P[j]+P[l];
                new_el.E[1]=i;
                new_el.E[2]=j;
                new_el.E[3]=l;
                T[ new_el.val%mod ].pb ( new_el );
            }
    for ( i=1; i<=n; i++ )
        for ( j=i; j<=n; j++ )
            for ( l=j; l<=n; l++ )
            {
                s=P[i]+P[j]+P[l];
                s=sum-s;
                // cautam s in hash
                for ( o=0; o<T[s%mod].size(); o++ )
                    if ( T[s%mod][o].val == s)
                    {
                        // gasit!
                        out<<P[i]<<" "<<P[j]<<" "<<P[l]<<" "<<P[ T[s%mod][o].E[1] ]<<" "<<P[ T[s%mod][o].E[2] ]<<" "<<P[ T[s%mod][o].E[3] ]<<"\n";
                        return 0;
                    }
            }*/
    for ( i=1; i<=n; i++ )
        for ( j=i; j<=n; j++ )
            for ( l=j; l<=n; l++ )
            {
                new_el.val=P[i]+P[j]+P[l];
                new_el.E[1]=i;
                new_el.E[2]=j;
                new_el.E[3]=l;
                T.pb ( new_el );
            }
    i=0;
    j=T.size()-1;
    while ( i<j )
    {
        while ( ( T[i].val+T[j].val > sum ) && ( i<j) )
            j--;
        if ( ( T[i].val + T[j].val ) == sum )
        {

            out<<P[ T[i].E[1] ]<<" "<<P[ T[i].E[2] ]<<" "<<P[ T[i].E[3] ]<<" ";
            out<<P[ T[j].E[1] ]<<" "<<P[ T[j].E[2] ]<<" "<<P[ T[j].E[3] ]<<"\n";
            return 0;
        }
        i++;
    }
    out<<"-1";
    return 0;
}