Cod sursa(job #212474)
Utilizator | Data | 5 octombrie 2008 17:05:18 | |
---|---|---|---|
Problema | Loto | Scor | 95 |
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;
}
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;
}
continue;
}
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;
}
continue;
}
}
return 0;
}