Cod sursa(job #1865557)

Utilizator Coroian_DavidCoroian David Coroian_David Data 1 februarie 2017 20:16:33
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <cstdio>

using namespace std;

FILE *f, *g;

int n, s;

int v[101];

int lst[1050001];
int urm[1000001];
int val[1000001];

int nr;

int HASH = (1 << 20) - 1;

int h(int x)
{
    return (x & HASH);
}

void readFile()
{
    f = fopen("loto.in", "r");

    fscanf(f, "%d%d", &n, &s);

    int i;
    for(i = 1; i <= n; i ++)
    {
        fscanf(f, "%d", &v[i]);
    }

    fclose(f);
}

void printFile(int a, int b, int c, int rst)
{
    int i, j, k;
    int ok = 1, found;
    for(i = 1; i <= n && ok; i ++)
    {
        for(j = 1; j <= n && ok; j ++)
        {
            for(k = 1; k <= n && ok; k ++)
            {
                if(v[i] + v[j] + v[k] == rst)
                    found = 1;

                if(found == 1)
                {
                    ok = 0;

                    g = fopen("loto.out", "w");

                    fprintf(g, "%d %d %d %d %d %d\n", v[a], v[b], v[c], v[i], v[j], v[k]);

                    fclose(g);
                }
            }
        }
    }
}

void add(int a, int b)
{
    int p = lst[a], nrul;

    while(p != 0)
    {
        if(val[p] == b)
        {
            return;
        }

        p = urm[p];
    }


    val[++ nr] = b;

    urm[nr] = lst[a];

    lst[a] = nr;
}

bool caut(int a, int b)
{
    int p = lst[a], nrul;

    while(p != 0)
    {
        if(val[p] == b)
        {
            return 1;
        }

        p = urm[p];
    }

    return 0;
}

void getHash()
{
    int i, j, k, s;

    for(i = 1; i <= n; i ++)
    {
        for(j = 1; j <= n; j ++)
        {
            for(k = 1; k <= n; k ++)
            {
                s = v[i] + v[j] + v[k];

               // printf("%d %d\n", h(s), s);

                add(h(s), s);
            }
        }
    }
}

void getRez()
{
    int i, j, k;
    int ok = 1, sum, found;
    for(i = 1; i <= n && ok; i ++)
    {
        for(j = 1; j <= n && ok; j ++)
        {
            for(k = 1; k <= n && ok; k ++)
            {
                sum = s - v[i] - v[j] - v[k];

               // printf("%d %d\n", sum, h(sum));

                if(sum > 0)
                    found = caut(h(sum), sum);

                if(found == 1)
                {
                    ok = 0;

                   // printf("**********************+++++++++++++++++++++%d\n", sum);

                    printFile(i, j, k, sum);
                }
            }
        }
    }

    if(ok == 1)
    {
        g = fopen("loto.out", "w");

        while(1);

        fprintf(g, "-1\n");

        fclose(g);
    }
}

void solve()
{
    getHash();

    getRez();
}

int main()
{
    readFile();

    solve();

    return 0;
}