Cod sursa(job #322446)

Utilizator freak93Adrian Budau freak93 Data 8 iunie 2009 20:45:19
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<fstream>
#include<cstring>
#define maxn 101

using namespace std;

ifstream f("loto.in");
ofstream g("loto.out");

struct elem
{
    int s,x,y,z;

} a[maxn*maxn*maxn],b[maxn*maxn*maxn];

int i,j,n,s,k,r[maxn],p,x,y,ct[1024],ind[1024];

void rad(elem *a,elem *b,int n,int byte)
{
    memset(ct,0,sizeof(ct));

    int i;

    for(i=1;i<=n;++i)
        ++ct[(a[i].s>>byte)&1023];

    ind[0]=1;

    for(i=1;i<1024;++i)
        ind[i]=ind[i-1]+ct[i-1];

    for(i=1;i<=n;++i)
        b[ind[(a[i].s>>byte)&1023]++]=a[i];

}

void radix(elem *a,int n)
{
    rad(a,b,n,0);
    rad(b,a,n,10);
    rad(a,b,n,20);
}

int main()
{
    f>>n>>s;

    for(i=1;i<=n;++i)
        f>>r[i];

    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            for(k=1;k<=n;++k)
                a[++p].x=r[i],a[p].y=r[j],a[p].z=r[k],a[p].s=r[i]+r[j]+r[k];

    radix(a,n*n*n);

    x=1;
    y=p;

    while(x<=y)
        if(b[x].s+b[y-1].s>=s)
            --y;
        else
            if(b[x].s+b[y].s==s)
            {
                g<<b[x].x<<" "<<b[x].y<<" "<<b[x].z<<" "<<b[y].x<<" "<<b[y].y<<" "<<b[y].z<<"\n";
                f.close();
                g.close();

                return 0;
            }

            else
                ++x;

    g<<"-1\n";

    f.close();

    g.close();

    return 0;
}