Zadanie

Keďže je svetová pandémia a všetky obchody sú zatvorené, Emma sa rozhodla, že si bude pestovať potraviny sama. Na začiatok sa rozhodla pre sadenie mrkvy. Ako dni plynuli, mrkva rástla. Avšak, keďže Emma bývala v malej dedine obklopenej lúkami, postupne jej na záhradu začali chodiť kradnúť mrkvu miestne zajace. Bezradná Emma sa rozhodla, že musí tento problém čím skôr vyriešiť a začala zajace sledovať. Tie však boli prefíkané a vyčkávali skryté za plotom pokiaľ sa nebudú môcť bezpečne dostať na záhradu. Jediné, čo bolo spoza plota vidieť, boli ich vytŕčajúce uši. Pozorná Emma si však tento detail všimla a po čase zistila, že čakajúce zajace sú vždy rovnako veľké a teda majú aj rovnakú vzdialenosť medzi ušami. S týmto poznatkom už vedela jednoducho zistiť na koľko zajacov striehnucich za plotom si musí dať pozor. Odvtedy bolo krádežiam mrkvy koniec.

Vedeli by ste vypočítať, koľko zajacov Emma práve vidí?

Úloha

Pozorujeme zajace. Predpokladáme, že všetky zajace sú rovnako veľké, presnejšie, že majú rovnakú vzdialenosť medzi ušami. Avšak keďže sú plaché, skrývajú sa pred nami a to tak, že vidíme len ich uši U. Chceli by sme zistiť, koľko zajacov vidíme, prípadne či je naše pozorovanie chybné a v skutočnosti sa nejedná o zajace. Vašou úlohou je zistiť, na koľkých zajacov sa pozeráme.

Formát vstupu

Vstup je tvorený 1 riadkom, na ktorom sa nachádza \(n\) znakov U alebo ..

Formát výstupu

Na výstup vypíšte jedno číslo, a to počet sledovaných zajacov. V prípade zlého pozorovania vypíšte hodnotu \(-1\).

Hodnotenie

Sú 4 sady vstupov, v ktorých platia tieto obmedzenia:

Sada 1 2 3 4
\(1 \leq n \leq\) \(100\) \(1\,000\) \(100\,000\) \(1\,000\,000\)

Príklad

Input:

..U..U.U..U

Output:

2

V tomto prípade vidíme \(2\) zajace, ktoré majú zhodnú vzdialenosť medzi ušami rovnú \(2\).

Input:

..UUU.U

Output:

-1

V danom prípade je pozorovanie chybné, nemôže sa jednať o zajace, a teda bude výstup \(-1\).

Myšlienka riešenia

Aby sme zistili, koľko zajacov sa skrýva za plotom, musı́me najprv zistiť vzdialenosť medzi prvými dvoma ušami na vstupe. Keďže predpokladáme, že vzdialenosť medzi ušami je pre všetkych zajacov rovnaká, malo by platiť, že pre každého nasledujúceho zajaca, tj. pre každú nasledujúcu dvojicu ušı́ na vstupe bude táto vzdialenosť rovnaká. V prı́pade, že sa daná vzdialenosť lı́ši, nejedná sa o zajace, a teda na výstupe bude \(-1\). Pokiaľ bude vzdialenosť pre každé \(2\) uši rovnaká, vypı́šeme počet zajacov, pre ktorých sme túto vzdialenosť overovali.

Časová a pamäťová zložitosť

Keďže sa stačı́ na celý vstup pozrieť iba jeden raz, časová zložitosť bude lineárne závislá od dĺžky vstupu – \(O(n)\). Pamäťová zložitosť bude konštantná - \(O(1)\), keďže stačı́ ak si budeme počet zajacov uchovávať v jednej premennej a postupne počas čı́tania vstupu túto hodnotu zvyšovať.

def main(prvy = True, ucho = 0, vstup = input(), vzdialenost = 0):
    x = None
    pocet = 0
    for znak in vstup:
        if znak == "U":
            if ucho == 0:
                ucho +=1
                vzdialenost = 0
            elif ucho == 1:
                ucho = 0
                pocet+=1
                if prvy == True:
                    x = vzdialenost
                    prvy = False
                    vzdialenost = 0
                elif prvy == False:
                    if x != vzdialenost:
                        return -1
        elif znak !="U" and ucho==1:
            vzdialenost+=1
    return pocet

print(main())
#include <iostream>
using namespace std;

int main() {
    string in;
    cin >> in;

    int sirka_zajaca = -1;
    int zaciatok_zajaca = -1;
    int pocet_zajacov = 0;

    for (int i = 0; i <= in.length(); i++) {
        if (in[i] == 'U') {
            if (zaciatok_zajaca == -1) {
                zaciatok_zajaca = i;
            } else {
                pocet_zajacov++;
                if (sirka_zajaca == -1) {
                    sirka_zajaca = i - zaciatok_zajaca;
                } else {
                    int sirka = i - zaciatok_zajaca;

                    if (sirka != sirka_zajaca) {
                        cout << "-1" << endl;
                        return 0;
                    }
                }
                zaciatok_zajaca = -1;
            }
        }
    }

    cout << pocet_zajacov << endl;
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.