Cod sursa(job #168978)

Utilizator ovy2906Popescu Ovidiu ovy2906 Data 31 martie 2008 22:14:11
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
 #include<stdio.h>  
   #include<stdlib.h>  
    #define NMAX 101  
      
    int n;  
    int S, v[NMAX], trei[NMAX * NMAX * NMAX];  
   int i,j,k,st=1,dr;  
     
   void pivot(int s,int d,int &m)  
 {  
    int ps=0,pd=1,aux;  
   while(s<d)  
   {if(trei[s]>=trei[d]) {aux=trei[s]; trei[s]=trei[d]; trei[d]=aux;  
                 aux=ps; ps=pd; pd=aux;} s+=ps; d-=pd;}  
  m=s;}  
     
     
     
  int Q_Sort(int s,int d)  
   { int m;  
    if(s<d) {pivot(s,d,m);  
         Q_Sort(s,m-1);  
        Q_Sort(m+1,d);} }  
    
     
  int scout(int val)  
   {  
     for(i=1; i<=n; i++)  
     for(j=1; j<=n; j++)  
    for(k=1; k<=n; k++)  
    
    if(v[i] + v[j] + v[k] == val)  
                 { printf("%d %d %d ",v[i],v[j],v[k]);  
               return 0; }  
     
   return -1;}  
    
     
   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(k=1; k<=n; k++) trei[++dr] = v[i] + v[j]+ v[k];  
     
     Q_Sort(1,dr);  
     
     while(n)  
     {  
     
     for(; trei[st] + trei[dr] > S && st<dr; dr--);  
    
     
      if( trei[st] + trei[dr] == S)  
      { scout(trei[st]); scout(trei[dr]); printf("\n"); return 0;}  
    
       if(st==dr) break;  
    
   for(; trei[st] + trei[dr] < S && st<dr; st++);  
   
     }  
     
     printf("-1\n");  
     
    return 0; }