Cod sursa(job #354417)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 7 octombrie 2009 23:03:43
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include<cstdio>
#include<cstdlib>

#define MAXN 100

int n, s;
int v[MAXN];
int rez[6];
int nrSume, sume[MAXN * MAXN * MAXN];

void citeste()
{
    FILE* fi = fopen("loto.in", "r");
    fscanf(fi, "%d%d", &n, &s);
    for(int i = 0; i < n; ++i)
        fscanf(fi, "%d", &v[i]);
    fclose(fi);
}

void scrie()
{
    FILE* fo = fopen("loto.out", "w");
    //FILE* fo = stdout;
    if(rez[5] == 0) fprintf(fo, "-1");
    else for(int i = 0; i < 6; ++i) fprintf(fo, "%d ", rez[i]);
    fprintf(fo, "\n");
    fclose(fo);
}

void genereazaSume()
{
    int i, j, k;
    for(i = 0; i < n; ++i)
        for(j = 0; j < n; ++j)
            for(k = 0; k < n; ++k)
                sume[nrSume++] = v[i] + v[j] + v[k];
}

int fcmp(const void* a, const void* b)
{
    return (*((int*)a)) - (*((int*)b));
}

void sorteazaSume()
{
    qsort(sume, nrSume, sizeof(int), fcmp);
    //int i;
    //for(i = 0; i < nrSume; ++i) printf("%d ", sume[i]);
    //printf("\n");
}

void gasesteNumere(int suma, int* vPoz)
{
    int i, j, k;
    for(i = 0; i < n; ++i)
    {
        for(j = 0; j < n; ++j)
        {
            for(k = 0; k < n; ++k)
            {
                if(v[i] + v[j] + v[k] == suma)
                {
                    vPoz[0] = v[i];
                    vPoz[1] = v[j];
                    vPoz[2] = v[k];
                    return;
                }
            }
        }
    }
}

int cautaSumaComplementara(int sumaCautata, int li, int ls)
{
    for(int i = li; i <= ls; ++i) if(sumaCautata == sume[i]) return 1;
    return 0;
}

void rezolva()
{
    genereazaSume();
    sorteazaSume();

    int i;
    for(i = 0; i < nrSume; ++i)
    {
        if(cautaSumaComplementara(s - sume[i], i, nrSume - 1))
        {
            gasesteNumere(sume[i], rez);
            gasesteNumere(s - sume[i], rez + 3);
            return;
        }
    }
}

int main()
{
    citeste();
    rezolva();
    scrie();
    return 0;
}