12231. Kolejka [AL_01_02]

[alvir]

Mam problem z powyższym zadaniem. Problemem jest to, że mój program zostaje odrzucony przez sędziego ze względu na przekroczony limit czasu.
Zastanawiam się więc nad innym rozwiązaniem problemu, ale nie mogę go znleźć i chciałbym prosić o jakąś podpowiedź.
Oto mój kod(nie za bardzo wiem jak go wkleić, żeby był schludnie, więc jeżeli ktoś, mógłby mi powiedzieć jak to zrobić to byłoby miło):

#include <iostream>
#include <string>

using namespace std;

string kolej;
int main()
{
    int ile;
    int dlogosc_kolejki;
    cin>>ile; 									//to licznik ilosci ciagow wprowadzonych

    for(int i=1; i<=ile; i++) 	

					//tu wykonuje sie petla ponawiajaca wprowadzenie ciagu itd.
{
    cin>>kolej;								//wprowadzamy ciag znakow
    
    dlogosc_kolejki=kolej.length();
    for(int y=dlogosc_kolejki-1; y>=1; y--) 				/*petla rusza od konca sprawdzajac czy poprzedni wyraz nie 
    									jest wiekszy od poprzedzajacego go*/
    {
	    if(kolej[y]>kolej[y-1])
	    {
		    kolej.erase(y-1, 1); 				//jezeli tak to go usuwa
		    dlogosc_kolejki--;
	        
	    }
    
    }
    cout<<kolej<<endl; 							//wypisujemy ostateczna kolejke
}
return 0;

}

[narbej]

stringi są wolne - porównując np do tablicy char, a poniższa linijka
kolej.erase(y-1, 1) <-- to jest to już dużo za wolne w tym zadaniu.

PS
Zaznaczasz cały wklejany kod i ctrl+k - już Ci to zrobiłem.

[alvir]

Dzięki wielkie za pomoc. Rozumiem, że zamiast samego "erase" mam wymyślić coś co będzie usuwać te znaki? Pętle można zostawić?

[narbej]

2 x tak.

[alvir]

W oparciu o twoje rady opracowalem juz kilka programów, jednak żaden z nich nie zadziałał wstarczająco szybko, dla wymogów tego zadania.
Wklejam tutaj to, co wydaje mi się najlepszym z wymyślonych przezemnie sposobów. Nie mam za bardzo pomysłu co jeszcze może być tutaj za wolne. Miałem też zalążek pomysłu z rekurencją, ale narazie stanąłem tam w martwym punkcie.

    #include <iostream>
    #include <string>
    using namespace std;
    
    char kolej[1000000];
    
    
    
    int main()
    {
        int ile_powtorzen;
        cin>>ile_powtorzen;                     //wybieramy iloscpowtorzen i rozpoczyna sie petla ktora wykona wczytywania
        for(int i=1; i<=ile_powtorzen; i++) 
        {
            char *ok_kolej;
            ok_kolej = new char[1000000];       //za pomoca wskaznika deklarujemy robocza tabele char
            cin>>kolej;                         //wprowadzamy pierwotna kolejke
            int ile=0;                            
            while(kolej[ile]!=NULL) ile++;          //int ile jest licznikiem w petli okreslajacej dlogosc pierwotnej kolejki
    
            char przod=kolej[ile-1];                //okreslamy robocza zmienna przod
            int bufor=0;                            //bufor jest licznikiem do pracy i zapisu w roboczej tabeli ok_kolej
            for(int j=ile-2; j>=0; j--)             //petla rozpoczyna od tylu do przodu kolejki
            {
                if((int)kolej[j]>=(int)przod)       //to wyrazenie szuka danej litery, ktora bedzie wieksza od aktualnego przodu
                {
                    ok_kolej[bufor]=przod;          //jezeli znajdzie taka litere to wpisuje aktualny przod do ok_kolei
                    przod=kolej[j];                 //a potem znaleziona wieksza litera staje sie przodem
                    bufor++;                        //bufor jest powiekszany
                }        
            }
            ok_kolej[bufor]=przod;                  //jezeli porownanie dotarlo do konca ozancza to ze aktualny przod jest najwiekszy i powinien wyladaowac w ok_kolei
            ok_kolej[bufor+1]=NULL;                 //dodajemy na koncu ok_kolei NULL, dla zachowania zasad STRING (nie wiem czy to potrzebne)
            for(int j=bufor; j>=0; j--) cout<<ok_kolej[j]; //nalezy odwrocic kolej tak by najwieksze litery znalazly sie na poczatku, a nie na koncu
            cout<<endl;
            delete [] ok_kolej; //robocza ok_kolej jest usuwana z pamieci przed powtorzeniem petli
        }
        return 0;
    }

[narbej]

Dzisiaj nie będę miał czasu, ale to co zauważyłem. Tablica kolej jest globalna, a powinno się unikać wszelkich zmiennych globalnych, chyba, że nie mamy wyjścia lub wiemy co robimy [wiemy że to zło, ale się z tym godzimy w imię innych wyższych celów ]
Ok_kolej mogłaby być zadeklarowana identycznie i tylko raz, nie widzę tu sensu tworzenia jej dynamicznie w środku pętli - tym bardziej, że i tak wstawiasz za każdym razem na sztywno stałą wartość. Pomyśl, czy nie można [efektywnie] użyć tylko jednej tablicy, podobnie jak w początkowym pomyśle, ale bez erase.

Na razie tyle.

[adambek]

AC

[i6g7g6y5]

Dzień dobry, ja tutaj z pytaniem odnośnie treści bo nie wiem czy ją rozumiem.
więc od najsilniejszego idziemy od 'z' do 'a', następnie wiadomo, że 'a' > 'A'.
Skąd wiadomo czy 'a' > 'Z'? albo 'a'<'Z', skoro małe 'z' jest > 'a' to duże 'Z' > 'A' ?
Dlaczego nie jest treść sprecyzowana?
Jakby było napisany 'a' > 'Z' to by wszystko było jasne, (bo zakładamy, że 'Z' > 'A')

[tarpauwatratar]

Skąd wiadomo czy 'a' > 'Z'? albo 'a'<'Z', skoro małe 'z' jest > 'a' to duże 'Z' > 'A' ?

Z przykładu i treści zadania.

Dlaczego nie jest treść sprecyzowana?

Przyznaję, że można było doprecyzować specyfikację zadania. Niemniej ja dostałem AC za pierwszym razem, a opierałem się wyłącznie na treści zadania. 305 AC też o czymś świadczy więc nie jest źle.

Jakby było napisany 'a' > 'Z' to by wszystko było jasne, (bo zakładamy, że 'Z' > 'A')

Nie byłoby jasne. Ktoś zacząłby się zastanawiać, dlaczego w przykładzie są ciągi literek typu: "klKKnNLlNL", skoro w treści opisano jedynie literki a, A, z oraz Z.

A teraz wisienka na torcie

Dlaczego nie jest treść sprecyzowana?

Bo nie jest

Swojego czasu też męczyłem się z jakimś zadaniem, którego nie rozumiałem. Oczywiście część zadań ma to do siebie, że ich treść dociera do ludzi dopiero po otrzymaniu baaaardzo dokładnych wskazówek, niemalże gotowca - kwestia tak zwanego "nie nadawania na tych samych falach". To zadanie jednak do nich się nie zaliczało - po rozwiązaniu go dalej uważałem, że treść wprowadza w błąd. Swoje zastrzeżenia przedstawiłem na forum, gdzie nikt nie zaprzeczał moim tezom, ale mimo to ludzie (jak pamiętam głównie @narbej) stawali po stronie autora i uważali moje podejście za czepialstwo. Oczywiście nie przemawiała do mnie taka argumentacja...

Aż tu nagle ktoś (niestety nie pamiętam kto) na moje twierdzenie, iż specyfikacja powinna być dokładna, odpowiedział coś w rodzaju (przekazuję sens wypowiedzi, a nie słowa): "Powinna, ale w praktyce zawsze specyfikacja nie jest dokładna, stanowi pewne przybliżenie i trzeba się domyślać co autor zadania/klient/prowadzący laboratoria ma na myśli mając jedynie pewien ramowy szkic oraz modyfikować specyfikację adekwatnie do napotkanych trudności programistycznych i humorów autora zadania/klienta/prowadzącego".

Radzę zapamiętać i kombinować aż do skutku przy każdym kontakcie z programowaniem, nawet na SPOJu

[i6g7g6y5]

prawdopodobnie obstawiam, że autor zadania nie chciał go utrudniać, więc siła zwierzęcia jest kodem ASCII , zatem faktycznie A < Z < a < z
wystarczyłoby taką nierówność zapisać i tyle :).

[i6g7g6y5]

Otrzymuję TLE (przekroczono limit czasu).
Na początku zrobiłem na cin, cout i faktycznie - mogło przekroczyć limit, ale gdy przeszedłem na scanf i printf i nadal wyświetla, że przekroczono... no to już więcej nie zrobię.
Co jest nie tak?
kodzik:<=Kiedyś był tu ze wskaźnikami =>
zadanie: http://pl.spoj.com/problems/AL_01_02/

PS
Czy to przez to, że wskaźniki są za wolne?

[narbej]

prawdopodobnie obstawiam, że autor zadania nie chciał ...

Najpierw zrób zadanie, a nie z góry obstawiaj

Nie tylko w języku c/c++ napis 'a' ma konkretne znaczenie, dla każdego trochę bardziej zaawansowanego [kumatego] programisty oczywiste.

jest kodem ASCII , zatem faktycznie A < Z < a < zwystarczyłoby taką nierówność zapisać i tyle :).

Wystarczy[łoby] mieć tablicę kodów ASCII pod ręką i od czasu do czasu do niej zaglądnąć. i tylko tyle

305 AC też o czymś świadczy więc nie jest źle.

Zgoda, ale jest też 618 [na razie ] TLE i tylko 122 osób, które mogły wysłać więcej niż jedno AC - stąd te 305. W końcu zadanie jest nie bez powodu w kategorii zadań średnich, a nie łatwych.

[i6g7g6y5]

Nikt nie wie?

[narbej]

zrobiłem na cin, cout

Też zrobiłem na cin, cout + ios::sync_with_stdio(0) ===> AC czas 1.26

kodzik: http://ideone

90 linijek to kodzik? [ok 20 linijek kodziku w zupełności wystarczyłoby]
Dlatego trudno to analizować.

Czy to przez to, że wskaźniki są za wolne

Niee, to przez programistę, bo to od niego zależy co z tym [ze wskaźnikami] zrobi.

PS
Musisz przemyśleć i skrócić kod - nic tu raczej nie da się zrobić i wymyśleć. Przy okazji przemyśl taką swoją dziwną konstrukcję:

if(p)
{
while(p)
{
...
Oczywiście wątpię, czy jej poprawienie spowoduje cudowne nie TLE

PS 2
Nie rozumiem też twojego sposobu pisania main(). Przecież wszyscy wiedzą, że prawidłowo [ale też bez wpływu na TLE] powinno się pisać:

int main(){
starter();
}
i tyle , bez zbędnych śmieci w main().

[i6g7g6y5]

dobra, to jade bez wskaznikow i tych wszystkich bo nie ma to sensu...
if(p) bo jesli nie ma p to nie ma co sprawdzac...

[tarpauwatratar]

prawdopodobnie obstawiam, że autor zadania nie chciał go utrudniać, więc siła zwierzęcia jest kodem ASCII , zatem faktycznie A < Z < a < zwystarczyłoby taką nierówność zapisać i tyle :).

Yyyy... to będę chamem. A co z x? A < Z < a < z .... a x? x < A < Z < a < z czy A < x < Z < a czy...?

Otrzymuję TLE (przekroczono limit czasu).

Jak wielu.

Na początku zrobiłem na cin, cout i faktycznie - mogło przekroczyć limit, ale gdy przeszedłem na scanf i printf i nadal wyświetla, że przekroczono... no to już więcej nie zrobię.

Widocznie zły algorytm...

kodzik: http://ideone.com/JPwPPy

Yyyy... jestem wróżbitą

Czy to przez to, że wskaźniki są za wolne?

Tak i nie, a ściślej: dzięki @narbej za odpowiedź

Zgoda, ale jest też 618 [na razie ] TLE i tylko 122 osób, które mogły wysłać więcej niż jedno AC - stąd te 305. W końcu zadanie jest nie bez powodu w kategorii zadań średnich, a nie łatwych.

Mógłbym znowu wykazać się "czepialstwem" i podać przykłady zadań łatwych z dużo gorszymi wynikami, ale oczywiscie rozumiem sens wypowiedzi i zgadzam się z nim.

W każdym razie w matematyce zaprzeczeniem kwantyfikatora ogólnego jest kwantyfikator szczegółowy. A w tym przypadku nie tylko istnieje osoba, która to zrozumiała, ale aż 305 osób ogarnęło to zadanie Nota bene jedno z moich ulubionych

PS
@i6g7g6y5 jeżeli nie masz pomysłu to ewentualnie możesz przeszukać moje ostatnie posty... pisałem komuś o zadaniu ze zwierzakami ustawiającymi się w kolejce Bardzo możliwe, że padło tam słowo kluczowe do uzyskania AC (ale nie gwarantuję!)

[i6g7g6y5]

pisałem komuś o zadaniu ze zwierzakami ustawiającymi się w kolejce

No akurat mi o tym pisałeś

[tarpauwatratar]

Wybacz, że nie zapamiętałem - ostatnio mam nieszczęście rzadko siedzieć na SPOJu... dopadło mnie życie krótko mówiąc

No ale w takim razie sprawdziłem i gwarantuję, że prawo dżungli w kolejce opisałem podpowiedzią dającą AC

[narbej]

if(p) bo jesli nie ma p to nie ma co sprawdzac...

Nie miałeś tłumaczyć, ale przemyśleć i przestać stosować.
Powtórzę
Zamiast:
if(p)
while(p)

wystarczy aż nadto
samo

while(p)

.
.

ale aż 305 osób ogarnęło to zadanie

Warto jeszcze, żeby jedna z tych ogarniających osób [dużo mniej niż 305], nauczyła się prawidłowo czytać i interpretować dane - wystarczy tylko przeczytać uważnie nagłówki rubryk no i niestety trochę pomyśleć.

[tarpauwatratar]

Warto jeszcze, żeby jedna z tych ogarniających osób [dużo mniej niż 305], nauczyła się prawidłowo czytać i interpretować dane - wystarczy tylko przeczytać uważnie nagłówki rubryk no i niestety trochę pomyśleć.

Patrzyłem na szybko (zapomniałem, że w ogóle jest taka kolumna). Poza tym podane przeze mnie liczby wybiegają w przyszłość

Ale przyznaję, że dopiero teraz Twoja wcześniejsza wypowiedź nabrała dla mnie głębszego sensu. I fakt- na dzień dzisiejszy duuużo mniej osób rozwiązało to zadanie.