Cod sursa(job #1089040)

Utilizator 0051David Sera 0051 Data 21 ianuarie 2014 09:49:55
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

#define MAX 102

int a[MAX];
int b[MAX*MAX*MAX];
int c[6];

int n,s;
int t;

bool cautare(int s1)
{
    int st=1,dr=t,m;
    int x=s-s1;

    while(st<=dr)
    {

        m=(st+dr)/2;

        if(b[m]==x)
            return 1;
        if(b[m]>x)
            dr=m-1;
        else
            st=m+1;
    }
    return 0;
}

int main()
{
    int i,j,k;
    fin>>n>>s;
    for(i=1;i<=n;i++)
        fin>>a[i];
    t=0;
   // sort(a+1, a+n+1);
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++){
                b[++t]=a[i]+a[j]+a[k];
            }
    sort(b+1,b+t+1);
    bool ok=0;
    int x1,x2;
    for(i=1;i<=t;i++){

        if(cautare(b[i])){
            x1=b[i];
            x2=s-b[i];
            ok=1;
            break;
        }
    }
    if(!ok)
    {
        fout<<-1<<"\n";
        return 0;
    }
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++){
                if(x1==(a[i]+a[j]+a[k])){
                    c[0]=a[i];
                    c[1]=a[j];
                    c[2]=a[k];
                    goto next;
                }
            }
    next:
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++){
                if(x2==(a[i]+a[j]+a[k])){
                    c[3]=a[i];
                    c[4]=a[j];
                    c[5]=a[k];
                    goto sebi;
                }
            }
    sebi:
    sort(c,c+6);
    for(i=0;i<6;i++)
        fout<<c[i]<<" ";
    return 0;
}