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
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.
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 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.
Date de ieşire
Fişierul de ieşire aliniere.out va contine Q numere, al i-ulea numar reprezentand numarul minim de secvente eliminate din impartirea i.
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ Q ≤ 1000
- 1 ≤ K[i] ≤ 1000, oricare ar fi 1 ≤ i ≤ Q
- 1 ≤ v[i] ≤ 109, oricare ar fi 1 ≤ i ≤ N
- pentru 30 de puncte: 1 ≤ v[i] ≤ 106, oricare ar fi 1 ≤ i ≤ N
- pentru alte 30 de puncte secventele oricarei impartiri sunt disjuncte
- pentru 10 puncte dintre ele: 1 ≤ K[i] ≤ 50, oricare ar fi 1 ≤ i ≤ Q
- pentru alte 20 de puncte: 1 ≤ N, K, Q ≤ 15
- elementele vectorului si implicit capetele secventelor sunt indexate de la 0
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)
