Cod sursa(job #3041585)
Utilizator | Data | 31 martie 2023 18:50:01 | |
---|---|---|---|
Problema | Loto | Scor | 5 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 3.83 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");
int n, s, mr[101][101][101], a[101], i, j, k, st, dr, mij, psx, psy, n1, n2;
struct coord
{
int x, y, z;
}p1, p2;
bool ok;
int main()
{
fin>>n>>s;
for(i=1; i<=n; i++)
fin>>a[i];
sort(a+1, a+n+1);
for(i=1; i<=n; i++)
{
for(j=i; j<=n; j++)
{
for(k=j; k<=n; k++)
{
mr[i][j][k]=a[i]+a[j]+a[k];
//fout<<mr[i][j][k]<<' ';
}
//fout<<'\n';
}
//fout<<'\n';
}
ok=1;
for(i=1; i<=n*ok; i++)
{
for(j=i; j<=n*ok; j++)
{
for(k=j; k<=n*ok; k++)
{
n1=mr[i][j][k];
n2=s-mr[i][j][k];
if(n2<=mr[n][n][n] && n1<s)
{
st=i, dr=n;
while(st<=dr)
{
mij=(st+dr)/2;
if(mr[mij][n][n]==n2)
{
p1.x=i;
p1.y=j;
p1.z=k;
p2.x=mij;
p2.y=n;
p2.z=n;
ok=0;
break;
}
else
{
if(mr[mij][n][n]<n2)
st=mij+1;
else
dr=mij-1;
}
}
if(ok==1)
{
psx=st;
st=psx, dr=n;
while(st<=dr)
{
if(mr[psx][mij][n]==n2)
{
p1.x=i;
p1.y=j;
p1.z=k;
p2.x=psx;
p2.y=mij;
p2.z=n;
ok=0;
break;
}
else
{
if(mr[psx][mij][n]<n2)
st=mij+1;
else
dr=mij-1;
}
}
}
if(ok==1)
{
psy=st;
st=psy, dr=n;
while(st<=dr)
{
if(mr[psx][psy][mij]==n2)
{
p1.x=i;
p1.y=j;
p1.z=k;
p2.x=psx;
p2.y=psy;
p2.z=mij;
ok=0;
break;
}
else
{
if(mr[psx][psy][mij]<n2)
st=mij+1;
else
dr=mij-1;
}
}
}
}
}
}
}
if(ok==1)
fout<<"-1";
else
{
fout<<a[p1.x]<<' '<<a[p1.y]<<' '<<a[p1.z]<<' ';
fout<<a[p2.x]<<' '<<a[p2.y]<<' '<<a[p2.z]<<' ';
}
return 0;
}