Cod sursa(job #2784251)

Utilizator andreimocianAndrei Mocian andreimocian Data 16 octombrie 2021 10:17:48
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");

struct indici
{
    int i1, i2, i3;
} ind;

const int p = 370003;
int n, s, sum, complement;
int a[105], poz[10];
bool ok = false;
vector<int> h[370005];

void citire()
{
    fin >> n >> s;
    for (int i = 1; i <= n; i++)
    {
        fin >> a[i];
    }
}

void adauga(int x)
{
    int r = x % p;
    if (h[r].size() == 0 || h[r][0] != x)
    {
        h[r].push_back(x);
    }
}

int cautare(int x)
{
    int r = x % p;
    for (int i = 0; i < h[r].size(); i++)
    {
        if (h[r][i] == x)
        {
            return 1;
        }
    }
    return -1;
}

void cautare_suma(int complement)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            for (int k = j; k <= n; k++)
            {
                if (a[i] + a[j] + a[k] == complement)
                {
                    ind.i1 = i;
                    ind.i2 = j;
                    ind.i3 = k;
                }
            }
        }
    }
}

void solve()
{
    int i, j, k;
    for (i = 1; i <= n; i++)
    {
        for (j = i; j <= n; j++)
        {
            for (k = j; k <= n; k++)
            {
                adauga(a[i] + a[j] + a[k]);
            }
        }
    }

    for (i = 1; i <= n; i++)
    {
        for (j = i; j <= n; j++)
        {
            for (k = j; k <= n; k++)
            {
                sum = a[i] + a[j] + a[k];
                complement = s - sum;
                if (complement > 0)
                {
                    if (cautare(complement) == 1)
                    {
                        poz[1] = i;
                        poz[2] = j;
                        poz[3] = k;
                        cautare_suma(complement);
                        ok = true;
                        poz[4] = ind.i1;
                        poz[5] = ind.i2;
                        poz[6] = ind.i3;
                        break;
                    }
                }
            }
        }
    }
}

int main()
{
    citire();
    solve();
    if (ok)
    {
        sort(poz + 1, poz + 7);
        for (int i = 1; i <= 6; i++)
        {
            fout << a[poz[i]] << " ";
        }
    }
    else
    {
        fout << -1;
    }
    return 0;
}