Predstavte si typický deň vo firme Kódíme S Prestávkami. Je 10:50 a všetci hladní programátori sa pýtajú jedinú otázku: “Kedy bude obed?”
V tejto firme však nechodia na obed len tak hala-bala. Na veľkej obrazovke v kuchynke svieti dlhý reťazec núl a jednotiek, ktorý určuje čo sa práve deje:
Blok núl: “Obed sa ešte pripravuje.”
Blok jednotiek: “Obed je hotový, môžete ísť.”
Samozrejme, signál musí byť vždy pekne v poradí – najprv všetky nuly, potom všetky jednotky.
No ako to už býva, systém sa občas pokazí. Namiesto pekného prechodu z núl na jednotky sa na obrazovke objaví niečo takéto:
`0101110010`
Výsledkom je panika na chodbe. Máme ísť na obed? Ešte počkať? Máme si objednať pizzu?
Programátori si však vedia poradiť. Predpokladajú, že sa v signáli stalo čo najmenej chýb, a tak sa snažia zistiť, koľko čisel by stačilo zmeniť, aby sa signál opravil a všetci konečne vedeli, čo majú robiť.
Dostanete reťazec tvorený nulami a jednotkami. Zistite, koľko najmenej čísel treba v zadanom reťazci zmeniť tak, aby sa z neho stal signál tvaru: 000…111 Teda aby ste dostali reťazec tvorený súvislým blokom núl a potom súvislým blokom jednotiek, pričom oba súvislé bloky musia mať dĺžku aspoň 1.
Na prvom riadku vstupu je číslo $n$ ($2 \leq n \leq 10^6$) udávajúce dĺžku reťazca. V druhom riadku sa nachádza reťazec tvorený $n$ znakmi len 0 alebo 1.
V jednotlivých sadách platia nasledujúce obmedzenia:
| Sada | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $2 \leq n \leq$ | $15$ | $1000$ | $10^5$ | $10^6$ |
Vypíš jeden riadok a v ňom jedno celé číslo udávajúce najmenší počet zmien, ktoré musíme spraviť, aby sme sa dostali do požadovaného stavu.
Input:
7
0101101
Output:
2
Môžeme zameniť nuly na tretej a šiestej pozícii za jednotky, vznikne nám reťazec 0111111. Alebo môžeme zmeniť jednotku na druhej pozícii a nulu na šiestej pozícii. Vtedy vznikne reťazec 0001111.
Input:
5
00000
Output:
1
Reťazec má obsahovať súvislý blok núl aj jednotiek, preto potrebujeme urobiť jednu zmenu - pridať na koniec reťazca jednotku. Vznikne nám tak reťazec 00001.
Našou úlohou je čo najmenším počtom zmien upraviť reťazec tak, aby
mal tvar najprv súvislého bloku núl, po ktorom nasleduje súvislý blok
jednotiek. Znamená to, že reťazec musí vyzerať ako napríklad
0000111.
Riešenie si môžeme predstaviť tak, že si vyberieme nejaké miesto v reťazci, nazvime ho hranica, kde má byť prechod z núl na jednotky. Všetky znaky naľavo od hranice by mali byť nuly a napravo od hranice jednotky. Ak tam nie sú, musíme ich zmeniť. Naším cieľom je nájsť takú hranicu, kde bude potrebné zmeniť čo najmenej znakov.
Počet zmien pre jednu konkrétnu hranicu vypočítame nasledovne: spočítame, koľko jednotiek je naľavo od hranice (tie treba zmeniť na nuly), a koľko núl je napravo od hranice (tie musíme zmeniť na jednotky). Súčet týchto dvoch čísel nám povie, koľko zmien musíme spraviť, ak by bola hranica práve na tomto mieste.
Ak by sme pre každú hranicu opakovane rátali počet jednotiek naľavo a počet núl napravo, trvalo by to príliš dlho. Pre každú hranicu by sme prešli celý reťazec, teda celkovo by sme $n$-krát prešli reťazec dĺžky $n$. Čo by viedlo k celkovej časovej zložitosti $O(n^2)$. To ale vieme urobiť oveľa efektívnejšie.
Na začiatku si spočítame celkový počet jednotiek v reťazci. Potom prechádzame reťazec zľava doprava a sledujeme, koľko jednotiek sme už stretli. Z toho vieme koľko jednotiek je naľavo od aktuálnej hranice - teda koľko znakov musíme zmeniť naľavo od hranice. Taktiež si z toho vieme dopočítať aj koľko núl je napravo. Keďže vieme koľko jednotiek je celkovo a koľko z nich sme prešli, vieme odčítaním týchto dvoch čísel zistiť koľko jednotiek zostáva. Rovnako vieme koľko znakov zostáva do konca. Ak odčítame počet zvyšných jednotiek od počtu zvyšných znakov, zistíme počet zvyšných núl.
Pre každé možné umiestnenie hranice tak vieme v konštantnom čase vypočítať, koľko zmien by sme museli spraviť, a zároveň si priebežne pamätáme najmenší takýto počet. Po prejdení celého reťazca tak nájdeme najmenší počet potrebných zmien.
Toto riešenie má časovú aj pamäťovú zložitosť $O(n)$, keďže reťazec prechádzame len raz a pamätáme si len reťazec a niekoľko pomocných premenných.
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete