Missioni - territoriali 2008

Aiuto
1 
#include <fstream>
#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int main()
{
    ifstream in("input.txt");
    int n; in >> n;
    // vettore che tiene le soluzioni nel formato <numero missioni, fine ultima missione
    vector<pair<int, int>> soluzioni;
    int a, b; in >> a >> b;
    soluzioni.push_back(make_pair(0, 0));
    soluzioni.push_back(make_pair(1, soluzioni[0].second + a));
    
    for (int i = 2; i < n + 1; ++i) {
        in >> a >> b;
        auto j = soluzioni.size();
        auto sol2 = soluzioni[j - 2];
        //cout << sol2.first << " " << sol2.second << "\n";
        auto sol1 = soluzioni[j - 1];
        //cout << sol1.first << " " << sol1.second << "\n\n";
        
        // aggiunge la nuova missione solo se possibile entro la scadenza
        if (sol1.second + a <= b) {
            sol1.second = sol1.second + a;
            ++sol1.first;
        }   
        if (sol2.second + a <= b) { // come sopra
            sol2.second = sol2.second + a;
            ++sol2.first;
        }

        //cout << sol1.first << " " << sol2.first << " " << soluzioni[j - 1].first << "\n";
        // controlla quale soluzione è la migliore contando l'ultima missione poi la aggiunge, ma solo se la nuova soluzione è migliore della precedente
        if (sol1.first > sol2.first && sol1.first > soluzioni[j - 1].first) {
            //cout << "sol 1\n";
            soluzioni.push_back(sol1);
        }
        else if (sol1.first == sol2.first) { // se le soluzioni sono uguali è favorita quella che finisce prima
                if (soluzioni[j - 1].second > sol1.second || sol2.second < soluzioni[j - 1].second) {
                //cout << "sol == " << sol1.second << " " << sol2.second << "\n";
                soluzioni.push_back(sol1.second <= sol2.second ? sol1 : sol2);
            }
        }
        else {
            //cout << "sol2\n";
            if (sol2.first > soluzioni[j - 1].first)soluzioni.push_back(sol2);
        }
    }

    //for (auto beg = soluzioni.begin(); beg != soluzioni.end(); ++beg) {
        //cout << beg->first << " " << beg->second << "\n";
    //}

    ofstream out("output.txt");
    out << (*(soluzioni.end() - 1)).first << endl;
    out.close();
}

Ho implementato questa soluzione stile dynamic programming per Missioni ma non passa i test case 6, 7, 8.
Inizialmente credevo di aver individuato il problema in quanto non consideravo il caso in cui ci fossero una serie di missioni con la stessa scadenza ma durata minore una dopo l’altra e ho corretto il programma ma non li passa lo stesso.
Ora sarei sul punto di implementare un’ altra soluzione ma mi piacerebbe capire perchè non funziona questa.

2

Se possibile spiega l’algoritmo che hai usato, in modo che è più facile capire se è sbagliato :stuck_out_tongue:

Inoltre nei testcase che fallisce che esito dà? time limit superato? wrong answer?

3

Giusto scusa, l’algoritmo consiste nel creare un vettore di soluzioni dove l’ultima posizione contiene la soluzione finale.
Le prime due posizioni sono per 0 e 1 missione, e ogni entry del vettore contiene il numero di missioni che è possibile svolgere e il giorno in cui termina l’ultima missione.
Per ogni iterazione leggo una nuova missione e vedo se è possibile inserirla considerando la scadenza e la fine delle ultime due precedenti, poi aggiungo la soluzione migliore, ma solo se è diversa dall’ultima inserita per evitare che se ne accodino più di una uguale.

Nei test case dà wrong answer.