Feladat
Az osztályteremben a gyerekek körbe rendezett székeken ülnek. Várnak valamire. Sugárzó szemükből megérezhetjük, hogy valami jóra várnak. Valószínűleg nem papír lesz. Lelkesen összetörik őket, és sokan már nyálasak is. Várnak valamilyen ételt? Rendetlenségért? Vagy várják az összes csemege legnagyobb kincsét, magát a csokoládét?
Igen, a tanár hamarosan bejön a szobába, és csokoládét hoz nekik. Sajnos a csokoládé csak egy 1, ezért a gyerekeknek megosztaniuk kell a csokoládét. Egyeseknek nem is sikerülhet.
Segítsen a tanárnak kideríteni, hány gyermek ehet csokoládéból.
A feladat
A csokoládéasztal \ (r \) sorokból és \ (s \) oszlopokból áll. A tanár azzal kezdi, hogy körben átadja a csokoládét egy gyermeknek. A gyermek letör egy csokoládé sort vagy oszlopot, a többit a tőle jobbra ülő gyermeknek nyújtja.
A fiúk falatkák, és amikor csokoládét kapnak, a lehető legtöbbet letörik a darabról. Tehát, ha a csokoládénak több sora van, mint oszlopának, akkor egy oszlopot törnek, különben egy sort.
A lányok nem annyira mohók, és vékony vonalat is szeretnének tartani. Ezért letörik a lehető legkisebb darabot, szintén egy sort vagy egy oszlopot, de azt választják, amiben kevesebb csokoládé kocka van.
Tudja meg, hány gyermek hiányolja a csokoládét, ha a tanár kiválasztja, melyik gyermekkel kezdjen. A gyermeket csak egyszer számolják, még akkor is, ha többször hiányzik a csokoládé.
Beviteli formátum
Az első sor tartalmazza a \ (t \) osztályok számát, amelyekben ezt a problémát meg kell oldani. A következő \ (t \) sorok mindegyikén található egy osztály leírása, amely a \ (r \), \ (s \) számokból és a \ (Z \) karakterláncból áll. .
A csokoládé méretei (r \ -szeresek s \) kockák. \ (Z \) egy "C" és "D" betűkből álló karakterlánc, amely leírja, hogy mely gyerekek fiúk és melyik lányok.
A "C" betűk a fiúkat és a "D" lányokat jelölik, a gyermek a táblához legközelebb ülve a húr első helyzetében \ (Z \), a gyermek pedig a gyermek jobb oldalán ül a második pozícióban, majd a a másik jobb oldalán ülő gyermek, és így tovább. A lánc első gyermeke az utolsó gyermektől jobbra is ül.
A bemeneti méretre vonatkozó korlátozások a következők:
Az egyes csokoládék sorainak és oszlopainak száma legalább \ (1 \) és legfeljebb \ (10 ^ 6 \). Minden osztályban legalább \ (1 \) és legfeljebb \ (10 ^ 6 \) tanuló van.
Az osztályok száma legfeljebb \ (10 ^ 6 \), és ezen felül az összes osztályban legfeljebb \ (10 ^ 7 \) tanuló van. Az összes csokoládé együtt legfeljebb \ (10 ^ 7 \) sorral és legfeljebb \ (10 ^ 7 \) oszloppal rendelkezik.
A táblázatban láthatja az osztályok számának felső határát (t) és az egy osztály tanulóinak számát (z \), valamint a sorok számát (r \) és oszlopait \ (r \). egy csokoládé minden bemeneti készletben.
| Maximum \ (t \) | \ (50 \) | \ (1 \, 000 \) | \ (10 ^ 6 \) | \ (10 \) | \ (10 ^ 6 \) |
| Maximum \ (z, r, s \) | \ (50 \) | \ (1 \, 000 \) | \ (20 \) | \ (10 ^ 6 \) | \ (10 ^ 6 \) |
Kimeneti formátum
Írjon \ (t \) sorokat a kimenethez, minden osztály számára írja be, hány gyerek ehet csokoládét, ha elosztják a feladatban leírt módon.
Példa
Bemenet:
Kimenet:
Harmadik osztályban a lányoknak kell először enniük, mert a fiú megeszi az összes csokoládét, ami hozzá kerül. Negyedik osztályban a csokoládé akkora, hogy mindenki megeheti. Az ötödik osztályban a gyerekek a következő sorrendben étkeznek: CCDDCDC. Így a csokoládé méretei (4.4), (4.3), (4.2), (3.2), (2.2), (2.1), (1.1), (0), 0) lesznek, és mindenki eszik.
Mivel az iskoláknak kevés a pénzük.↩
A megoldás legfontosabb része az, hogy gyorsan válaszolhassunk egy ilyen kérdésre: "ha csokoládét kezdenénk osztogatni az \ (i \) -től a gyerektől a \ (j \) -ig, akkor a csokoládé elég lenne minket?"
Ugyanis, ha ezt tudnánk, úgynevezett kétfutásos technikával megoldhatnánk a problémát. Két futót veszünk, és mindkettőt a kör elején üljük. A futókat Ivannak és Jožo-nak hívják, és \ (i \) és \ (j \) pozíciókban lesznek. Amikor a gyermekeket etethetjük \ (i \) helyzetből \ (j \) helyzetbe, Jožo a kör következő négyzetére lép. Különben Ivan megmozdul. Ne feledje, hogy Ivan soha nem éri el Jožát, mert nulla gyermeket tudunk táplálni. Az algoritmus akkor ér véget, amikor Jožo kétszer megkerüli az egész kört, és a probléma megoldása a futók lehető legnagyobb távolsága lesz az algoritmus futtatása során. Gondoljon bele, miért van ez így.
A kivétel az, hogy ha a válasz nagyobb, mint a gyermekek száma, akkor csak a gyermekek számát fogjuk felsorolni.
Mindkét futó legfeljebb \ (2 \ ell \) lépést hajt végre, ahol \ (\ ell \) a kör mérete (string hossza \ (Z \)), ami az algoritmust lényegesen gyorsabbá teszi, mintha az összes \ (O (\ ell ^ 2) \) párok \ ((i, j) \) .
Tehát hogyan lehet megtudni, hogy a gyermekek egy részét meg lehet-e etetni?
Először megforgatjuk a csokoládét, hogy legalább olyan magas legyen, mint széles. Ezután megőrizhetjük ezt a tulajdonságot a fogyasztás során - a fiú mindig megeszi az oszlopot, és beszűkíti a csokoládét. Ha egy lány magasabb csokoládét kap, mint szélesebb, eszik egy sort. Ha azonban egy lány olyan magas csokoládét eszik, mint széles, akkor egy rudat eszik.
Nézzük meg a gyermekek szakaszát \ (i \) - \ (j \). Képzelje el, hogy az \ (i \) -te gyermek elsőként evett csokoládét. Legyen \ (c \) a fiúk száma ebben a szakaszban, \ (d \) a lányok száma és \ (e \) azoknak a lányoknak a száma, akik ettek egy tábla csokoládét. Ezután egy \ (r \ szorzat s \) dimenziós csokoládé, ahol \ ((r \ leq s) \) elegendő a \ (i \) - \ (j \) gyermekek számára, ha \ (e + c \ leq s \) és egyúttal \ (de \ leq r \). Ez egyébként megegyezik a \ (e + c \ leq s \) és a (c + d \ leq r + s \) ellenőrzésével .
A (z) \ (c \) és a (d) a kör egyes szakaszaihoz könnyű megtalálni. A feladat egyetlen nehéz része az volt, hogy hatékonyan megtudja \ (e \) .
Ne feledje, hogy amikor egy lány csokis egy fiú után, az biztosan nem számít bele az \ (e \) értékbe. Hasonlóképpen, ha \ (8 \) lányok vannak \ (8 \) fiúk után. Intuitív módon ahhoz, hogy nagyok legyünk \ (e \), sok lányra van szükségünk csokoládéfogyasztáshoz, anélkül, hogy sok fiú csokoládét eszne előttük. Pontosabban, vigyük a gyermekek szekvenciáit az \ (i \) pozícióból az összes lehetséges helyzetbe \ (k \), \ (k \ leq j \), mindegyik sorrendben számoljuk meg a lányokat és fiúkat, és engedjük \ (f \) legyen a legnagyobb a lányok és a fiúk számának különbségei között. Ezután \ (e = max (0, (s-r + f + 1) // 2) \). (Gondolj arra, miért.)
Tehát csak ki kell találnunk a \ (f \) kiszámításának módját. Ezt úgy tehetjük meg, hogy \ (O (\ ell) \) időt együttesen felhasználunk az összes \ (f \) kiszámításához, de elég egy egyszerűbb megoldás, ha intervallumfát használunk az időben \ (O (\ ell \ log \ ell) \ \), ugyanolyan összetettségű multisetet használva.
Először a lányok és a fiúk számának különbségét a kör elejétől az adott pozícióig külön pozícióban tároljuk. A (z) \ (f \) megtudásához meg kell ismernünk a (z) \ (i \) és \ (j \) közötti intervallum maximumát ebben a mezőben, és levonni az \ (i-1 \) pozíció értékét .
Vita
Itt szabadon megvitathatja a megoldást, megoszthatja kódjait és így tovább.
Megjegyzések hozzáadásához be kell jelentkeznie.