Cod sursa(job #136569)

Utilizator igorPirnau Igor igor Data 15 februarie 2008 17:47:50
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<fstream.h>
using namespace std;

#define smax 1000100
#define nmax 200

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

int s[smax], a[nmax], n, i, nr, j, k, sp, sbin, st, dr, mij, sol[7], ok;
long S; 
void suma(int x,int &v1,int &v2,int &v3)
{
    int i, j, k;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            for(k=1; k<=n; k++)
                if(a[i]+a[j]+a[k]==x) 
                {
                    v1=i; v2=j; v3=k;
                    return;
                }
}
    
int main()
{
    f>>n>>S;
    for(i=1; i<=n; i++) f>>a[i];
    f.close();

    nr=0;
    for(i=1; i<=n; i++) 
        for(j=1; j<=n; j++) 
            for(k=1; k<=n; k++) 
                s[++nr]=a[i]+a[j]+a[k];

    sort( s+1, s+nr+1 );
    
    ok=0;
    for(i=1; i<=nr && !ok ; i++){
        sp=s[i];
        st=1; dr=nr;
        while( st <= dr){
            mij=(st+dr)/2;
            if( sp + s[mij] > S ) dr=mij;
                else if( sp + s[mij] < S ) st=mij+1;
                        else{ ok=1; sbin=s[mij]; st=dr+1; }
        }
    }

    if(ok){
        suma(sp, sol[1], sol[2], sol[3]);
        suma(sbin, sol[4], sol[5], sol[6]);
        sort(sol+1, sol+6+1);
        for(i=1; i<=6; i++) g<<sol[i]<<' ';
    }
        else g<<"-1";

    g.close();
    return 0;
}