Apr 2016
1 / 11
Apr 2016
Aug 2017
lich555
Apr '16

Witam.
Napisałem po dłuższym czasie myślenia taki oto program do zadania AL_01_02 - Kolejka, które znajdziecie pod tym linkiem: AL_01_02 - Kolejka24
Tutaj jest mój kod39
Wynik jest (najprawdopodobniej) prawidłowy, lecz problem jest z czasem wykonania. Jak zoptymalizować ten program?
PS. Jak wkleić kod źródłowy na to forum?

  • created

    Apr '16

  • last reply

    Aug '17
  • 10

    replies

  • 1.1k

    views

  • 3

    users

  • 2

    links

narbej
Apr '16
1

ctrl c
ctrl v
zaznaczasz wklejony kod i: ctrl shift c
lub zaznaczasz wklejony kod i w menu ==> '</>'

        for (int i = 1; i < n; ++i){
            if (A[i] == A[i-1]){
                continue;
                }
lich555
Apr '16
2

Niezbyt rozumiem jak mi ma to pomóc. Porównuje to element tablicy z jej poprzednim i jeśli są równe to kontynuuje. 

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int ile;
    char tablica[ 1000000 ];
    
    cin >> ile;
    for( int i = 0; i < ile; i++ )
    {
        cin >> tablica;
        int IleZnakow = strlen( tablica );
        
        for( int b = 0; b < IleZnakow; b++ )
        {
            for( int x = IleZnakow - 1; x >= 0; x-- )
            {
                if( tablica[ b ] < tablica[ x ] )
                {
                    tablica[ b ] = tablica[ x ];
                    tablica[ x ] = 0;
                }
            }
        }
        
        for( int q = 0; q < IleZnakow; q++ )
        {
            cout << tablica[ q ];
        }
        cout << endl;
    }
    return 0;
}

Wiem, że dla testowych też mam źle, ale prosiłbym o jakąś małą wskazówkę
co do tego kodu, czy w ogóle idę dobrym tokiem rozumowania, jakoś mnie
naprowadzić.

narbej
Apr '16
1

To nie była żadna pomoc na temat zadania. To była tylko odpowiedź na pytanie jak wkleić kod i przykład - nie związany z tym zadaniem - fragment poprawnie wklejonego kodu. Niestety ta moja podpowiedź nic nie pomogła. Poprawiłem więc i wkleiłem poprawnie twój źle wklejony kod - możesz obejrzeć historię edycji swojego ostatniego postu - kliknij w ikonkę pomarańczowego ołówka-pisaka.

Co do zadania - doprowadź najpierw chociaż do tego, aby twój program poprawnie odpowiadał na testy z zadania, a dopiero wtedy możesz myśleć o problemie przekroczenia limitu czasu.

To zadanie nie jest trudne, ale też nie jest łatwe. Jest w kategorii średnich. Aby je zrobić trzeba je dokładnie zrozumieć, więc warto poczytać je kilkakrotnie i zrobić najpierw na "papierze" + "ołówek". Potrzebny jest tu także pewien spryt programistyczny [pewien zasób i doświadczenie]. Jedyny sposób zdobycia, to samodzielne rozwiązywanie jak największej ilosci zadań, zaczynając od najprostszych i najłatwiejszych.

lich555
Apr '16

Tutaj jest działający kod, który (jakżeby inaczej) przekracza limit czasowy:
#include
#include 

using namespace std;

int main()
{
    int ile;
    char tablica[ 1000000 ];

    cin >> ile;
    for( int i = 0; i < ile; i++ )
    {
        cin >> tablica;
        int IleZnakow = strlen( tablica );

        for( int b = IleZnakow - 1; b > 0; b-- )
        {
            if( tablica[ b ] > tablica[ b - 1 ] )
            {
                tablica[ b - 1 ] = tablica[ b ];
                tablica[ b ] = 0;
            }
        }

        for( int q = 0; q < IleZnakow; q++ )
        {
            cout << tablica[ q ];
        }
        cout << endl;
    }
    return 0;
}
narbej
Apr '16

!. Nadal wklejasz kod nie zupełnie poprawnie - musisz zaznaczyć cały kod - zobacz, jak masz :wklejone includy
2. Obawiam się, że tylko na ekranie program wygląda poprawnie. Pomyśl. Przy przekierowaniu do pliku, te zera są przecież jednak w jakiś sposób tam [w pliku] umieszczane [drukowane]. To że ich "normalnie" nie widzisz, nie świadczy,że ich tam niema. Dobry hex edytor Ci to dokładnie pokaże.

lich555
Apr '16
1

Przepraszam za złe wklejenie kodu. Dobrym pomysłem byłoby użycie string zamiast tablicy? Zastanawiałem się nad funkcją erase(), ale pożera ona niesamowite zasoby czasowe i raczej nie przyjęłoby mi rozwiązania.
Nie wystarczy zapamiętać nr indeksu ostatniego "poprawnego" zwierzaka? Te zera mogłyby być, ale na końcu i nie zostałyby one wypisane.

narbej
Apr '16

Nie przepraszaj, po prostu się popraw i następnym razem postaraj się lepiej.

Ponieważ "jedziesz" od końca, więc zastanów się dokładnie co i ja się dzieje. Ostatni zwierzak w kolejce zostanie w niej zawsze, więc niech tak będzie, nic nie zmieniasz, ale pamiętasz to miejsce [indeks]. Idziesz do przodu i co? Gdy napotykasz silniejszego lub równego nic nie się nie dzieje, nic nie zmieniasz. Zapamiętujesz to miejsce w kolejce - indeks [nowy]. Idziesz do przodu [kolejki]. Gdy napotykasz słabszego, to nic się nie dzieje idziesz do przodu. Gdy napotykasz silniejszego, równego, to tylko kopiujesz go do zapamiętanego miejsca -1 i zapamiętujesz to nowe miejsce. Gdy dojdziesz do początku, to drukujesz od zapamiętanego miejsca. Pewnie napisałem niezrozumiale ale nie mam zamiaru pisać inaczej - rozwiązywanie krzyżówek, sudoku, gier i zagadek umysłowych wymaga pewnego wysiłku, więc proszę, wyśil się trochę. :wink:

1 year later
pain121297
Aug '17
1

Mam ten sam problem (przekroczony limit czasu). Nie jestem pewien co jest złe: mój pomysł, czy jego wykonanie. Mógłby mnie ktoś naprowadzić co? Jeśli jego wykonanie, to co powinienem zmienić w kodzie.

opis:
Zaczynamy od ostatniej litery i oznaczamy ją jako lidera. Następnie prównujemy lidera z każdą literą w górę kolejki:
-jeśli porównywana litera jest mniejsza rangą od lidera wyrzucamy ją (zmieniamy na 0 );
-jeśli taka sama nie robimy nic;
-jeśli większa zostaje nowym liderem.
Na koniec wypisujemy wszystkie znaki oprócz tych usuniętych (zmienionych na 0).

kod:
-------------------- <-- usunięty

narbej
Aug '17
1

for (int j=0;j<strlen(kolejka);j++) <==> TLE [wielokrotne wywoływanie funkcji strlen]