Cod sursa(job #212460)

Utilizator alexeiIacob Radu alexei Data 5 octombrie 2008 16:42:10
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.91 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;
}

void destroy(const int s1,const int s2,const int N)
{
     int aux;
     int i,j,k;
     bool local,use1=false,use2=false,stupid=false;
     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];local=false;                   
                                if( aux==s1 && use1==false )
                                {
                                    printf("%d %d %d",i,j,k);
                                    use1=true;local=true;
                                    if( stupid==false )
                                    {
                                        stupid=true;printf(" ");
                                    }
                                }
                                if( aux==s2 && use2==false && local==false )
                                {
                                    printf("%d %d %d",i,j,k);
                                    use2=true;
                                    if( stupid==false )
                                    {
                                        stupid=true;printf(" ");
                                    }
                                }
                                if( use1==true && use2==true )
                                return;
                       }
              }
     }
}

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 sol1=0,sol2=0,aux;
    for(i=1; i<M; ++i)
    {
             aux=find(S-SOL[i]);
             if( aux )
             {
                 sol1=SOL[i];sol2=SOL[aux];
             }
    }
       
    if( sol1 )
    destroy(sol1,sol2,N);
    else
    printf("%d\n",-1);
    
    return 0;
}