| Fişierul intrare/ieşire: | aliniere.in, aliniere.out | Sursă | FMI No Stress 9 |
| Autor | Mihai-Dragos Preda | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
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.
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.
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ Q ≤ 10 000
- 1 ≤ K i ≤ 1000, oricare ar fi 1 ≤ i ≤ Q
- 1 ≤ inaltime elev ≤ 109
- 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
Exemplu
| aliniere.in | aliniere.out |
|---|---|
| 12 9 2 10 7 2 14 6 6 4 12 3 3 3 6 1 4 5 7 9 10 3 3 4 9 3 1 5 10 | 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 |
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 intrebare exista 7 grupuri: (9 2) (10 7 2) (14) (6 6) (4 12) (3) (3)
