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 cm, pe care sunt marcate poziţii de lungime cm. Poziţiile sunt numerotate pe tablă de la la , poziţia fiind marcată la începutul tablei (capătul din stânga), iar poziţia fiind marcată la sfârşitul tablei (capătul din dreapta).
La începutul jocului fiecare jucător are benzi colorate, toate de aceeaşi lungime 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 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 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ță
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:
- determină numărul de puncte de penalizare pentru fiecare dintre cei doi jucători;
- 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 care reprezintă cerinţa care urmează a fi rezolvată ( sau ). Pe cea de-a doua linie se află trei numere naturale separate prin câte un spaţiu , 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 și , separate printr-un singur spaţiu. Dacă atunci este numărul de puncte de penalizare acumulate de Ana, iar numărul de puncte de penalizare acumulate de Bogdan. Dacă atunci este lungimea maximă a unei zone de culoare roşie la sfârşitul jocului, iar este lungimea maximă a unei zone de culoare verde la sfârşitul jocului.
Restricții și precizări
- ;
- ;
- ;
- 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 .
- Poziţiile sunt numere naturale mai mici decât .
- Fiindcă sunt începători, Ana şi Bogdan încă nu joacă optim.
- Pentru teste valorând de puncte cerinţa este 1.
- Pentru teste valorând de puncte ; ; şi .
Exemplul 1
strips.in
1
20 4 3
9
15
2
13
5
17
0
12
strips.out
0 1
Exemplul 2
strips.in
2
20 4 3
9
15
2
13
5
17
0
12
strips.out
8 7
Explicație
Tabla de joc are de cm, poziţiile fiind numerotate de la la . Jucătorii au fiecare câte benzi de lungime .
La prima mutare Ana aplică o bandă roşie peste poziţiile .
La a doua mutare Bogdan aplică o bandă verde peste poziţiile .
La a treia mutare Ana aplică o bandă roşie peste poziţiile .
La a patra mutare Bogdan aplică o bandă verde peste poziţiile .
La a cincea mutare Ana aplică o bandă roşie peste poziţiile .
La a şasea mutare Bogdan aplică o bandă verde peste poziţiile .
La a şaptea mutare Ana aplică o bandă roşie peste poziţiile .
La a opta mutare Bogdan a ales o poziţie invalidă (pentru că atinge o zonă de culoare roşie), ca urmare mutarea nu va fi executată (va avea punct de penalizare).
Tabla de joc la finalul jocului va arăta astfel:
