Aliniere

aliniere

== include(page="template/taskheader" task_id="aliniere") ==

Doru, profesor de sport, are acum ora cu o clasa de a 9a. Fiind boboci, acestia au o prezenta destul de ridicata, mai exact N. Domn professor ii pune pe elevi sa se alinieze crescator dupa inaltime, insa observa ca acestia s-au aranjat intr-o linie dupa grupurile de prietenii formate. **Elevii nu vor in niciun fel sa isi paraseasca grupul si nici sa schimbe ordinea din interiorul grupului**. Deoarece vorbeste toata lumea cu toata lumea, Doru, algoritmician in timpul liber, observa ca fiecare grup formeaza o secventa si nu isi da seama exact care sunt ele asa ca ii numeroteaza pe elevi incepand cu 0 de la stanga la dreapta isi pune Q intrebari de forma:
“Daca grupurile sunt (0, 1, … , x ~0~ ), (x ~0~ +1, … , x ~1~ ), (x ~1~ +1, … , x ~2~ ), … , (x ~k-1~ +1, … , n-1), care este numarul minim de grupuri pe care trebuie sa il dau afara pentru a putea alinia elevii crescator?”
Ajutati-l pe Doru sa raspunda la intrebari.

Se da un vector cu N elemente si Q impartiri ale acestuia in secvente (nu neaparat disjuncte).
Pentru fiecare impartire data se cere sa se afiseze numarul minim de secvente ce trebuie eliminate astfel incat cele ramase sa poata fi reordonate pentru a obtine un vector sortat crescator.

h2. Date de intrare

Fişierul de intrare aliniere.in contine pe prima linie numarul natural N. Pe a doua linie se află N numere naturale, separate prin câte un spaţiu, reprezentând inaltimile elevilor. Pe a treia linie se afla numarul natural Q. Pe fiecare linie i din urmatoarele Q se afla un numar natural K ~i~ ce reprezinta numarul de elemente din vectorul x al intrebarii i, iar apoi K ~i~ numere ce reprezinta vectorul x.

Fişierul de intrare $aliniere.in$ contine pe prima linie numarul natural N. Pe a doua linie se află N numere naturale, separate prin câte un spaţiu, reprezentând vectorul. Pe a treia linie se afla numarul natural Q. Pe fiecare linie i din urmatoarele Q se afla un numar natural K[i] ce reprezinta numarul de secvente din impartirea i, iar apoi K[i] perechi de numere reprezentand capetele secventelor.

h2. Date de ieşire

Fişierul de ieşire aliniere.out va contine Q numere, al i-ulea numar reprezentand raspunsul pentru intrebarea numarul i.

Fişierul de ieşire $aliniere.out$ va contine Q numere, al i-ulea numar reprezentand numarul minim de secvente eliminate din impartirea i.

h2. Restricţii

* 1 ≤ N ≤ 100 000
* 1 ≤ Q ≤ 10 000
* 1 ≤ K ~i~ ≤ 1000, oricare ar fi 1 ≤ i ≤ Q
* 1 ≤ inaltime elev ≤ 10^9^
* Toti cei Q vectori “x” sunt sortati strict crescator si au elementele < N-1
* Fiecare dintre cele k+1 grupuri formeaza o secventa, iar elevii trebuie sortati schimband doar ordinea grupurilor
* Daca eliminam toate grupurile, se considera ca am obtinut un vector sortat
* pentru 30 de puncte: 1 ≤ N, K ~i~, Q ≤ 12, oricare ar fi 1 ≤ i ≤ Q
* pentru alte 30 de puncte: 1 ≤ N ≤ 1000 si 1 ≤ K ~i~, Q ≤ 100, oricare ar fi 1 ≤ i ≤ Q

* 1 ≤ N ≤ 100 000
* 1 ≤ Q ≤ 1000
* 1 ≤ K[i] ≤ 1000, oricare ar fi 1 ≤ i ≤ Q
* 1 ≤ v[i] ≤ $10^9^$, oricare ar fi 1 ≤ i ≤ N
* pentru 30 de puncte secventele oricarei impartiri sunt disjuncte
** pentru 10 puncte dintre ele: 1 ≤ N, K, Q ≤ 200
* pentru alte 30 de puncte: 1 ≤ N, K[i], Q ≤ 12, oricare ar fi 1 ≤ i ≤ Q
 
* elementele vectorului si implicit capetele secventelor sunt **indexate de la 0**

h2. Exemplu
table(example). |_. aliniere.in |_. aliniere.out |
| 12

9 2 10 7 2 14 6 6 4 12 3 3

2 1 4 3 3 5 8 6 2 7 9 11

3

6 1 4 5 7 9 10
3 3 4 9
3 1 5 10

6 2 2 1 2 3 3 3 6 8 9 10 11
5 0 2 2 3 4 6 8 10 9 11
4 0 2 3 5 7 9 11 11

| 3

2
3
|
| 30
11 2 4 5 5 8 9 10 10 10 2 13 13 14 14 16 16 28 18 19 20 21 22 23 25 26 26 27 27 17
10
6 3 9 10 13 14 23
4 8 9 11 13
6 4 10 17 24 25 26
6 1 8 17 24 26 28
3 14 18 26
6 11 13 14 19 20 21
5 1 2 9 18 22
5 2 9 12 15 20
4 5 6 21 26
6 3 7 13 19 23 24
| 3
3

4
2

3
3
3
4
3
4

|
h3. Explicaţie

* Primul exemplu:
** Pentru prima intrebare exista 7 grupuri: (9 2) (10 7 2) (14) (6 6) (4 12) (3) (3)
Daca eliminam primul, al doilea si al cincilea grup, obtinem grupurile: (14) (6 6) (3) (3). Schimband ordinea lor, obtinem vectorul sortat: 3 3 6 6 14
** Pentru a doua intrebare sunt grupurile: (9 2 10 7) (2) (14 6 6 4 12) (3 3)
Putem pastra doar al doilea si ultimul grup: 2 3 3
** Pentru a treia intrebare singura varianta este sa eliminam tot in afara de ultimul grup. Astfel obtinem vectorul: 3

* Pentru prima impartire avem 6 secvente: (4), (1, 4), (3), (3, 3, 5, 8), (2, 7), (9, 11)
Daca eliminam a doua, a patra si a cincea secventa raman secventele: (4), (3), (9, 11) ce pot fi reordonate pentru a obtine vectorul crescator (3 4 9 11)
O solutie alternativa ar fi eliminarea secventelor (3), (3, 3, 5, 8), (2, 7) pentru a obtine vectorul (1 4 4 9 11)
 
* Pentru a doua impartire avem 5 secvente: (2, 1, 4), (4, 3), (3, 5, 8), (2, 7, 9), (7, 9, 11)
Daca eliminam primele 4 secvente, obtinem vectorul sortat (7 9 11), format doar din ultima secventa.
 
* Pentru a treia impartire avem 4 secvente: (2, 1, 4), (3, 5), (9, 2, 7, 9), (11)
Putem elimina prima si a treia secventa pentru a obtine vectorul (3 5 11)

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