Cod sursa(job #3041541)

Utilizator Shaan_StefanShaan Stefan Shaan_Stefan Data 31 martie 2023 17:42:23
Problema Loto Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.45 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];
                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;
}