Cod sursa(job #1698695)

Utilizator panteapaulPantea Paul panteapaul Data 5 mai 2016 01:02:56
Problema Loto Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>

using namespace std;

int n, s;
deque<int> nrs;
ifstream in("loto.in");
ofstream out("loto.out");

void rec(deque<int> stak, int sum, bool &sol) {
    int i, j, back;

    if (stak.empty()) back = 0;
    else back = stak.back();

    if (stak.size() == 5) {
        for (i=back; i<n && sum + nrs[i] < s; i++) {

        }

        if (i<n && sum + nrs[i] == s) {
            sol = true;

            for (j=0; j<5; j++) {
                out<<nrs[stak[j]]<<" ";
            }
            out<<nrs[i];
        }


        return;
    }

    for (i=back; i<n && sum + nrs[i] < s; i++) {
        stak.push_back(i);
        rec(stak, sum+nrs[i], sol);

        if (sol) {
            return;
        }
        stak.pop_back();
    }
}

int main()
{
    bool sol = false;
    int i, x;
    in>>n>>s;

    for (i=0; i<n; i++) {
        in>>x;
        nrs.push_back(x);
    }

    sort(nrs.begin(), nrs.end());

    deque<int> stak;
    rec(stak, 0, sol);

    if (!sol) {
        out<<-1;
    }

    in.close();
    out.close();
    return 0;
}