Cod sursa(job #3184092)

Utilizator andreea1313Andreea andreea1313 Data 14 decembrie 2023 12:25:24
Problema Semne Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

bool solve(int idx, int currentSum, int targetSum, const vector<int>& ai, vector<char>& signs) {
    if (idx == ai.size()) {
        return currentSum == targetSum;
    }

    // Try adding the current element
    signs[idx] = '+';
    if (solve(idx + 1, currentSum + ai[idx], targetSum, ai, signs)) {
        return true;
    }

    // Try subtracting the current element
    signs[idx] = '-';
    if (solve(idx + 1, currentSum - ai[idx], targetSum, ai, signs)) {
        return true;
    }

    return false;
}

int main() {
    ifstream infile("semne.in");
    ofstream outfile("semne.out.");

    if (!infile || !outfile) {
        cerr << "Error opening files." << endl;
        return 1;
    }

    int N, S;
    infile >> N >> S;

    vector<int> ai(N);
    for (int i = 0; i < N; ++i) {
        infile >> ai[i];
    }

    vector<char> signs(N);
    if (solve(0, 0, S, ai, signs)) {
        // Output the result to the file
        for (int i = 0; i < N; ++i) {
            outfile << signs[i];
        }
        outfile << endl;
    }
    else {
        outfile << "Impossible" << endl;
    }

    infile.close();
    outfile.close();

    return 0;
}