Cod sursa(job #3367887)

Utilizator Barbu_DariusBarbu Darius Barbu_Darius Data 11 octombrie 2026 18:19:31
Problema Loto Scor 100
Compilator c-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <stdio.h>

#define MAX_N 100
#define MAX_SUME 176900

int n, s;
int numere[MAX_N];
int sume[MAX_SUME];
int comp_i[MAX_SUME];
int comp_j[MAX_SUME];
int comp_k[MAX_SUME];
int nr_sume;

int cautareBinara(int valoare_cautata) {
    int stg, drg, mij, ans;
    stg = 0;
    drg = nr_sume - 1;
    ans = -1;
    while (stg <= drg) {
        mij = (stg + drg) / 2;
        if (sume[mij] == valoare_cautata) {
            ans = mij;
            drg = mij - 1;
        } else if (sume[mij] < valoare_cautata) {
            stg = mij + 1;
        } else {
            drg = mij - 1;
        }
    }
    return ans;
}

int main() {
    FILE *fin, *fout;
    int i, j, k, rest, pozitie, gasit;
    int pas, temp_s, temp_i, temp_j, temp_k;
    
    fin = fopen("loto.in", "r");
    
    fscanf(fin, "%d %d", &n, &s);
    for (i = 0; i < n; i++) {
        fscanf(fin, "%d", &numere[i]);
    }
    
    fclose(fin);
    
    nr_sume = 0;
    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
        for (k = j; k < n; k++) {
            sume[nr_sume] = numere[i] + numere[j] + numere[k];
            comp_i[nr_sume] = numere[i];
            comp_j[nr_sume] = numere[j];
            comp_k[nr_sume] = numere[k];
            nr_sume++;
            }
        }
    }
    
    for (pas = nr_sume / 2; pas > 0; pas /= 2) {
        for (i = pas; i < nr_sume; i++) {
            temp_s = sume[i];
            temp_i = comp_i[i];
            temp_j = comp_j[i];
            temp_k = comp_k[i];
            for (j = i; j >= pas && sume[j - pas] > temp_s; j -= pas) {
            sume[j] = sume[j - pas];
            comp_i[j] = comp_i[j - pas];
            comp_j[j] = comp_j[j - pas];
            comp_k[j] = comp_k[j - pas];
            }
            sume[j] = temp_s;
            comp_i[j] = temp_i;
            comp_j[j] = temp_j;
            comp_k[j] = temp_k;
        }
    }
    
    fout = fopen("loto.out", "w");
    gasit = 0;
    
    for (i = 0; i < nr_sume && !gasit; i++) {
        rest = s - sume[i];
        pozitie = cautareBinara(rest);
        if (pozitie != -1) {
        fprintf(fout, "%d %d %d %d %d %d\n", 
        comp_i[i], comp_j[i], comp_k[i],
        comp_i[pozitie], comp_j[pozitie], comp_k[pozitie]);
         gasit = 1;
        }
    }
    
    if (!gasit) {
        fprintf(fout, "-1\n");
    }
    
    fclose(fout);
    return 0;
}