Revizia anterioară Revizia următoare
| 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, 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.
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 grupuri din intrebarea 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 ≤ 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 ≤ 109
- pentru 30 de puncte: 1 ≤ N, K[i], Q ≤ 12, oricare ar fi 1 ≤ i ≤ Q
Exemplu
| aliniere.in | aliniere.out |
|---|---|
| 12 2 1 4 3 3 5 8 6 2 7 9 11 3 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 4 2 |
Explicaţie
- 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)
