Cod sursa(job #2548763)
Utilizator | Data | 17 februarie 2020 00:20:57 | |
---|---|---|---|
Problema | Loto | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 5.1 kb |
#include <bits/stdc++.h>
#define NMAX 105
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");
int i,j,k,n,st,dr,mij,cnt,ok,cnt2,s1,s2,s;
int u[NMAX*NMAX*NMAX],v[NMAX],w[NMAX*NMAX],rasp[6];
int main()
{
fin>>n>>s;
for(i=1;i<=n;i++)
{
fin>>v[i];
}
sort(v+1,v+n+1);
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
{
for(k=j;k<=n;k++)
{
u[++cnt]=v[i]+v[j]+v[k];
}
}
}
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
{
w[++cnt2]=v[i]+v[j];
}
}
sort(u+1,u+cnt+1);
sort(w+1,w+cnt2+1);
for(i=1;i<=cnt;i++)
{
st=1;
dr=cnt;
ok=0;
while(st<=dr)
{
mij=(st+dr)/2;
if(u[mij]+u[i]>s)dr=mij-1;
else if(u[mij]+u[i]<s)st=mij+1;
else
{
ok=1;
s1=u[mij];
s2=u[i];
break;
}
}
if(ok==1)
{
break;
}
}
if(ok==1)
{
for(i=1;i<=cnt2;i++)
{
st=1;
dr=n;
ok=0;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[mij]+w[i]>s1)dr=mij-1;
else if(v[mij]+w[i]<s1)st=mij+1;
else
{
ok=1;
s1-=v[mij];
rasp[0]=v[mij];
break;
}
}
if(ok==1)break;
}
if(ok==1)
{
for(i=1;i<=n;i++)
{
st=1;
dr=n;
ok=0;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[mij]+v[i]>s1)dr=mij-1;
else if(v[mij]+v[i]<s1)st=mij+1;
else
{
ok=1;
rasp[1]=v[mij];
rasp[2]=v[i];
break;
}
}
if(ok==1)break;
}
if(ok==1)
{
for(i=1;i<=n;i++)
{
st=1;
dr=n;
ok=0;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[mij]+v[i]>s1)dr=mij-1;
else if(v[mij]+v[i]<s1)st=mij+1;
else
{
ok=1;
rasp[1]=v[mij];
rasp[2]=v[i];
break;
}
}
if(ok==1)break;
}
if(ok==1)
{
for(i=1;i<=cnt2;i++)
{
st=1;
dr=n;
ok=0;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[mij]+w[i]>s2)dr=mij-1;
else if(v[mij]+w[i]<s2)st=mij+1;
else
{
ok=1;
s2-=v[mij];
rasp[3]=v[mij];
break;
}
}
if(ok==1)break;
}
if(ok==1)
{
for(i=1;i<=n;i++)
{
st=1;
dr=n;
ok=0;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[mij]+v[i]>s2)dr=mij-1;
else if(v[mij]+v[i]<s2)st=mij+1;
else
{
ok=1;
rasp[4]=v[mij];
rasp[5]=v[i];
break;
}
}
if(ok==1)break;
}
if(ok==1)
{
for(i=0;i<6;i++)
fout<<rasp[i]<<" ";
}
else fout<<-1;
}
else fout<<-1;
}
else fout<<-1;
}
else fout<<-1;
}
else fout<<-1;
}
else fout<<-1;
}