1 testcase sbagliato in brackets2

Aiuto
1

Salve a tutti, sto cercando l’errore da troppo, se qualcuno può darmi una mano grazie mille :slight_smile: . Allego il mio codice e premetto che il testcase in questione è il 35.

#include <fstream>
#include <iostream>
#include <string>
#include <vector>

#define SUMAX 50000

using namespace std;

int N, meta;//meta è definito nel main
vector<int> A;
vector<bool> test;//vettore per distinguere i numeri presi dai non presi
vector<vector<int>> memo;

int solve(int i, bool preso, int somma){
    if (i == N || somma>meta)
    {
        return memo[i][somma] = 0;
    }
    if (somma == meta)
    {
        return somma;
    }

    if (memo[i][somma] != -1)
    {
        return memo[i][somma];
    }
    
    if(solve(i + 1, test[i] = true, somma + A[i]) == meta)return meta;
    if(solve(i + 1, test[i] = false, somma) == meta)return meta;
    else return memo[i][somma] = 0;
}

int main() {
    // uncomment the two following lines if you want to read/write from files
    // ifstream cin("input.txt");
    // ofstream cout("output.txt");
    int tot = 0;
    cin >> N;

    A.resize(N);
    test.resize(N, 0);
    memo.resize(N+1, vector<int>(SUMAX,-1));//memo con N+1 per semplice comodità nella ricorsione

    for (int i = 0; i < N; ++i){
        cin >> A[i];
        tot += A[i];
    }
    meta = tot/2;

    int t = solve(0, 0, 0);//chiamata alla dp
    int bilancio = 0;
    bool flag = 1;

    for (int i = 0; i < N; i++)//ciclo per controllare che l'ordine dei numeri sia valido
    {
        if (test[i] == true)
        {
            bilancio += A[i];
        }
        else{
            bilancio -= A[i];
        }
        if (bilancio < 0)
        {
            flag = 0;
            break;
        }
    }

    if(flag){
        //creazione della stringa in outputs
        string ans;
        for (int i = 0; i < N; i++)
        {
            if (test[i] == true)
            {
                for (int j = 0; j < A[i]; j++)
                {
                    ans.push_back('(');
                }
            }
            else{
                for (int j = 0; j < A[i]; j++)
                {
                    ans.push_back(')');
                }
            }    
        }
        cout << ans << endl;
    }
    else{
        cout << -1 << endl;
    }

    return 0;
}
2

Una prima considerazione: se tot è dispari perché proseguire?
Poi non mi è chiara la logica della solve:
se metto test[i]=false a somma dovrei sottrarre A[i].
Comunque questa parte non mi convince:
if (somma == meta)
{
return somma;
}
Se trovi che la somma degli A[i] presi fino a i vale meta, sei sicuro che questo ti garantisca di aver trovato una soluzione giusta?
Magari no ma lo vai a scoprire fuori dalla solve quando fai il bilancio (troppo tardi).
Facendo nella solve la somma algebrica degli A[i] e controllando che alla fine questa somma faccia 0
il tuo codice (così modificato) ha fatto 100.

1 Mi Piace
3

Grazie dell’aiuto intanto, ho modificato il codice ma continuo ad avere lo stesso problema di prima :sweat_smile: . Ri allego il codice modificato :confused: .

#include <fstream>
#include <iostream>
#include <string>
#include <vector>

#define SUMAX 50000*2

using namespace std;

int N;
vector<int> A;
vector<bool> test;//vettore per distinguere i numeri presi dai non presi
vector<vector<int>> memo;

int solve(int i, bool preso, int somma){
    if (i == N)
    {
        return somma;
    }

    if (memo[i][somma + SUMAX/2] != -100000)
    {
        return memo[i][somma + SUMAX/2];
    }
    
    if(solve(i + 1, test[i] = true, somma + A[i]) == 0){
        return 0;
    }
    if(solve(i + 1, test[i] = false, somma - A[i]) == 0){
        return 0;
    }
    else return memo[i][somma + SUMAX/2] = -1;
}

int main() {
    // uncomment the two following lines if you want to read/write from files
    // ifstream cin("input.txt");
    // ofstream cout("output.txt");
    cin >> N;

    A.resize(N);
    test.resize(N, 0);
    memo.resize(N, vector<int>(SUMAX,-100000));//memo, uso somma+SUMAX/2 sopra perchè somma puo essere <0

    for (int i = 0; i < N; ++i){
        cin >> A[i];
    }

    int t = solve(0, 0, 0);//chiamata alla dp

    if(!t){
        //creazione della stringa in output
        string ans;
        for (int i = 0; i < N; i++)
        {
            if (test[i] == true)
            {
                for (int j = 0; j < A[i]; j++)
                {
                    ans.push_back('(');
                }
            }
            else{
                for (int j = 0; j < A[i]; j++)
                {
                    ans.push_back(')');
                }
            }    
        }
        cout << ans << endl;
    }
    else{
        cout << -1 << endl;
    }

    return 0;
}
4

La solve che avevo modificato è questa:

int solve(int i, bool preso, int somma) {
    if (i == N )
    {
        if(somma==0)
            return memo[i][somma] = 1;
        return memo[i][somma] = 0;
    }
    
    if (memo[i][somma] != -1)
    {
        return memo[i][somma];
    }

    if (solve(i + 1, test[i] = true, somma + A[i]) == 1)return memo[i][somma]=1;
    if (somma - A[i] >= 0)
        if (solve(i + 1, test[i] = false, somma - A[i]) == 1)return memo[i][somma] = 1;
    return memo[i][somma] = 0;
}

Restituisce 1 se è andata bene 0 altrimenti.
Comunque ritoccando di poco la tua seconda versione si fa ugualmente 100/100 eccola:

int solve(int i, bool preso, int somma){
    if (i == N)
    {
        return somma;
    }

    if (memo[i][somma + SUMAX/2] != -100000)
    {
        return memo[i][somma + SUMAX/2];
    }
    
    if(solve(i + 1, test[i] = true, somma + A[i]) == 0){
        return 0;
    }
    if(somma - A[i]>=0){
        if(solve(i + 1, test[i] = false, somma - A[i]) == 0){
            return 0;
        }
    }
   // else
  //      test[i]=false;
    
    return memo[i][somma + SUMAX/2] = -1;
}
1 Mi Piace