Cod sursa(job #371508)

Utilizator SiriusSirius Sirius Data 5 decembrie 2009 16:28:50
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<cstdio> 
#include<algorithm> 
using namespace std; 
const int N=1<<20; 
int i,q,j,k,poqi,poqj,n,ss,a[101],v[7],s[N]; 
int cautb() 
{ 
    
int j,pas=N; 
    
for(j=0;pas;pas>>=1) 
        
if(j+pas<=q) 
            
if(s[j+pas]+s[i]<=ss) 
                
j+=pas; 
    
if(s[j]+s[i]!=ss) return 0; 
    
return j; 
} 
void cautsol() 
{ 
    
int i,j,k; 
    
for(i=1;i<=n;i++) 
        
for(j=i;j<=n;j++) 
            
for(k=j;k<=n;k++) 
            
{ 
                
if(a[i]+a[j]+a[k]==s[poqj] && v[1]==0) 
                
{ 
                    
v[1]=a[i]; 
                    
v[2]=a[j]; 
                    
v[3]=a[k]; 
                
} 
                
if(a[i]+a[j]+a[k]==s[poqi] && v[4]==0) 
                
{ 
                    
v[4]=a[i]; 
                   
v[5]=a[j]; 
                    
v[6]=a[k]; 
                
} 
            
} 
} 
int main() 
{ 
    
freopen("loto.in","r",stdin); 
    
freopen("loto.out","w",stdout); 
    
scanf("%d%d",&n,&ss); 
    
for(i=1;i<=n;i++) 
        
scanf("%d",&a[i]); 
    
for(i=1;i<=n;i++) 
        
for(j=i;j<=n;j++) 
            
for(k=j;k<=n;k++) 
                
s[++q]=a[i]+a[j]+a[k]; 
    
sort(s+1,s+q+1); 
    
for(i=1;i<=q;i++) 
    
{ 
        
poqj=cautb(); 
        
if(poqj!=0) 
        
{ 
            
poqi=i; 
            
break; 
        
} 
    
} 
    
if(poqj==0) printf("-1"); 
    
else
    
{ 
cautsol();         
sort(v+1,v+7); 

for(i=1;i<=6;i++)             
printf("%d ",v[i]); 
    
} 

return 0; 
}