Cod sursa(job #2876513)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 23 martie 2022 12:01:54
Problema Loto Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>
#define MAXN 100

using namespace std;

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

int n, s, arr[MAXN], sol[6] = {0};
void citire() {
    fin >> n >> s;
    for (int i = 0; i < n; i++)
        fin >> arr[i];
}

bool back(int i, int sum) {
    if (i == 6)
        return sum == s;

    //se estimeaza o valoare
    int maxi = s / (6 - i);
    int poz = upper_bound(arr, arr + n, maxi) - arr;
    while (arr[poz] > maxi)
        poz--;

    for (int j = 0; j <= poz; j++) {
        sol[i] = arr[j];
        sum += sol[i];
        bool res = back(i + 1, sum);
        if (res)
            return true;
        sum -= sol[i];
    }

    return false;
}

int main() {
    citire();
    sort(arr, arr + n);
    if (back(0, 0))
        for (int i = 0; i < 6; i++)
            fout << sol[i] << ' ';
    return 0;
}