C++ - pytanie - Szkopuł

Question

Hej! Od pewnego czasu zainteresowałem się algorytmiką. Zacząłem rozwiązywać w C++ różne zadania ze SPOJa i systemu Szkopuł (obsługującego OI i OIJ). Teraz zabrałem się za zadanie "Minusy" (https://szkopul.edu.pl/problemset/problem/xB0uOrHG0vxqYqG2Y-Nhjlzu/site/?key=statement). Podczas rozwiązywania przykładowych problemów z zadania, wynik u mnie lokalnie wychodzi poprawny. Podobnie na Ideone - jest tak jak powinno być. Tymczasem po wgraniu do systemu Szkopuł i wybraniu odpowiedniego języka wyskakuje błąd, punktacja 0/100 i informacje, że w każdym z przeprowadzonych testów wynik wynosił 134513184 zamiast wartości oczekiwanej. Czy ktoś, kto miał doczynienia z tym systemem może powiedzieć co może być tego przyczyną. Poniżej zamieszczam mój kod. Wiem, że nie jest idealnie, ale uczę się. Najpierw wczytuję ciąg znaków, następnie zamieniam każde 2 minusy na plus (zgodnie z zadaniem) i na końcu algorytmem gąsienicowym liczę największy ciąg minusów. Nie wiem co jest tu nie tak... Każdy test zwraca dokładnie ten sam wynik...

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie();
    cout.tie();

    int idX=0, start=0, koniec=0, suma_tymczasowa;
    int najwiecej_minusow;
    string wczytywanie;
    vector <int> plusy_minusy;

    cin >> wczytywanie;
    
    while(idX<wczytywanie.length())
    {
        if(wczytywanie[idX]=='+')
        {
            plusy_minusy.push_back(43);
        } else if(wczytywanie[idX]=='-'&&wczytywanie[idX+1]=='-')
        {
            plusy_minusy.push_back(43);
            idX++;
        } else
        {
            plusy_minusy.push_back(45);
        }
        idX++;
    }

    while(koniec<plusy_minusy.size())
    {
        suma_tymczasowa = 0;
        for(int i=start; i<=koniec; i++)
        {
            suma_tymczasowa += plusy_minusy[i];
        }

        if((suma_tymczasowa%43)==0||koniec-start==0)
        {
            if((koniec-start+1)>najwiecej_minusow)
                najwiecej_minusow=koniec-start+1;
            koniec++;
        } else
            start++;
    }

    cout << najwiecej_minusow;

    return 0;
}

 

Answer 1

Problem jest w tym, że algorytm jest błędny. Zobacz sobie taki przypadek:

---+

Twój program zwróci 1, a powinno być 2. Wynika to z tego, że zachłannie zamieniasz 2 pierwsze minusy w plus i w powyższym przypadku otrzymujesz +-+. Czasami może być tak, że bardziej opłaca się zamienić ostatnie 2 minusy na plus, wtedy dostałbyś -++.

Poza tym algorytm jest za wolny, co jest spowodowane pętlą w linii 38. A szkopul zwraca dziwne wyniki, bo zmienna najwiecej_minusow nie jest zainicjalizowana.