Určite si pamätáte úlohu Organizácia Kapustnice z
minulej série. Keď ju Kristína úspešne vyriešila na plný počet hneď sa
išla svojím riešením pochváliť svojej sestričke Janke. Vysvetľovala jej
ho na príklade zo zadania. Tá sa jej však začala pýtať veľa rôznych
otázok: a čo keby v tomto reťazci bolo tuto T
namiesto
V
? Ako by sa zmenilo riešenie keby sme uvažovali len tento
podreťazec? Čo keby sme tu pridali V
ako 3tie písmenko? Čo
keby sme tu zobrali tento podreťazec a zrkadlovo ho otočili?
Úloha
Naštudujte si úlohu Organizácia Kapustnice z minulej série. V nej začneme so stolom s vedúcimi a tortami – reprezentovaný reťazcom z písmen ‘T’ - reprezentujúce tortu, a ‘V’ – reprezentujúce vedúceho. Vedúci sa hýbu zľava doprava, zoberú prvú tortu ku ktorej prídu a odídu z radu. Chceme doniesť do radu niekoľko vedúcich a/alebo tort, tak aby každá torta bola zjedená, a každý vedúci mal presne jednu tortu, a to tak, aby výsledný rad (počet vedúcich + počet tort) bol čo najmenší. Práve dĺžka najmenšieho radu ktorý vieme dostať, je čo nás zaujíma.
Navyše, chceme vedieť, ako sa táto hodnota mení, ak zmeníme rad vedúcich a tort. Na vstupe bude postupne \(q\) z nasledovných požiadaviek:
vysledok a b
- vypíšte najmenšiu dosiahnuteľnú dĺžku opraveného radu, ak nás zaujíma rad medzi reprezentovaný tortami/vedúcimi medzi indexami \(a\) a \(b\) – vrátane. (Indexy číslujeme od 0.) Napriklad ak je momentálne stav raduVVTVTTVV
a chceme vyhodnotiť operáciuvysledok 1 5
, tak program vypíše 6, pretože to je dĺžka správneho výsledku úlohy keď sa uvažuje podreťazecVTVTT
začínajúci na indexe \(1\) a končiaci na indexe \(5\).vymen a z
- zmeňte znak na pozícii \(a\) na znakz
.z
je buď ‘V’ alebo ‘T’. Napríklad reťazecVVTVTTVV
sa operáciouvymen 1 T
zmení naVTTVTTVV
.pridaj a z
- pridaj na \(a\)-te miesto radu (teda po \(a\) miestach v rade) bude pridaný znakz
(vedúci ak je to ‘V’, torta ak ‘T’). Napríklad reťazecVTTVTTVV
sa operácioupridaj 2 V
zmení naVTVTVTTVV
.zmaz a b
- z radu odstránime všetkých vedúcich/všetky torty medzi indexami \(a\) a \(b\) (vrátane). Napríklad reťazecVTVTVTTVV
sa operáciouzmaz 5 6
zmení naVTVTVVV
.reverzni a b
- zrkadlovo obrátime časť radu medzi indexami \(a\) a \(b\). Napríklad reťazecVTVTVVV
sa operácioureverzni 1 4
zmení naVVTVTVV
.
Vstup
V prvom riadku vstupu sú dve čísla: Počet znakov v počiatočnom reťazci \(1 \le n \le 10^5\) a počet operácii \(0 \le q \le 10^5\). Na druhom riadku vstupu sa nachádza počiatočný stav radu \(r\). Nasledujúcich \(q\) riadkov popisuje operácie. Každý z týchto riadkov obsahuje jedno z nasledujúcich:
vysledok a b
kde \(0 \le a \le b\) a \(b\) je menej ako dĺžka reťazca vytvoreného predchádzajúcimi operáciamivymen a z
kde \(0 \le a\), \(z\in\{V, T\}\) a \(a\) je menej ako dĺžka reťazca vytvoreného predchádzajúcimi operáciamipridaj a z
kde \(0 \le a\), \(z\in\{V, T\}\) a \(a\) nepresiahne dĺžku reťazca vytvoreného predchádzajúcimi operáciamizmaz a b
kde \(0 \le a \le b\) a \(b\) je menej ako dĺžka reťazca vytvoreného predchádzajúcimi operáciamireverzni a b
kde \(0 \le a \le b\) a \(b\) je menej ako dĺžka reťazca vytvoreného predchádzajúcimi operáciami
Výstup:
Pre každú operáciu vysledok a b
vypíšte jedno číslo:
najmenšiu možnú dĺžku na ktorú možno “opraviť” podreťazec radu medzi
indexami \(a\) a \(b\) (vrátane).
Bodovanie
Existuje 8 testovacích sád.
V prvej sade počet operácii \(q \le 100\) a dĺžka reťazca neprekročí 100.
V druhej sade bude používaná iba operácia
vysledok
na celom vstupe, a operáciapridaj
ale nové torty/vedúci sú pridané iba na koniec raduV tretej sade bude používaná iba operácia
vysledok
ale na ľubovolnom podintervale.V sadách 4, 5 budú používané iba operácie
vymen
avysledok
.V sade 6 budú požívané iba operácie
vymen
,vysledok
,pridaj
.V sade 7 budú používané operácie
vymen
,vysledok
,pridaj
azmaz
.V sade 8 budú používané všetky operácie.
Príklad
Input:
8 9
VVTVTTVV
vysledok 1 5
vymen 1 T
vysledok 1 5
pridaj 2 V
vysledok 1 5
zmaz 5 6
vysledok 1 5
reverzni 1 4
vysledok 1 5
Output:
6
8
6
8
6
- Prvá otázka sa pýta na najlepšie opravenie (pod)radu VTVTT. Z riešenia Organizácie Kapustnice vieme, že výsledok je 6.
- Po druhej požiadavke bude rad VTTVTTVV.
- Tretia otázka sa pýta na opravenie radu TTVTT, z ktorého najlepšie vieme spraviť napríklad VVVTTVTT.
- Po štvrtej požiadavke bude rad VTVTVTTVV.
- Piata otázka sa pýta na opravenie radu TVTVT, do ktorého stačí pridať jediného vedúceho.
- Po šiestej požiadavke dostaneme rad VTVTVVV.
- Siedma otázka sa pýta na podpostupnosť TVTVV.
- Po ôsmej požiadavke dostaneme rad VVTVTVV.
- Napokon, deviata otázka sa pýta na odpoveď pre podpostupnosť VTVTV.
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.