Cod sursa(job #1867984)

Utilizator mihai.alphamihai craciun mihai.alpha Data 4 februarie 2017 14:45:50
Problema Loto Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

#define In "loto.in"
#define Out "loto.out"
#define UI unsigned int

FILE *fin, *fout;
const int MAX = 100;

struct punct  {
    bool tr;
    int a;
    int e[4];
};

int n, s, v[MAX + 1];

class HASH  {
    private:
    static const int L = 1 << 14 - 1;
    std::vector <punct> v[L + 1];

    public:
    inline void insert(int el, int a1, int a2, int a3)  {
        UI key = el & L;
        punct q;
        q.e[1] = a1, q.e[2] = a2, q.e[3] = a3;
        q.a = el;
        q.tr = 1;
        v[key].push_back(q);
    }
    inline void erase(int el)  {
        UI key = el & L, i;
        for(i = (UI)0;i < v[key].size();i++)  {
            if(v[key][i].a == el)  {
                break;
            }
        }
        if(i < v[key].size())  {
            punct aux = v[key].back();
            v[key][i] = aux;
            v[key].pop_back();
        }
    }
    inline punct find(int el)  {
        punct mama;
        mama.tr = false;
        UI key = el & L, i;
        for(i = (UI)0;i < v[key].size();i++)  {
            if(v[key][i].a == el)  {
                mama = v[key][i];
                mama.tr = true;
                return mama;
            }
        }
        return mama;
    }

};

HASH h;

int main()  {
    fin = fopen(In, "r");
    fout = fopen(Out, "w");

    fscanf(fin, "%d%d", &n, &s);
    for(UI i = 0;i < n;i++)
        fscanf(fin, "%d", &v[i]);
    std::sort(v, v + n);

    for(UI i = 0;i < n;i++)
        for(UI j = i;j < n;j++)
            for(UI k = j;k < n;k++)  {
                h.insert(v[i] + v[j] + v[k], v[i], v[j], v[k]);
            }

    for(UI i = 0;i < n;i++)
        for(UI k = i;k < n;k++)
            for(UI j = k;j < n;j++)  {
                    if(s - v[i] - v[j] - v[k] > 0)  {
                        punct uu = h.find(s - v[i] - v[j] - v[k]);
                        if(uu.tr == true)  {
                            fprintf(fout, "%d %d %d %d %d %d\n", v[i], v[j], v[k], uu.e[1], uu.e[2], uu.e[3]);
                            return 0;
                        }
                }
            }
    fprintf(fout, "-1");
    fclose(fin);
    fclose(fout);
    return 0;
}