Cod sursa(job #1189890)
Utilizator | Data | 23 mai 2014 20:18:53 | |
---|---|---|---|
Problema | Loto | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 4.13 kb |
#include<fstream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");
struct nod
{
int val,pasi,backin;
};
const int modulo=1000007;
int n,S,a[105],sol[10];
vector<nod>H[modulo];
int main()
{
int i,indice,j,len,l,p,aux,xl,yl,xr,yr,SL,SK;
bool test=0;
nod k;
fin>>n>>S;
xl=yl=xr=yr=SL=SK=-1;
for (i=1;i<=n;i++)
{
fin>>a[i];
k.val=a[i];
k.pasi=1;
k.backin=a[i];
H[a[i]%modulo].push_back(k);
}
sort(a+1,a+n+1);
indice=1;
while (indice<=2)
{
for (i=0;i<=modulo-1;i++)
{
len=H[i].size();
for (j=0;j<len;j++)
if (H[i][j].pasi==indice)
for (l=1;l<=n;l++)
{
aux=(H[i][j].val+a[l])%modulo;
test=0;
for (p=0;p<H[aux].size() && !test;p++)
if (H[aux][p].pasi==indice+1 && H[aux][p].val==H[i][j].val+a[l])
{
p=H[aux].size()+1;
test=1;
}
if (!test)
{
k.pasi=indice+1;
k.val=H[i][j].val+a[l];
k.backin=a[l];
H[aux].push_back(k);
p=H[aux].size()+1;
}
}
}
indice++;
}
for (i=0;i<=modulo-1;i++)
{
len=H[i].size();
for (j=0;j<len;j++)
if (H[i][j].pasi==3 && H[i][j].val<=S)
{
aux=S-H[i][j].val;
p=aux%modulo;
for (l=0;l<H[p].size();l++)
if (H[p][l].pasi==3 && H[p][l].val==aux)
{
xl=i;
yl=j;
xr=p;
yr=l;
SL=H[i][j].val;
SK=H[p][l].val;
l=H[p].size()+1;
p=len+1;
i=modulo;
}
}
}
if (SL!=-1)
{
aux=3;test=1;
while (aux>0 && test)
{
test=0;
len=H[SL%modulo].size();
for (j=0;j<len;j++)
if (H[SL%modulo][j].pasi==aux && H[SL%modulo][j].val==SL)
{
test=1;
sol[++sol[0]]=H[SL%modulo][j].backin;
SL-=sol[sol[0]];
j=len+1;
}
aux--;
}
aux=3;test=1;
while (aux>0 && test)
{
test=0;
len=H[SK%modulo].size();
for (j=0;j<len;j++)
if (H[SK%modulo][j].pasi==aux && H[SK%modulo][j].val==SK)
{
test=1;
sol[++sol[0]]=H[SK%modulo][j].backin;
SK-=sol[sol[0]];
j=len+1;
}
aux--;
}
sort(sol+1,sol+sol[0]+1);
for (i=1;i<=sol[0];i++) fout<<sol[i]<<" ";
}
else fout<<"-1";
fout<<"\n";
return 0;
}