Zadanie

V miestnom útulku funguje adopcia psíkov1 trochu zvláštne. Ľudia aj psíkovia sa postavia do radu. Vždy keď susedí človek s nejakým psíkom, tak sa môže rozhodnúť, že si ho adoptuje. Toto sa opakuje, pokiaľ sa to dá. Majiteľa útulku by ale zaujímalo, koľko najmenej smutných psíkov a ľudí vie ostať na konci dňa. Viete mu s tým pomôcť?

Úloha

Na vstupe dostanete postupnosť znakov P a C. Vždy, keď sa v postupnosti vedľa seba nachádza P a C, tak ich môžeme vymazať. Toto opakujeme pokiaľ to ide. Koľko najmenej znakov nám vie ostať na konci?

Formát vstupu

Na prvom riadku je celé číslo \(N\) (\(1 \leq N \leq 10^6\)). Na druhom riadku je reťazec dĺžky \(N\) pozostávajúci z písmen P a C.

Sada 1 2 3 4
\(1 \leq N \leq\) \(100\) \(10'000\) \(10^6\) \(10^6\)

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo, ktoré je minimálny počet znakov, ktoré vedia ostať na konci.

Príklady

Input:

2
PC

Output:

0

Prvý človek si adoptuje prvého psa.

Input:

4
CCPP

Output:

0

Najprv si adoptuje vnútorný človek vnútorného psa a následne vonkajší človek bude susediť s vonkajším psom, čiže si ho môže adoptovať.

Input:

3
PCP

Output:

1

Jednému človeku sa bohužiaľ neujde žiaden psík na adoptovanie.

  1. V prípade záujmu o adopciu alebo podporu sa môžete obrátiť na Slobodu zvierat alebo na Váš miestny útulok.↩︎

Môžeme sa zamyslieť: Vie nastať situácia, kedy sú v rade aj ľudia, aj psy, ale nikde človek nesusedí so psom? Evidentne nie. Prečo? Lebo každý súvislý úsek ľudí je na krajoch zakončovaný koncom rady alebo psom. Rovnako to funguje aj keď psov a ľudí vymeníme. A keďže máme aspoň dva súvislé úseky (aspoň jeden úsek ľudí a aspoň jeden úsek psov) a iba dva konce radov, tak niekde musí susediť človek so psom.

Čiže pokiaľ existuje v rade aspoň jeden človek a aspoň jeden pes, tak existuje dvojica, ktorú môžeme vymazať. Toto opakujeme, pokiaľ sú v rade aj psy aj ľudia. Každá adopcia zmenší počet ľudí aj psov o 1, čiže na konci dňa ostanú buď iba ľudia alebo iba psy. Takže minimálny počet znakov, ktoré ostanú na konci je \(|\text{počet psov} -\text{počet ľudí}|\).

Záleží na poradí ľudí a psov v rade?

Nie, lebo v našich úvahách vyššie sme nikdy nepredpokladali, že ľudia a psy sú zoradené nejako špeciálne. Vždy sme len hovorili, že ak sú v rade aspoň jeden človek a aspoň jeden pes, tak existuje dvojica susediacich ľudí a psov, ktorých môžeme vymazať. Čiže ak by sme zmenili poradie ľudí a psov, tak by sa nič nezmenilo.

Časová zložitosť

Časová zložitosť je \(O(n)\), keďže potrebujeme prejsť celý rad a spočítať počet ľudí a psov.

Pamäťová zložitosť

Záleží, či načítavame celý rad do pamäte, a potom ho spracovávame, alebo či načítame iba jeden znak, spracujeme ho a potom načítame ďalší znak. V prvom prípade je pamäťová zložitosť \(O(n)\), v druhom prípade je pamäťová zložitosť \(O(1)\). Na plný počet bodov stačila implementácia s pamäťovou zložitosťou \(O(n)\).

Vzorový python kód má pamäťovú zložitosť \(O(n)\), pretože načítava celý rad do pamäte. Vzorový C++ kód má pamäťovú zložitosť \(O(1)\), pretože načítava iba jeden znak naraz.

N = int(input())
s = input()

psi = 0
ludia = 0
for ch in s:
    if ch == 'P':
        psi += 1
    else:
        ludia += 1

print(abs(psi - ludia))
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N;
    cin >> N;

    int psi = 0;
    int ludia = 0;
    for (int i = 0; i < N; i++)
    {
        char x;
        cin >> x;
        if (x == 'P')
            psi++;
        else
            ludia++;
    }

    cout << abs(psi - ludia) << "\n";
}

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ť.