SPOJ - MWP2_1E - Szpieg

Witam
mam problem z następującym zadaniem: https://pl.spoj.com/problems/MWP2_1E/. Sędzia nie akceptuje mojego zadania ("Błędna odpowiedź). Czy ktoś mógłby mi podpowiedzieć, gdzie jest błąd? Poniżej mój kod:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void displayWords (vector <string> vectorToSort)
{
    for (int i=0; i<vectorToSort.size(); i++)
    {
        cout << vectorToSort[i] << endl;
    }
}

int main()
{
    vector<string> vectorToSort;
    string wordToSort;
    while (getline(cin, wordToSort))
    {
        vectorToSort.push_back(wordToSort);
        sort(vectorToSort.begin(), vectorToSort.end());
        cout << endl;
        displayWords(vectorToSort);
        cout << endl;
    }

    return 0;
}

Próbowałaś uruchomić dla danych wejściowych podanych na stronie? TIP: sprawdź ile elementów jest na wejściu a ile elementów wypisujesz na ekran.

lubie_programowac napisał(a):

Próbowałaś uruchomić dla danych wejściowych podanych na stronie? TIP: sprawdź ile elementów jest na wejściu a ile elementów wypisujesz na ekran.

Próbowałam uruchomić dla danych wejściowych. Ze względu na to, że nie ma z góry podanej ilości wyrazów mój program na bieżąco sortuje wyrazy i wyrzuca je na ekran (po każdym wpisanym nowym wyrazie). Po wpisaniu wszystkich danych wejściowych na stronie, otrzymuję takie same dane wyjściowe jak na stronie.

Po wpisaniu wszystkich danych wejściowych na stronie, otrzymuję takie same dane wyjściowe jak na stronie. Czy aby na pewno otrzymujesz dokładnie takie same dane wyjściowe jak podane w przykładzie? Przekieruj wejście oraz wyjście z oraz do pliku tekstowego przy pomocy < oraz >, sprawdź czy dane wyjściowe są dokładnie takie same jak w przykładzie.

lubie_programowac napisał(a):

Po wpisaniu wszystkich danych wejściowych na stronie, otrzymuję takie same dane wyjściowe jak na stronie. Czy aby na pewno otrzymujesz dokładnie takie same dane wyjściowe jak podane w przykładzie? Przekieruj wejście oraz wyjście z oraz do pliku tekstowego przy pomocy < oraz >, sprawdź czy dane wyjściowe są dokładnie takie same jak w przykładzie.

Dodałam przekierowanie danych wyjściowych do pliku tekstowego i wg. mnie dane są takie same jak dane wyjściowe w przykładzie. Nadal nie widzę błędu :(

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <cstdlib>

using namespace std;

void saveAsFile (vector <string> vectorToSort)
{
    fstream file;
    file.open("text.txt", ios::out);

    if(file.good() == true)
    {
        for (int i=0; i<vectorToSort.size(); i++)
        {
            file << vectorToSort[i] << endl;
        }
        file.close();
    }
    else
    {
        cout << "Nie mozna otworzyc pliku!" << endl;
        system("pause");
    }
}

void displayWords (vector <string> vectorToSort)
{
    for (int i=0; i<vectorToSort.size(); i++)
    {
        cout << vectorToSort[i] << endl;
    }
}

int main()
{
    vector<string> vectorToSort;
    string wordToSort;
    while (getline(cin, wordToSort))
    {
        vectorToSort.push_back(wordToSort);
        sort(vectorToSort.begin(), vectorToSort.end());
        system("cls");
        displayWords(vectorToSort);
        saveAsFile(vectorToSort);
    }

    return 0;
}

Skompilowałem kod Twojego programu z pierwszej wypowiedzi przy pomocy g++ main.cpp Następnie utworzyłem plik tekstowy z zawartością która znajduje się w przykładzie, zapisałem go jako input.txt do folderu gdzie został wygenerowany plik wykonywalny. Następnie wywołałem ./a.out <input.txt >output.txt To jest bardzo prosta sprawdzarka zadań ze SPOJA. W pliku output.txt jest inna zawartość niż ta w przykładzie ze strony. Dzięki temu możesz ~debugować program. Twój kod z pierwszego wpisu jest prawie dobrze napisany, wygeneruj output. Myślę że od razu rzuci Ci się w oczy co jest z nim nie tak.

Kolego/Koleżanko, niepotrzebnie dopisuje nowe linie, do tego za dużo razy wywołujesz sort, zupełnie niepotrzebnie.

Tu masz referencyjne rozwiązanie:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
using namespace std;

int main() {
	vector<string> lines;
	copy(istream_iterator<string>(cin), istream_iterator<string>(), back_inserter(lines));
	sort(lines.begin(), lines.end());
	copy(lines.begin(), lines.end(), ostream_iterator<string>(cout, "\n"));
	return 0;
}

Patrzę na kod i widzę groch z kapustą.
Oddziel wyraźnie fragmenty kodu (tak zrobił @nalik, każda linia robi jedno z tych zadań i nic więcej):

• wczytanie, wszystkich linii/wyrazów
• posortowanie
• wyświetlenie

Wszystkie te części nie mają prawa się pokrywać, jak to jest u ciebie i co jest źródłem błędów.

Poza tym, łaskawie uruchom u siebie ten kod i zobacz jaki jest wynik dla jakiś danych wejściowych. Sama zobaczysz, że to nie działa i sędzia SPOJ nie będzie potrzebny do stwierdzenia, że coś jest źle.

@lubie_programowac: dziękuję za podpowiedź. Rzeczywiście sposób z zapisywaniem wyniku do pliku tekstowego to super sprawa! Przyda się na przyszłość

@nalik: dziękuję za rozwiązanie, jednak Twój kod nie do końca jest dla mnie jasny (jestem na początku przygody z programowaniem a to mój pierwszy program z użyciem wektorów). Mimo wszystko pomogło mi to rozwiązać mój problem.

@MarekR22: Wybacz za "groch z kapustą" ale jak wcześniej wspomniałam dopiero się uczę :)

Ostatecznie udało się rozwiązać problem a SPOJ zaakceptował moje rozwiązanie. Dziękuję za pomoc!

Poprawiłam swój kod, ale spoj wyrzuca: "Przekroczony limit czasu"... Co tu jest nie tak?

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void wyswietlWyrazy (vector <string> wektorWyrazow) {
    for (int i = 0; i < wektorWyrazow.size(); i++) {
        cout << wektorWyrazow[i] << endl;

    }

}

int main() {
    vector < string > wpisanyWyraz;
    string wyraz = " ";


    do  {
        getline(cin, wyraz);
        wpisanyWyraz.push_back(wyraz);//dodaje do wektora nowe dane
        sort(wpisanyWyraz.begin(), wpisanyWyraz.end());

    } while (!wyraz.empty() );

    wyswietlWyrazy(wpisanyWyraz);

    return 0;
}

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
using namespace std;

int main()
{
  istream_iterator<string> iis(cin),iie;
  vector<string> all;
  back_insert_iterator<vector<string>> biv(all);
  copy(iis,iie,biv);
  sort(all.begin(),all.end());
  ostream_iterator<string> ois(cout,"\n");
  copy(all.begin(),all.end(),ois);
  return 0;
}

Magda Pietrzykowska napisał(a):

Poprawiłam swój kod, ale spoj wyrzuca: "Przekroczony limit czasu"... Co tu jest nie tak?

Sortujesz po każdym wczytaniu kolejnego wyrazu marnujesz czas na wielokrotne sortowanie.

Mówiąc technicznie złożoność czasowa twojego algorytmu to O(n^2).
Wczytanie danych daje O(n), do tego std::sort w wersji optymistycznej jest O(n), dlatego sumarycznie, złożoność czasowa algorytmu jest kwadratowa.
Mówiąc bardziej po ludzku, czas wykonania twojego algorytmu jest proporcjonalna do kwadratu rozmiaru danych.

Wystarczy osobno wczytywać liczby i osobno sortować. Wtedy złożoność algorytmu wyniesie O(n long n) (pesymistyczna złożoność czasowa std::sort).