Zadanie

V triede na stoličkách usporiadaných do kruhu sedia deti. Na niečo čakajú. Podľa ich žiarivých očí môžeme vytušiť, že čakajú na niečo dobré. Asi to nebude písomka. Nedočkavo sa mrvia a mnohým sa už zbiehajú sliny. Čakajú na nejaké jedlo? Na nejakú maškrtu? Alebo nebodaj čakajú na najväčšiu maškrtu zo všetkých maškŕt, samotnú čokoládu?

Áno, už onedlho príde do miestnosti pani učiteľka a donesie im čokoládu. Bohužiaľ, čokoláda je len jedna1 a tak sa budú musieť deti o čokoládu podeliť. Niektorým sa možno ani neujde.

Pomôžte pani učiteľke zistiť, koľko najviac detí sa môže z čokolády najesť.

Úloha

Tabuľka čokolády sa skladá z \(r\) riadkov a \(s\) stĺpcov kociek čokolády. Pani učiteľka začne tým, že podá čokoládu niektorému dieťaťu v kruhu. Dieťa si odlomí buď jeden riadok alebo jeden stĺpec čokolády a zvyšok podá dieťaťu, ktoré sedí napravo od neho.

Chlapci sú pažraví a vždy, keď dostanú čokoládu, tak si odlomia čo najväčší kus. Čiže keď má čokoláda viac riadkov ako stĺpcov, odlomia si jeden stĺpec, inak si odlomia jeden riadok.

Dievčatá nie sú až také pažravé a navyše si chcú udržať štíhlu líniu. Odlomia si preto čo najmenší kus, tiež jeden riadok alebo jeden stĺpec, ale vyberú si to, čo má menej kociek čokolády.

Zistite, koľko najviac deťom sa ujde čokoláda, ak pani učiteľka čo najlepšie vyberie, ktoré dieťa začne. Dieťa sa započíta len raz, aj keby sa mu čokoláda ušla viackrát.

Formát vstupu

Na prvom riadku je počet tried \(t\), v ktorých treba vyriešiť tento problém. Na každom z ďalších \(t\) riadkov je popis jednej triedy pozostávajúci z čísel \(r\), \(s\) a reťazca \(Z\).

Čokoláda má rozmery \(r \times s\) kociek. \(Z\) je reťazec pozostávajúci z písmen “C” a “D”, ktorý popisuje, ktoré deti sú chlapci a ktoré dievčatá.

Písmená “C” označujú chlapcov a “D” dievčatá, pričom na prvej pozícii reťazca \(Z\) je dieťa, ktoré sedí najbližšie k tabuli, na druhej pozícii dieťa, ktoré sedí napravo od neho, potom dieťa, ktoré sedí napravo od druhého, a tak ďalej. Prvé dieťa v reťazci zároveň sedí napravo od posledného dieťaťa.

 

Obmedzenia na veľkosti vstupov sú naslednovné:

Počet riadkov aj počet stĺpcov každej čokolády je aspoň \(1\) a najviac \(10^6\). V každej triede je aspoň \(1\) žiak a najviac \(10^6\) žiakov.

Počet tried je najviac \(10^6\) a navyše vo všetkých triedach dokopy je najviac \(10^7\) žiakov. Všetky čokolády dokopy majú najviac \(10^7\) riadkov a najviac \(10^7\) stĺpcov.

V tabuľke si môžete pozrieť horné obmedzenia na počet tried \(t\) a počet žiakov vo jednej triede \(z\) a počet riadkov \(r\) a stĺpcov \(r\) jednej čokolády v jednotlivých sadách vstupov.

Označenie vstupu 1 2 3 4 5
Maximálne \(t\) \(50\) \(1\,000\) \(10^6\) \(10\) \(10^6\)
Maximálne \(z,r,s\) \(50\) \(1\,000\) \(20\) \(10^6\) \(10^6\)

Formát výstupu

Na výstup vypíšte \(t\) riadkov, pre každú triedu vypíšte, koľko najviac detí sa môže najesť čokolády, ak si ju budú deliť spôsobom popísaným v zadaní.

Príklad

Input:

5
4 4 DDDDDDD
4 4 CCCCCCCCCCC
10 1 CCCDDD
10 10 CDCD
4 4 DCDCCCD

Output:

7
4
4
4
7

V tretej triede musia najprv jesť dievčatá, lebo chlapec zje celú čokoládu, ktorá ku nemu príde. V štvrtej triede je čokoláda taká veľká, že sa všetci najedia. V piatej triede budú jesť deti v tomto poradí: CCDDCDC. Tým pádom budú rozmery čokolády postupne (4,4), (4,3), (4,2), (3,2), (2,2), (2,1), (1,1), (0,0) a všetci sa najedia.

  1. Lebo školy majú málo peňazí.↩

Kľúčová časť riešenia je, dokázať rýchlo odpovedať na takúto otázku: “ak by sme začali čokoládu rozdávať od \(i\)-teho dieťaťa až po \(j\)-te dieťa vystačí nám čokoláda?”

Totiž, ak by sme to vedeli, vieme úlohu riešiť takzvanou technikou dvoch bežcov. Zoberieme dvoch bežcov a oboch posadíme na začiatok kruhu. Bežci sa budú volať Ivan a Jožo a budú na pozíciách \(i\) a \(j\). Vždy, keď dokážeme nakŕmiť deti od pozície \(i\) po pozíciu \(j\), pohne sa Jožo na ďalšie políčko v kruhu. V opačnom prípade sa pohne Ivan. Všimnime si, že Ivan nikdy nepredbehne Joža, pretože nula detí dokážeme nakŕmiť. Algoritmus skončí, keď Jožo dvakrát obehne celý kruh a riešenie úlohy bude najväčšia možná vzdialenosť bežcov počas behu algoritmu. Rozmyslite si, prečo je tomu tak.

Výnimkou je, že ak by bola odpoveď väčšia ako počet detí, vypíšeme len počet detí.

Obaja bežci spravia najviac \(2\ell\) krokov, kde \(\ell\) je veľkosť kruhu (dĺžka reťazca \(Z\)), vďaka čomu je algoritmus podstatne rýchlejší, ako keby sme skúšali všetkých \(O(\ell^2)\) dvojíc \((i,j)\).

Ako teda zistiť, či sa nejaký úsek detí dá nakŕmiť?

Najskôr si otočíme čokoládu, tak aby bola aspoň taká vysoká ako široká. Túto vlastnosť potom vieme zachovať počas celej konzumácie – chlapec vždy zje stĺpec a čokoládu zúži. Dievča ak dostane čokoládu, ktorá je vyššia ako širšia, zje riadok. Ak však dievča zje čokoládu, ktorá je rovnako vysoká ako široká, zje stĺpec.

Pozrime sa na úsek detí od \(i\) po \(j\). Predstavme si, že \(i\)-te dieťa bolo prvé čo jedlo čokoládu. Označme si \(c\) počet chlapcov v tomto úseku, \(d\) počet dievčat a \(e\) počet dievčat, ktoré zjedli stĺpec čokolády. Potom, čokoláda rozmerov \(r\times s\), kde \((r\leq s)\) vystačí pre deti od \(i\) po \(j\), pokiaľ \(e + c \leq s\) a zároveň \(d-e \leq r\). To je inak to isté, ako overovať \(e+c \leq s\) a \(c+d\leq r+s\).

Zistiť \(c\) a \(d\) pre nejaký úsek kruhu je ľahké. Jediná ťažká časť tejto úlohy bolo efektívne zistiť \(e\).

Všimnime si, že keď dievča je čokoládu po chlapcovi, tak sa určite nezapočíta do \(e\). Podobne, ak máme \(8\) dievčat po \(8\) chlapcoch. Intuitívne, na to, aby bolo veľké \(e\), potrebujeme, aby veľa dievčat jedlo čokoládu bez toho aby pred nimi jedlo čokoládu veľa chlapcov. Presnejšie, zoberme postupnosti detí od pozície \(i\), po všetky možné pozície \(k\), \(k\leq j\), v každej postupnosti spočítame dievčatá a chlapcov, a označme \(f\) najväčší z rozdielov počtu dievčat mínus počet chlapcov. Potom \(e = max(0, (s-r+f+1)//2)\). (Rozmyslite si, prečo.)

Čiže už len potrebujeme zistiť, ako spočítať \(f\). To sa dá spraviť, tak, že dokopy na výpočet všetkých \(f\) spotrebujeme \(O(\ell)\) času, stačí však jednoduchšie riešenie pomocou intervalového stromu v čase \(O(\ell \log \ell)\), prípade pomocou multimnožiny s rovnakou zložitosťou.

Najskôr si do samostatného poľa uložíme na každú pozíciu rozdiel počtu dievčat a chlapcov od začiatku kruhu po danú pozíciu. Keď budeme chcieť zistiť \(f\), potrebujeme vedieť maximum intervalu od \(i\) po \(j\) v tomto poli, a od toho odpočítať hodnotu na pozícii \(i-1\).

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