defrag

Defrag

h2. Cerinţă

Cunoscând numărul de piste P şi de sectoare S al unui platan, numărul şi poziţia clusterilor ocupaţi, să se scrie un program care determină :

Cunoscând numărul de piste $P$ şi de sectoare $S$ al unui platan, numărul şi poziţia clusterilor ocupaţi, să se scrie un program care determină :

1. numărul de piste care au toţi clusterii liberi;
2. numărul *minim* de mutări de clusteri, pentru fiecare pistă în parte, astfel încât platanul să devină defragmentat.
h2. Date de intrare

Pe prima linie a fişierului de intrare _defrag.in_ se găseşte numărul natural V a cărui valoare poate fi doar 1 sau 2.
Pe a doua linie a fişierului de intrare se găsesc două numere naturale P şi S, separate printr-un spaţiu, cu semnificaţia din enunţ.
A treia linie conţine un număr natural C reprezentând numărul total de clusteri ocupaţi de pe platan, iar pe fiecare din următoarele C linii se găseşte câte o pereche de valori pi  şi si, 1 ≤ i ≤ C, separate printr-un spaţiu, reprezentând pista, respectiv sectorul unde se află fiecare cluster ocupat.

Pe prima linie a fişierului de intrare _defrag.in_ se găseşte numărul natural $V$ a cărui valoare poate fi doar $1$ sau $2$.
Pe a doua linie a fişierului de intrare se găsesc două numere naturale $P$ şi $S$, separate printr-un spaţiu, cu semnificaţia din enunţ.
A treia linie conţine un număr natural $C$ reprezentând numărul total de clusteri ocupaţi de pe platan, iar pe fiecare din următoarele $C$ linii se găseşte câte o pereche de valori $p{~i~}$  şi $s{~i~}$, $1 ≤ i ≤ C$, separate printr-un spaţiu, reprezentând pista, respectiv sectorul unde se află fiecare cluster ocupat.

h2. Date de ieşire
Fişierul de ieşire este _defrag.out._

Dacă valoarea lui V este 1 atunci fişierul de ieşire va conţine pe prima linie un număr natural ce reprezintă numărul de piste care au toţi clusterii liberi.
Dacă valoarea lui V este 2 atunci fişierul de ieşire va conţine pe prima linie P numere naturale notate  Mi, 1 ≤ i ≤ P,  separate prin câte un singur spaţiu, unde Mi reprezintă numărul minim de mutări de clusteri, dintre cei aflaţi pe pista i, astfel încât pe pista i clusterii ocupaţi să se găsească într-o ordine consecutivă.

Dacă valoarea lui $V$ este $1$ atunci fişierul de ieşire va conţine pe prima linie un număr natural ce reprezintă numărul de piste care au toţi clusterii liberi.
Dacă valoarea lui $V$ este $2$ atunci fişierul de ieşire va conţine pe prima linie $P$ numere naturale notate $M{~i~}$ , $1 ≤ i ≤ P$, separate prin câte un singur spaţiu, unde $M{~i~}$ reprezintă numărul minim de mutări de clusteri, dintre cei aflaţi pe pista $i$, astfel încât pe pista $i$ clusterii ocupaţi să se găsească într-o ordine consecutivă.

h2. Restricţii

* 1 ≤ P ≤ 100
* 1 ≤ S ≤ 360
* 1 ≤ C ≤ P*S
* pistele sunt numerotate de la 1 la P începând cu pista exterioară;
* sectoarele sunt numerotate de la 1 la S în sensul acelor de ceasornic începând cu sectorul 1;
* dacă o pistă are toţi clusterii liberi, atunci valoarea cerută la a doua cerinţă este 0;
* 20% din teste vor avea valoarea V = 1, iar 80% din teste vor avea valoarea V = 2.

* $1 ≤ P ≤ 100$
* $1 ≤ S ≤ 360$
* $1 ≤ C ≤ P*S$
* pistele sunt numerotate de la $1$ la $P$ începând cu pista exterioară;
* sectoarele sunt numerotate de la $1$ la $S$ în sensul acelor de ceasornic începând cu sectorul $1$;
* dacă o pistă are toţi clusterii liberi, atunci valoarea cerută la a doua cerinţă este $0$;
* $20%$ din teste vor avea valoarea $V = 1$, iar $80%$ din teste vor avea valoarea $V = 2$.

h2. Exemplu

h3. Explicaţie
În primul exemplu datele corespund figurilor anterioare :

V = 1, deci se rezolvă *NUMAI* prima cerinţă.

$V = 1$, deci se rezolvă *NUMAI* prima cerinţă.

* Numărul de piste P = 4 , numărul de sectoare S = 8
* Numărul total de clusteri ocupaţi este C = 10 (cei marcaţi cu negru)
* Pe prima pistă sunt 4 clusteri ocupaţi, în sectoarele 1, 3, 5 si 7.
* Pe a doua pistă sunt 2 clusteri ocupaţi, în sectoarele 2 şi 4.

* Numărul de piste $P = 4$ , numărul de sectoare $S = 8$
* Numărul total de clusteri ocupaţi este $C = 10$ (cei marcaţi cu negru)
* Pe prima pistă sunt $4$ clusteri ocupaţi, în sectoarele $1, 3, 5$ si $7$.
* Pe a doua pistă sunt $2$ clusteri ocupaţi, în sectoarele $2$ şi $4$.

* Pe a treia pistă nu sunt clusteri ocupaţi.

* Pe a patra pistă sunt 4 clusteri ocupaţi, în sectoarele 1, 5, 6 şi 8.

* Pe a patra pistă sunt $4$ clusteri ocupaţi, în sectoarele $1, 5, 6$ şi $8$.

O singură pistă are toţi clusterii liberi, pista numărul 3, deci valoarea cerută este 1;

O singură pistă are toţi clusterii liberi, pista numărul $3$, deci valoarea cerută este $1$;

În al doilea exemplu datele corespund figurilor anterioare :

V = 2, deci se rezolvă *NUMAI* a doua cerinţă.

$V = 2$, deci se rezolvă *NUMAI* a doua cerinţă.

* Pe prima pistă sunt necesare minim două mutări de clusteri pentru ca toţi clusterii ocupaţi să se găsească într-o ordine consecutivă, deci valoarea cerută este 2.
* Pe a doua pistă este suficientă o singură mutare de cluster, pentru ca toţi clusterii ocupaţi să se găsească într-o ordine consecutivă, deci valoarea cerută este 1.
* Pe a treia pistă nu sunt clusteri ocupaţi, deci valoarea cerută este 0.
* Pe a patra pistă este suficientă o singură mutare de cluster, pentru ca toţi clusterii ocupaţi să se găsească într-o ordine consecutivă, deci valoarea cerută este 1.

* Pe prima pistă sunt necesare minim două mutări de clusteri pentru ca toţi clusterii ocupaţi să se găsească într-o ordine consecutivă, deci valoarea cerută este $2$.
* Pe a doua pistă este suficientă o singură mutare de cluster, pentru ca toţi clusterii ocupaţi să se găsească într-o ordine consecutivă, deci valoarea cerută este $1$.
* Pe a treia pistă nu sunt clusteri ocupaţi, deci valoarea cerută este $0$.
* Pe a patra pistă este suficientă o singură mutare de cluster, pentru ca toţi clusterii ocupaţi să se găsească într-o ordine consecutivă, deci valoarea cerută este $1$.

== include(page="template/taskfooter" task_id="defrag") ==