Cod sursa(job #2760184)

Utilizator ioana2008vIoana Velniceru ioana2008v Data 23 iunie 2021 15:49:24
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fi ("loto.in");
ofstream fo ("loto.out");

const int P = 666019;
const int N_MAX = 1000001;
int valori[N_MAX], liste[P + 1], urmator[N_MAX], nr_valori, n, s, numere[101];

bool exista(int el){
    int cheie_hash = el % P;
    int x = liste[cheie_hash];
    while (x != -1){
        if (valori[x] == el){
            return true;
        }
        x = urmator[x];
    }
    return false;
}

void adaugare(int el){
    if (exista(el)){
        return;
    }
    int cheie_hash = el % P;
    valori[nr_valori] = el;
    urmator[nr_valori] = liste[cheie_hash];
    liste[cheie_hash] = nr_valori;
    nr_valori++;
}

void stergere(int el){
    int cheie_hash = el % P;
    int x = liste[cheie_hash];
    while (x != -1 && valori[x] != el){
        x = urmator[x];
    }
    if (x != -1){
        valori[x] = valori[liste[cheie_hash]];
        liste[cheie_hash] = urmator[liste[cheie_hash]];
    }
}

void gasire_suma(int suma){
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            for (int k = 0; k < n; k++){
                if (numere[i] + numere[j] + numere[k] == suma){
                    fo << numere[i] << " " << numere[j] << " " << numere[k];
                    return;
                }
            }
        }
    }
}

int main()
{
    for (int i = 0; i < P; i++)
    {
        liste[i] = -1;
    }
    fi >> n >> s;
    for (int i = 0; i < n; i++){
        fi >> numere[i];
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            for (int k = 0; k < n; k++){
                adaugare(numere[i] + numere[j] + numere[k]);
            }
        }
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            for (int k = 0; k < n; k++){
                if (numere[i] + numere[j] + numere[k] <= s && exista(s - (numere[i] + numere[j] + numere[k]))){
                    fo << numere[i] << " " << numere[j] << " " << numere[k] << " ";
                    gasire_suma(s - (numere[i] + numere[j] + numere[k]));
                    fi.close();
                    fo.close();
                    return 0;
                }
            }
        }
    }
    fo << "-1";
    fi.close();
    fo.close();
    return 0;
}