Cod sursa(job #212478)

Utilizator alexeiIacob Radu alexei Data 5 octombrie 2008 17:17:10
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include<stdio.h>
#include<algorithm>
#define NMAX 1000024
#define NMIC 124
using namespace std;
int V[NMIC],SOL[NMAX];

void create_list(const int N,const int S)
{
    int aux;
    int i,j,k;
    for(i=1; i<=N; ++i)
             for(j=i; j<=N; ++j)  
                      for(k=j; k<=N; ++k)
                      {
                               aux=V[i]+V[j]+V[k];
                               if( aux<S )
                               SOL[++SOL[0]]=aux;
                      }
}

int find(const int target)
{
     const int M=SOL[0];
     int inc=1,sf=M;
     int mij;
     while( inc<=sf )
     {
            mij=(inc+sf)>>1;
     
            if( SOL[mij]==target )
            return mij;
            else
            {
                if( SOL[mij]<target )
                inc=mij+1;
                else
                sf=mij-1;
            }
     }
     return 0;
}

int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    
    int N,S;
    scanf("%d%d",&N,&S);
    
    int i,j,k;
    for(i=1; i<=N; ++i)
    scanf("%d",&V[i]);
    
    create_list(N,S);
    
    int M=SOL[0];
    sort(SOL+1,SOL+1+M);
    int aux;
    int sol1=0,sol2=0;
    bool use1=false,use2=false;
    for(i=1; i<=M; ++i)
    {
             aux=find(S-SOL[i]);
             if( aux )
             {
                 sol1=SOL[i];sol2=SOL[aux];
                 break;
             }
    }
    if( !sol1 ){
    printf("%d\n",-1); return 0;
    }
    int a1=0,a2=0,a3=0,a4=0,a5=0,a6=0;
    for(i=1; i<=N; ++i)
             for(j=i; j<=N; ++j)
                        for(k=j; k<=N; ++k)
                        {
                                 aux=V[i]+V[k]+V[j];
                                 
                                 if( aux==sol1 && use1==false )
                                 {
                                     a1=V[i]; a2=V[j]; a3=V[k];
                                     use1=true;
                                     if( use1==true && use2==true ){
                                         printf("%d %d %d %d %d %d\n",a1,a2,a3,a4,a5,a6);
                                         return 0;
                                     }
                                 }
                                 if( aux==sol2 && use2==false )
                                 {
                                     a4=V[i]; a5=V[j]; a6=V[k];
                                     use2=true;
                                     if( use1==true && use2==true ){
                                         printf("%d %d %d %d %d %d\n",a1,a2,a3,a4,a5,a6);
                                         return 0;
                                     }
                                 }
                        }                            
    return 0;
}