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:

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, nu isi da seama exact care sunt grupurile 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.

h2. Restricţii
* 1 ≤ N ≤ 100 000

* 1 ≤ Q ≤ 10 000
* 1 ≤ K ~i~ ≤ 1000, oricare ar fi 1 ≤ i ≤ Q

* 1 ≤ Q ≤ 1000
* 1 ≤ K[i] ≤ 1000, oricare ar fi 1 ≤ i ≤ Q
* Toti cei Q vectori “x” sunt sortati strict crescator si au elementele < N

* 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

* pentru 30 de puncte: 1 ≤ N, K[i], Q ≤ 12, oricare ar fi 1 ≤ i ≤ Q

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") ==