Misiune
În clasă, copiii stau pe scaune dispuse în cerc. Așteaptă ceva. Din ochii lor strălucitori, putem simți că așteaptă ceva bun. Probabil că nu va fi o hârtie. Sunt zdrobiți cu nerăbdare și mulți sunt deja salivați. Asteapta vreo mancare? Pentru o mizerie? Sau așteaptă cea mai mare comoară dintre toate delicii, ciocolata însăși?
Da, profesorul va veni în curând în cameră și le va aduce ciocolată. Din păcate, ciocolata este doar 1, așa că copiii vor trebui să împartă ciocolata. Este posibil ca unii să nu reușească.
Ajutați profesorul să afle câți copii pot mânca din ciocolată.
Sarcina
Tabelul cu ciocolată este format din \ (r \) rânduri și \ (s \) coloane de cuburi de ciocolată. Profesorul începe predând ciocolata unui copil în cerc. Copilul rupe fie un rând, fie o coloană de ciocolată și îi dă restul copilului care stă în dreapta lui.
Băieții sunt vorace și ori de câte ori primesc ciocolată, se rup cât mai mult din piesă posibil. Deci, atunci când ciocolata are mai multe rânduri decât coloane, acestea rup o coloană, altfel rup un rând.
Fetele nu sunt atât de lacome și, de asemenea, vor să păstreze o linie subțire. Prin urmare, rupe cea mai mică piesă posibilă, de asemenea, un rând sau o coloană, dar aleg ce are mai puține cuburi de ciocolată.
Aflați câți copii le va lipsi ciocolata, dacă profesorul alege cât mai bine ce copil să înceapă. Copilul este numărat o singură dată, chiar dacă îi lipsește ciocolata de mai multe ori.
formatul de intrare
Prima linie conține numărul de clase \ (t \) în care această problemă trebuie rezolvată. Pe fiecare dintre următoarele linii \ (t \) există o descriere a unei clase constând din numerele \ (r \), \ (s \) și șirul \ (Z \) .
Ciocolata are dimensiunile cuburilor \ (r \ times s \). \ (Z \) este un șir format din literele „C” și „D” care descriu ce copii sunt băieți și care fete.
Literele „C” indică băieții și fetele „D”, cu copilul așezat cel mai aproape de tablă în prima poziție a șirului \ (Z \) și copilul așezat în dreapta copilului în a doua poziție, apoi copil care stă în dreapta celuilalt și așa mai departe. Primul copil din lanț stă, de asemenea, în dreapta ultimului copil.
Restricțiile privind dimensiunile de intrare sunt după cum urmează:
Numărul de rânduri și numărul de coloane din fiecare ciocolată este cel puțin \ (1 \) și cel mult \ (10 ^ 6 \). Există cel puțin \ (1 \) elevi și cel mult \ (10 ^ 6 \) elevi în fiecare clasă.
Numărul de clase este cel mult \ (10 ^ 6 \) și, în plus, există cel mult \ (10 ^ 7 \) studenți în toate clasele împreună. Toate ciocolatele împreună au cel mult \ (10 ^ 7 \) rânduri și cel mult \ (10 ^ 7 \) coloane.
În tabel puteți vedea limitele superioare ale numărului de clase \ (t \) și numărul de elevi dintr-o clasă \ (z \) și numărul de rânduri \ (r \) și coloane \ (r \) de o ciocolată în fiecare set de intrări.
| Maxim \ (t \) | \ (50 \) | \ (1 \, 000 \) | \ (10 ^ 6 \) | \ (10 \) | \ (10 ^ 6 \) |
| Maxim \ (z, r, s \) | \ (50 \) | \ (1 \, 000 \) | \ (20 \) | \ (10 ^ 6 \) | \ (10 ^ 6 \) |
Format de iesire
Scrieți linii \ (t \) pentru rezultat, pentru fiecare clasă scrieți câte copii pot mânca ciocolată dacă o împart în modul descris în sarcină.
Exemplu
Intrare:
Ieșire:
În clasa a III-a, fetele trebuie să mănânce mai întâi, pentru că băiatul mănâncă toată ciocolata care îi vine. În clasa a IV-a, ciocolata este atât de mare încât toată lumea o poate mânca. În clasa a V-a, copiii vor mânca în următoarea ordine: CCDDCDC. Astfel, dimensiunile ciocolatei vor fi (4.4), (4.3), (4.2), (3.2), (2.2), (2.1), (1.1), (0), 0) și toată lumea mănâncă.
Pentru că școlile au bani puțini.↩
Partea cheie a soluției este să putem răspunde rapid la o astfel de întrebare: „dacă am începe să împărțim ciocolată de la copilul \ (i \) -acest copil la \ (j \) -acel copil, ciocolata ar fi suficientă pentru ne?"
Și anume, dacă am ști acest lucru, am putea rezolva problema folosind așa-numita tehnică cu doi alergători. Luăm doi alergători și ne așezăm pe amândoi la începutul cercului. Alergătorii vor fi numiți Ivan și Jožo și vor fi în pozițiile \ (i \) și \ (j \). Ori de câte ori îi putem hrăni pe copii din poziția \ (i \) în poziția \ (j \), Jožo trece la următorul pătrat din cerc. În caz contrar, Ivan se mișcă. Rețineți că Ivan nu îl depășește niciodată pe Joža, deoarece putem hrăni zero copii. Algoritmul se termină atunci când Jožo înconjoară întregul cerc de două ori și soluția problemei va fi cea mai mare distanță posibilă a alergătorilor în timpul rulării algoritmului. Gândiți-vă de ce este așa.
Excepția este că, dacă răspunsul este mai mare decât numărul de copii, vom enumera doar numărul de copii.
Ambii alergători execută cel mult pași \ (2 \ ell \), unde \ (\ ell \) este dimensiunea cercului (lungimea șirului \ (Z \)), făcând algoritmul mult mai rapid decât dacă am testa toate \ (O (\ ell ^ 2) \) perechi \ ((i, j) \) .
Deci, de unde știi dacă o parte din copii poate fi hrănită?
Mai întâi întoarcem ciocolata astfel încât să fie cel puțin la fel de mare ca lată. Putem apoi păstra această proprietate pe tot parcursul consumului - băiatul mănâncă întotdeauna coloana și îngustează ciocolata. Dacă o fată primește ciocolată mai înaltă decât lată, mănâncă o linie. Cu toate acestea, dacă o fată mănâncă ciocolată la fel de înaltă ca lată, mănâncă un bar.
Să ne uităm la secțiunea copiilor de la \ (i \) la \ (j \). Imaginați-vă că copilul \ (i \) -te a fost primul care a mâncat ciocolată. Să notăm \ (c \) numărul de băieți din această secțiune, \ (d \) numărul de fete și \ (e \) numărul de fete care au mâncat o bară de ciocolată. Apoi, o ciocolată de dimensiuni \ (r \ times s \), unde \ ((r \ leq s) \) este suficientă pentru copii de la \ (i \) la \ (j \), dacă \ (e + c \ leq s \) și în același timp \ (de \ leq r \). Acest lucru este altfel același cu verificarea \ (e + c \ leq s \) și \ (c + d \ leq r + s \) .
Este ușor să găsești \ (c \) și \ (d \) pentru unele secțiuni ale unui cerc. Singura parte dificilă a acestei sarcini a fost de a afla eficient \ (e \) .
Rețineți că atunci când o fată este ciocolată după un băiat, cu siguranță nu contează pentru \ (e \). În mod similar, dacă avem \ (8 \) fete după \ (8 \) băieți. Intuitiv, pentru a fi mari \ (e \), avem nevoie de multe fete care să mănânce ciocolată fără ca mulți băieți să mănânce ciocolată în fața lor. Mai exact, să luăm secvențele copiilor de la poziția \ (i \), la toate pozițiile posibile \ (k \), \ (k \ leq j \), în fiecare secvență numărăm fetele și băieții și să \ (f \) să fie cea mai mare dintre diferențe numărul de fete minus numărul de băieți. Apoi \ (e = max (0, (s-r + f + 1) // 2) \). (Gândiți-vă de ce.)
Deci, trebuie doar să ne dăm seama cum să calculăm \ (f \). Acest lucru se poate face consumând \ (O (\ ell) \) timp împreună pentru a calcula toate \ (f \), dar este suficientă o soluție mai simplă folosind un arbore de intervale în timp \ (O (\ ell \ log \ ell) \ \), folosind un multiset de aceeași complexitate.
În primul rând, stocăm diferența în numărul de fete și băieți de la începutul cercului până la poziția dată într-un câmp separat pentru fiecare poziție. Pentru a găsi \ (f \), trebuie să cunoaștem maximul intervalului de la \ (i \) la \ (j \) în acest câmp și să scădem valoarea la poziția \ (i-1 \) .
Discuţie
Aici puteți discuta în mod liber soluția, puteți partaja fragmentele de cod și așa mai departe.
Trebuie să fiți conectat pentru a adăuga comentarii.