Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-03-03 22:15:32.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:aliniere.in, aliniere.outSursăFMI No Stress 9
AutorMihai-Dragos PredaAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.3 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/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[i], Q ≤ 12, oricare ar fi 1 ≤ i ≤ Q
  • elementele vectorului si implicit capetele secventelor sunt indexate de la 0

Exemplu

aliniere.inaliniere.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)
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?