Cod sursa(job #1424359)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 24 aprilie 2015 09:09:58
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

int n,s ,h  ,ans1,ans2;
int x[105],v[1000005];

bool caut_bin(int st,int dr,int val){
    int m ;
    while( st <= dr ){
        m = (st+dr) >> 1;
        if( v[m] == val ) return 1;
        if( v[m] > val ) dr = m - 1;
        else             st = m + 1;
    }
    return 0;

}

int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);

    scanf("%d %d",&n,&s);

    for(int i=1;i<=n;++i)
        scanf("%d ",x+i);

    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    for(int k=1;k<=n;++k)
        v[++h] = x[i] + x[j] + x[k];

    sort(v+1,v+h+1);

    for(int i=1;i<= n*n*n; ++i){
        if( caut_bin(i,n*n*n,s-v[i]) )
        {ans1= v[i] , ans2=s-v[i] ; break;}
    }

    if( !ans1 ){
        printf("-1");
        return 0;
    }

    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    for(int k=1;k<=n;++k)
        if( x[i] + x[j] + x[k] == ans1 )
        {
            printf("%d %d %d ",x[i],x[j],x[k]);
            i=j=k=n*n*n+6;
        }
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    for(int k=1;k<=n;++k)
        if( x[i] + x[j] + x[k] == ans2 )
        {
            printf("%d %d %d",x[i],x[j],x[k]);
            i=j=k=n*n*n+6;
        }



    return 0;
}