Cod sursa(job #288205)

Utilizator pedobearBacauanu Vlad pedobear Data 25 martie 2009 17:13:38
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

int v[105],scomb[1000010],aux[1000010];
int n,S,i,j,h,cnt,x,st,dr,mid,sol;

void msort (int x,int y)
{
     if (x>=y) return;
     mid=(x+y)/2;
     msort (x,mid);
     msort (mid+1,y);
     
     int i=x, k=x-1, j=mid+1;
     while (i<=mid && j<=y){
           if (scomb[i]>=scomb[j]) aux[++k]=scomb[j++];
           else aux[++k]=scomb[i++];
           }
     if (i>mid) while (j<=y) aux[++k]=scomb[j++];
     else while (i<=mid) aux[++k]=scomb[i++];
     for (i=x;i<=y;i++) scomb[i]=aux[i];
}

void cbin ()
{
     for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            for (h=1;h<=n;h++){
                x=S-v[i]-v[j]-v[h];
                st=1;
                dr=cnt;
                while (st<=dr){
                      mid=(st+dr)/2;
                      if (x>=scomb[mid]) {
                                         st=mid+1;
                                         sol=mid;
                                         }
                      else dr=mid-1;
                      }
                if (x==scomb[sol]) break;
                }
            if (x==scomb[sol]) break;
            }
        if (x==scomb[sol]) break;
        }
}

void print ()
{
    printf ("%d %d %d ",v[i],v[j],v[h]);
    
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            for (h=1;h<=n;h++){
                x=v[i]+v[j]+v[h];
                if (x==scomb[sol]) break;
                }
            if (x==scomb[sol]) break;
            }
        if (x==scomb[sol]) break;
        }
        
    printf ("%d %d %d",v[i],v[j],v[h]);
}

int main ()
{
    freopen ("loto.in","r",stdin);
    freopen ("loto.out","w",stdout);
    
    scanf ("%d %d",&n,&S);
    for (i=1;i<=n;i++) scanf ("%d",&v[i]);
    
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            for (h=1;h<=n;h++)
                scomb[++cnt]=v[i]+v[j]+v[h];
                
    sort(scomb+1,scomb+cnt+1);
    cbin();
    
    if (x!=scomb[sol]) printf ("-1");
    else print();
    
    return 0;
}