20. ROTATOR SLOVA — REŠENJE ZADATKA

U zadatku se pri svakom pritisku tastera prvo slovo svake reči premešta na kraj te reči. Potrebno je odrediti najmanji pozitivan broj pritisaka nakon kojeg se ceo tekst vraća u početno stanje. Ključ problema je da za svaku reč pronađemo njen najmanji period, a zatim izračunamo najmanji zajednički sadržalac (NZS) tih perioda.

Zadatak je deo pripreme za takmičenje iz informatike. Pogledajte i stranicu Priprema za državno takmičenje iz informatike, na kojoj je zadatak postavljen.

Tekst zadatka

Kada se pritisne taster na tastaturi, prvo slovo svake reči u tekstu premesti se na poslednje mesto te reči. Odrediti koliko je puta potrebno pritisnuti taster da bi se rečenica vratila u početno stanje.

Ulaz:
Sa standardnog ulaza učitava se jedna linija teksta sastavljena od malih slova engleske abecede i razmaka. Tekst može imati najviše 10⁶ karaktera. Garantuje se da se rečenica vraća u prvobitno stanje nakon najviše 10¹⁸ pritisaka tastera.

Izlaz:
Ispisati najmanji broj pritisaka tastera, veći od nule, koji je potreban da se rečenica vrati u prvobitno stanje.

Primer 1

Ulaz:

mala sirena zivi na dnu mora

Izlaz:

Objašnjenje:
Posle svakog pritiska prvo slovo svake reči prelazi na kraj te reči. Posle 12 pritisaka svaka reč ponovo dobija svoj početni oblik.

mala sirena zivi na dnu mora
alam irenas iviz an nud oram
lama renasi vizi na udn ramo
amal enasir iziv an dnu amor
mala nasire zivi na nud mora
alam asiren iviz an udn oram
lama sirena vizi na dnu ramo
amal irenas iziv an nud amor
mala renasi zivi na udn mora
alam enasir iviz an dnu oram
lama nasire vizi na nud ramo
amal asiren iziv an udn amor
mala sirena zivi na dnu mora

Primer 2

Ulaz:

sestaci sedmaci i osmaci vole informatiku

Izlaz:

Primer 3

Ulaz:

dada tata i mama

Izlaz:

Napomena: U 50% test-primera reči nisu periodične. U 60% test-primera sve reči su kraće od 100 karaktera.

Ideja rešavanja

Jedan pritisak predstavlja rotaciju reči ulevo za jedno mesto. Ako se reč sastoji od ponavljanja kraćeg bloka, ne moramo pomerati slova onoliko puta koliko reč ima karaktera. Dovoljno je pomeranja za dužinu tog najkraćeg bloka.

Na primer, reč damdam ima šest karaktera, ali se blok dam ponavlja dva puta. Posle tri rotacije reč se vraća u početno stanje:

damdam
amdamd
mdamda
damdam

Zato je period reči damdam jednak 3, a ne 6. Za reč bez kraćeg ponavljajućeg bloka, na primer mala, period je dužina cele reči, odnosno 4.

Svaka reč ima svoj najmanji period. Da bi se ceo tekst vratio u početno stanje, broj pritisaka mora biti deljiv periodom svake reči. Zato tražimo NZS svih najmanjih perioda.

Šta nije dobro u prvobitnoj implementaciji?

Osnovna ideja prvobitnog rešenja — pronalaženje najkraćeg bloka koji se ponavlja, a zatim računanje NZS-a — jeste dobra. Ipak, implementacija koristi tip int za NZS i međuproizvode. Pošto se u tekstu zadatka rezultat može približiti vrednosti 10¹⁸, takav tip može da prekorači opseg i proizvede pogrešan rezultat.

Pored toga, proveravanje kandidata uz izdvajanje podniski nepotrebno ponavlja poređenja. To može da se ubrza korišćenjem prefiksne funkcije: ona za svaku reč pronalazi njen najmanji period u linearnom vremenu. U nastavku je optimizovana varijanta koja koristi long long za računanje NZS-a.

Optimizovano C++ rešenje

#include <iostream>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

// Euklidov algoritam: vraća najveći zajednički delilac dva broja.
long long nzd(long long a, long long b) {
    while (b != 0) {
        long long ostatak = a % b;
        a = b;
        b = ostatak;
    }
    return a;
}

// Vraća najmanji period reči: dužinu najkraćeg bloka
// čijim ponavljanjem može da se dobije cela reč.
int najmanjiPeriod(const string& rec) {
    int n = static_cast<int>(rec.size());
    vector<int> pi(n, 0);

    // Prefiksna funkcija (KMP): pi[i] je dužina najdužeg
    // pravog prefiksa rec[0..i] koji je istovremeno i sufiks.
    for (int i = 1, j = 0; i < n; ++i) {
        while (j > 0 && rec[i] != rec[j]) {
            j = pi[j - 1];
        }

        if (rec[i] == rec[j]) {
            ++j;
        }
        pi[i] = j;
    }

    // Kandidat za period je n - dužina najdužeg prefiksa-sufiksa.
    int period = n - pi[n - 1];

    // Kandidat je period cele reči samo ako deli njenu dužinu.
    if (n % period != 0) {
        period = n;
    }

    return period;
}

int main() {
    string tekst;
    getline(cin, tekst); // Učitava celu rečenicu, uključujući razmake.

    istringstream ulaz(tekst);
    string rec;
    long long odgovor = 1;

    // Izdvajamo reči; operator >> preskače višak razmaka.
    while (ulaz >> rec) {
        int period = najmanjiPeriod(rec);

        // NZS(a, b) = (a / NZD(a, b)) * b.
        // Delimo pre množenja i koristimo long long zbog velikog rezultata.
        long long delilac = nzd(odgovor, period);
        odgovor = (odgovor / delilac) * period;
    }

    cout << odgovor << '\n';
    return 0;
}

Objašnjenje koda

1. Učitavanje teksta. Funkcija getline učitava celu liniju, pa se razmaci ne gube. Zatim istringstream izdvaja reč po reč.

2. Pronalaženje perioda reči. Funkcija najmanjiPeriod računa prefiksnu funkciju. Iz vrednosti poslednjeg elementa dobija se kandidat n - pi[n - 1]. Ako taj broj ne deli dužinu reči, reč se ne sastoji od ponavljanja tog bloka, pa je njen najmanji period dužina cele reči.

3. Spajanje perioda. Promenljiva odgovor čuva NZS perioda svih do tada obrađenih reči. Za svaku novu reč izračunava se NZS trenutnog odgovora i njenog perioda pomoću formule NZS(a, b) = (a / NZD(a, b)) * b.

4. Ispis. Kada se obrade sve reči, odgovor je najmanji pozitivan broj pritisaka koji istovremeno vraća svaku reč, pa time i celu rečenicu, u početno stanje.

Provera na primerima

mala sirena zivi na dnu mora: najmanji periodi su 4, 6, 4, 2, 3 i 4; njihov NZS je 12.
sestaci sedmaci i osmaci vole informatiku: NZS perioda svih reči je 924.
dada tata i mama: reči dada, tata i mama imaju period 2, a reč i period 1; rezultat je 2.

Složenost

Prefiksna funkcija obrađuje svaki karakter reči konstantan broj puta. Zato je ukupna složenost za pronalaženje perioda O(n), gde je n broj karaktera teksta. Za prefiksnu funkciju koristi se dodatna memorija proporcionalna dužini najduže reči. NZS se računa pomoću Euklidovog algoritma, a rezultat se čuva u tipu long long, koji može da predstavi traženu granicu od 10¹⁸.

Zaključak: Ne moramo simulirati svaki pritisak tastera. Dovoljno je da za svaku reč nađemo njen najmanji period i izračunamo NZS tih perioda. Tako se izbegava potencijalno ogroman broj koraka, a rešenje ostaje efikasno i za duge tekstove.

Povratak
|< Priprema za državno takmičenje iz informatike