Î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.↩
Încărcare
Trebuie să fiți conectat pentru a încărca
Întrebări și discuții
La sfârșitul rundei, veți avea ocazia să discutați soluții într-o discuție sub o soluție model.