AL_01_02 - Kolejka - Przekroczono limit czasu

0

Jak można to zmienić aby nie było tego błędu?
Treść zadania: https://pl.spoj.com/problems/AL_01_02/

#include <bits/stdc++.h>
using namespace std;

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int ile_testow;
char naj_znak;
string ciag;
cin >>ile_testow;
for(int i=1; i<=ile_testow; i++){
cin >>ciag;
naj_znak=ciag[ciag.size()-1];
for(int j=ciag.size()-1; j>=0; j--){
if(naj_znak>ciag[j]){
ciag.erase(j,1);
}
naj_znak=ciag[j];
}
cout <<ciag<<endl;
}
return 0;
}

0

A myślisz, że czemu jest to za wolne? Spróbuj oszacować złożoność czasową swojego rozwiązania - przypuśćmy, że masz na wejściu ciąg długości n (załóżmy też, że odpalasz jedynie jeden test). Jak długo (w najgorszym wypadku) może działać Twoje rozwiązanie?

0
enedil napisał(a):

A myślisz, że czemu jest to za wolne? Spróbuj oszacować złożoność czasową swojego rozwiązania - przypuśćmy, że masz na wejściu ciąg długości n (załóżmy też, że odpalasz jedynie jeden test). Jak długo (w najgorszym wypadku) może działać Twoje rozwiązanie?

Treść mówi, że (t, n<10^6) i (t * n<10^6) oraz, że czas programu nie może wynieść więcej niż 2s.Moim zdaniem ten program ma złożoność O(t*n) (a jeżeli chodzi o jedynie jeden test to to jest O(n))

0
Ash. pl napisał(a):
enedil napisał(a):

A myślisz, że czemu jest to za wolne? Spróbuj oszacować złożoność czasową swojego rozwiązania - przypuśćmy, że masz na wejściu ciąg długości n (załóżmy też, że odpalasz jedynie jeden test). Jak długo (w najgorszym wypadku) może działać Twoje rozwiązanie?

Treść mówi, że (t, n<10^6) i (t * n<10^6) oraz, że czas programu nie może wynieść więcej niż 2s.Moim zdaniem ten program ma złożoność O(t*n) (a jeżeli chodzi o jedynie jeden test to to jest O(n))

No, ale Twoje rozwiązanie nie jest O(n), tylko O(n^2)

0

Z ciekawości zapodałem to zadanie do ChatGpt3.
Wyprodukował coś koślawego charakterystycznego dla początkujących (ale działa poprawnie). A próby nakłonienia go do zrobienie tego ładniej wprowadziły tylko błąd, albo jeszcze bardziej koślawy kod

MarekR22 do ChatGpt3

Rozwiąż następujące zadanie tworząc kod w C++:

W spokojnym na ogół Lesie Przedziałowym wybuchło ostatnio zamieszanie. Było ono spowodowane promocją na bilety do ZOO. Każde zwierzę chciało jak najszybciej kupić bilet, jako że zostało ich już niewiele. Jak wiadomo, w lesie panuje prawo dżungli - wygrywa silniejszy. Kolejka do kasy z biletami nie działa więc na zasadzie FIFO (First In First Out). Jej działanie wyjaśnimy na przykładzie.

Do pustej kolejki wchodzi sobie zając. Lis okazał się być wolniejszy i doszedł trochę później. Ale czemu miałby stanąć za zającem, skoro może go wyrzucić z kolejki i zająć jego miejsce? Pierwsze miejsce zajmuje zatem lis. Następnie dochodzi inny zając i widząc potężnego lisa musi stanąć za nim. Nagle z krzaków wyłania się kolejny zając. Widząc swojego pobratymca zastanawia się czy dałby radę wygonić go z kolejki, ale postanawia nie ryzykować przegranej i staje za nim. W końcu doczłapał się i niedźwiedź. Zające same uciekły z kolejki, a jednym ruchem łapy niedźwiedź wyeliminował i lisa, zajmując pierwsze miejsce. Do kasy dochodziły nowe i nowe zwierzęta zajmując odpowiednie miejsce pozbywając się słabszej konkurencji.

Twoim zadaniem jest wyświetlenie ostatecznej kolejki do kasy z biletami.

Uwaga: Kasa zostaje otwarta dopiero po utworzeniu ostatecznej kolejki, więc żadne zwierzę nie odchodzi od kasy w trakcie formowania się kolejki.
Wejście

W pierwszej linii znajduje się liczba testów t (t<10^6). Każda z następnych t linii zawiera ciąg znaków (a..z, A..Z) oznaczających siłę kolejnych zwierząt ustawiających się w kolejce ('a'<'z', 'a'>'A', początek kolejki jest po lewej stronie). Długość ciągu n nie przekracza 10^6 oraz t*n<10^7.
Wyjście

Dla każdego testu jedna linia opisująca ostateczną kolejność zwierząt.

Przykład
Wejście:
2
klkkn
klKKnNLlNL

Wyjście:
n
nlNL

ChatGpt3

#include <iostream>
#include <stack>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        stack<char> st;
        for (char c : s) {
            while (!st.empty() && c > st.top())
                st.pop();
            st.push(c);
        }
        string result;
        while (!st.empty()) {
            result += st.top();
            st.pop();
        }
        reverse(result.begin(), result.end());
        cout << result << endl;
    }
    return 0;
}

Kod przyjmuje liczbę testów t jako pierwszy argument wejścia. Następnie iteruje przez t testów, dla każdego testu tworzy pusty stos i iteruje przez każdy znak w ciągu wejściowym. Dla każdego znaku, sprawdza czy jest silniejszy niż ostatni element na stosie. Jeśli tak, usuwa ostatni element ze stosu. Gdy wszystkie znaki zostaną przetworzone, tworzy nowy ciąg, który jest odwróceniem zawartości stosu i wypisuje go na ekranie.

MarekR22 do ChatGpt3

podziel kod na mniejsze funkcje. Rozdziel operacje wejścia wyjścia od obliczeń.

ChatGpt3

#include <iostream>
#include <stack>
#include <string>
using namespace std;

stack<char> createQueue(string s);
void printQueue(stack<char> st);

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        auto queue = createQueue(s);
        printQueue(queue);
    }
    return 0;
}

stack<char> createQueue(string s) {
    stack<char> st;
    for (char c : s) {
        while (!st.empty() && c > st.top())
            st.pop();
        st.push(c);
    }
    return st;
}

void printQueue(stack<char> st) {
    string result;
    while (!st.empty()) {
        result += st.top();
        st.pop();
    }
    reverse(result.begin(), result.end());
    cout << result << endl;
}

Kod został podzielony na dwie funkcje: createQueue i printQueue. Funkcja createQueue przyjmuje jako argument ciąg wejściowy i tworzy kolejkę, a następnie zwraca ją jako stos. Funkcja printQueue przyjmuje jako argument stos i wypisuje jego zawartość odwróconą na ekranie.
Funkcja main() zawiera tylko operacje wejścia i wywołanie tych dwóch funkcji, co pozwala na łatwiejsze zrozumienie kodu i utrzymanie czytelności.

MarekR22 do ChatGpt3

użyj std::string zamiast std::stack

ChatGpt3

#include <iostream>
#include <string>
using namespace std;

string createQueue(string s);
void printQueue(string queue);

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        auto queue = createQueue(s);
        printQueue(queue);
    }
    return 0;
}

string createQueue(string s) {
    string queue = "";
    for (char c : s) {
        if (queue.empty() || c > queue.back())
            queue += c;
    }
    return queue;
}

void printQueue(string queue) {
    cout << queue << endl;
}

W tym kodzie, zamiast używać stosu, użyłem ciągu std::string do przechowywania kolejki. Funkcja createQueue nadal iteruje przez każdy znak wejściowy, ale zamiast umieszczać znaki na stosie, dodaje je do ciągu kolejki, jeśli są silniejsze od ostatniego znaku. Funkcja printQueue po prostu wypisuje ciąg kolejki na ekranie. Użycie std::string jest bardziej naturalne i czytelne niż użycie stosu, ponieważ ciąg jest już odpowiednią strukturą danych do przechowywania ciągu znaków.

MarekR22 do ChatGpt3

ostatnia zmiana wprowadziła błąd w createQueue, możesz go poprawić?

ChatGpt3

Tak, błąd polega na tym, że funkcja createQueue zawsze dodaje znak do ciągu kolejki, niezależnie od tego, czy jest silniejszy od ostatniego znaku. Aby poprawić błąd, należy dodać warunek sprawdzający siłę znaku przed jego dodaniem do kolejki.

string createQueue(string s) {
    string queue = "";
    for (char c : s) {
        if (queue.empty() || c > queue.back())
            queue += c;
    }
    return queue;
}

Należy zmienić na

string createQueue(string s) {
    string queue = "";
    for (char c : s) {
        if (queue.empty() || c > queue.back())
            queue += c;
        else{
            for(int i = queue.length()-1; i >= 0; i--){
                if(c > queue[i]){
                    queue.erase(i+1,queue.length()-i-1);
                    queue += c;
                    break;
                }
            }
        }
    }
    return queue;
}

W ten sposób, dla każdego znaku wejściowego, funkcja sprawdza, czy jest silniejszy od ostatniego znaku w kolejce. Jeśli tak, dodaje go do końca kolejki. Jeśli nie, iteruje od końca ciągu kolejki, szukając pierwszego znaku, którego jest silniejszy i usuwa wszystkie z

MarekR22 do ChatGpt3

nie błąd polegał na tym, że nie usuwasz znaków. Brakuje odpowiednika st.pop(); z wersji używającej std::stack

ChatGpt3

Tak, błąd polegał na tym, że brakowało usuwania słabszych znaków z kolejki. Aby to naprawić, możemy dodać pętlę, która będzie iterować od końca kolejki i usuwać znaki, które są słabsze od bieżącego znaku wejściowego.

string createQueue(string s) {
    string queue = "";
    for (char c : s) {
        if (queue.empty() || c > queue.back())
            queue += c;
        else {
            int i = queue.length() - 1;
            while (i >= 0 && c < queue[i]) {
                queue.erase(i, 1);
                i--;
            }
            queue += c;
        }
    }
    return queue;
}

W ten sposób, dla każdego znaku wejściowego, funkcja sprawdza, czy jest silniejszy od ostatniego znaku w kolejce. Jeśli tak, dodaje go do końca kolejki. Jeśli nie, iteruje od końca kolejki, usuwając słabsze znaki, aż znajdzie znak, którego jest silniejszy i dodaje go na koniec kolejki.

MarekR22 do ChatGpt3

Spróbuj jeszcze raz używając C++17 i std::back oraz std::push_back

ChatGpt3

#include <iostream>
#include <string>
using namespace std;

string createQueue(string s);
void printQueue(string queue);

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        auto queue = createQueue(s);
        printQueue(queue);
    }
    return 0;
}

string createQueue(string s) {
    string queue = "";
    for (char c : s) {
        if (queue.empty() || c > queue.back())
            queue.push_back(c);
        else {
            int i = queue.length() - 1;
            while (i >= 0 && c < queue[i]) {
                queue.pop_back();
                i--;
            }
            queue.push_back(c);
        }
    }
    return queue;
}

void printQueue(string queue) {
    cout << queue << endl;
}

W tym kodzie użyłem C++17, pop_back() i push_back() zamiast erase() i +=. pop_back() usuwa ostatni element z końca ciągu, a push_back() dodaje element na końcu ciągu.
Funkcja createQueue nadal działa tak samo jak poprzednio, ale jest bardziej zwięzła i czytelna.

Moja wersja inspirowana AI:

#include <iostream>
#include <string>

std::string finalQueue(std::string s);

int main()
{
    int t;
    std::cin >> t;
    while (t--) {
        std::string s;
        std::cin >> s;
        std::cout << finalQueue(std::move(s)) << '\n';
    }
    return 0;
}

std::string finalQueue(std::string s)
{
    std::string st;
    st.reserve(s.size());
    for (char c : s) {
        while (!st.empty() && c > st.back()) {
            st.pop_back();
        }
        st += c;
    }
    return st;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1