Fișierul intrare/ieșire	strips.in, strips.out	Sursă	OJI 2022 clasa a 8-a
Autor	Emanuela Cerchez	Adăugată de	Mircea Rebengiuc • mircea_007
Timp de execuție pe test	0.05 sec	Limită de memorie	5120 KB
Scorul tău	N/A	Dificultate	4.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Strips (clasa a 8-a)

Ana și Bogdan au inventat un nou joc, pe care l-au denumit Strips. Este un joc de strategie, dar și de antrenare a memoriei, deoarece se joacă pe o tablă care nu este vizibilă pentru cei doi jucători în timpul jocului. Tabla de joc este o bandă albă de lungime N cm, pe care sunt marcate poziții de lungime 1 cm. Pozițiile sunt numerotate pe tablă de la 0 la N − 1, poziția 0 fiind marcată la începutul tablei (capătul din stânga), iar poziția N − 1 fiind marcată la sfârșitul tablei (capătul din dreapta). La începutul jocului fiecare jucător are Nr benzi colorate, toate de aceeași lungime L cm. Benzile Anei sunt de culoare roșie, iar benzile lui Bogdan sunt de culoare verde. Jucătorii mută alternativ, prima la mutare fiind Ana. La o mutare, jucătorul care este la rând alege o poziție de pe tabla de joc și dacă poziția este validă, pe tabla de joc va fi plasată o bandă a jucătorului respectiv, cu capătul din stânga în poziția aleasă. Dacă poziția nu este validă, mutarea nu va fi executată, iar jucătorul respectiv va primi 1 punct de penalizare și pierde banda care ar fi trebuit plasată pe tablă la poziția respectivă (aceasta este eliminată din joc). O poziție este considerată validă, dacă pe tabla de joc poate fi plasată o bandă de lungime L cu capătul din stânga al benzii fixat la poziția specificată, astfel încât banda să fie integral pe tabla de joc, fără a se suprapune sau a se atinge cu o zonă de pe bandă colorată în culoarea adversarului. Jocul se termină când jucătorii nu mai au benzi. Fiecare jucător are ca scop să obțină o zonă pe bandă de lungime cât mai mare colorată în culoarea sa. O zonă de pe bandă este constituită din poziții consecutive, colorate cu aceeași culoare.

Cerințe

Scrieți un program care citește lungimea tablei de joc, numărul de benzi colorate pe care le are fiecare jucător la începutul jocului, lungimea benzilor, precum și pozițiile specificate de jucători pe parcursul jocului și rezolvă următoarele două cerințe:

1. determină numărul de puncte de penalizare pentru fiecare dintre cei doi jucători;
2. determină pentru fiecare jucător care este lungimea maximă a unei zone de pe tabla de joc colorată în culoarea sa la sfârșitul jocului.

Date de intrare

Fișierul de intrare strips.in conține pe prima linie un număr natural C care reprezintă cerința care urmează a fi rezolvată (1 sau 2). Pe cea de-a doua linie se află trei numere naturale separate prin câte un spațiu N Nr L, cu semnificația din enunț. Celelalte linii ale fișierului de intrare conțin în ordine pozițiile specificate de jucători pe parcursul jocului, câte o poziție pe o linie.

Date de ieșire

Fișierul de ieșire strips.out va conține o singură linie pe care vor fi scrise două numere naturale rezA rezB, separate printr-un singur spațiu.

• Dacă C = 1 atunci rezA este numărul de puncte de penalizare acumulate de Ana, iar rezB numărul de puncte de penalizare acumulate de Bogdan.
• Dacă C = 2 atunci rezA este lungimea maximă a unei zone de culoare roșie la sfârșitul jocului, iar rezB este lungimea maximă a unei zone de culoare verde la sfârșitul jocului.

Restricții

• 1 ≤ N ≤ 10⁹
• 1 ≤ Nr ≤ 50 000
• 1 ≤ L ≤ 20 000
• Se garantează că pentru datele de test, la finalul jocului, pentru fiecare dintre cei doi jucători numărul de zone disjuncte de pe tabla de joc colorate în culoarea jucătorului respectiv este ≤ 5000.
• Pozițiile sunt numere naturale mai mici decât N.
• Fiindcă sunt începători, Ana și Bogdan încă nu joacă optim.

Exemplu

Explicație

...