Cod sursa(job #288180)

Utilizator pedobearBacauanu Vlad pedobear Data 25 martie 2009 16:58:52
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

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

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);
    
    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;
        }
        
    if (x!=scomb[sol]) printf ("-1");
    else {
         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]);
        }
    
    return 0;
}