strips

Time limit: 0.1s Memory limit: 5MB Input: strips.in Output: strips.out

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 NN cm, pe care sunt marcate poziţii de lungime 11 cm. Poziţiile sunt numerotate pe tablă de la 00 la N1N - 1, poziţia 00 fiind marcată la începutul tablei (capătul din stânga), iar poziţia N1N - 1 fiind marcată la sfârşitul tablei (capătul din dreapta).

La începutul jocului fiecare jucător are NrNr benzi colorate, toate de aceeaşi lungime LL 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 11 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 LL 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 CC care reprezintă cerinţa care urmează a fi rezolvată (11 sau 22). Pe cea de-a doua linie se află trei numere naturale separate prin câte un spaţiu N Nr LN \ 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 rezArezA și rezBrezB, separate printr-un singur spaţiu. Dacă C=1C = 1 atunci rezArezA este numărul de puncte de penalizare acumulate de Ana, iar rezBrezB numărul de puncte de penalizare acumulate de Bogdan. Dacă C=2C = 2 atunci rezArezA este lungimea maximă a unei zone de culoare roşie la sfârşitul jocului, iar rezBrezB este lungimea maximă a unei zone de culoare verde la sfârşitul jocului.

Restricții și precizări

  • 1N1 000 000 0001 \leq N \leq 1 \ 000 \ 000 \ 000;
  • 1Nr50 0001 \leq Nr \leq 50 \ 000;
  • 1L20 0001 \leq L \leq 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 5 000\leq 5 \ 000.
  • Poziţiile sunt numere naturale mai mici decât NN.
  • Fiindcă sunt începători, Ana şi Bogdan încă nu joacă optim.
  • Pentru teste valorând 5050 de puncte cerinţa este 1.
  • Pentru teste valorând 4040 de puncte 1N1 000 0001 \leq N \leq 1 \ 000 \ 000; 1L1 0001 \leq L \leq 1 \ 000; şi 1Nr1 0001 \leq Nr \leq 1 \ 000.

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 2020 de cm, poziţiile fiind numerotate de la 00 la 1919. Jucătorii au fiecare câte 44 benzi de lungime 33.

La prima mutare Ana aplică o bandă roşie peste poziţiile 9,10,119, 10, 11.
La a doua mutare Bogdan aplică o bandă verde peste poziţiile 15,16,1715, 16, 17.
La a treia mutare Ana aplică o bandă roşie peste poziţiile 2,3,42, 3, 4.
La a patra mutare Bogdan aplică o bandă verde peste poziţiile 13,14,1513, 14, 15.
La a cincea mutare Ana aplică o bandă roşie peste poziţiile 5,6,75, 6, 7.
La a şasea mutare Bogdan aplică o bandă verde peste poziţiile 17,18,1917, 18, 19.
La a şaptea mutare Ana aplică o bandă roşie peste poziţiile 0,1,20, 1, 2.
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 11 punct de penalizare).
Tabla de joc la finalul jocului va arăta astfel:

Log in or sign up to be able to send submissions!