Fişierul intrare/ieşire:bisortare.in, bisortare.outSursăONSEPI, clasele 11-12
AutorAdrian PanaeteAdăugată deNicolaalexandraNicola Alexandra Mihaela Nicolaalexandra
Timp execuţie pe test0.25 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bisortare

Pentru o permutare p1, p2, . . . , pN a numerelor de la 1 la N şi o poziţie K, ( 1 ≤ K ≤ N ), notăm cu BestK numărul minim de interschimbări (a valori situate pe poziţii consecutive) necesare pentru a se obţine o permutare descrescătoare de la poziţia 1 la poziţia K şi crescătoare de la poziţia K la poziţia N. Se dă o permutare. Se cere să se rezolve una dintre următoarele două cerinţe:
1. Pentru o poziţie K dată să se calculeze BestK.
2. Pentru toate poziţiile K de la 1 la N să se calculeze BestK.

Date de intrare

Fişierul de intrare bisortare.in va conţine pe prima linie trei numere întregi separate prin spaţiu C, N şi K. C reprezintă cerinţa şi poate lua valoarea 1 sau valoarea 2. N reprezintă ordinul (lungimea) permutării. Dacă C = 1 atunci 1 ≤ K ≤ N reprezintă poziţia pentru care trebuie calculat BestK. Dacă C = 2 atunci K = 0 şi BestK trebuie calculat pentru toate poziţiile de la 1 la N. A doua linie conţine N numere întregi separate prin spaţiu p1, p2, . . . , pN reprezentând elementele permutării.

Date de ieşire

În fişierul de ieşire bisortare.out se va afla raspunsul după cum urmează. Dacă C = 1 se va rezolva cerinţa 1. În acest caz pe prima linie se va afişa un singur număr: BestK. Dacă C = 2 se va rezolva cerinţa 2. În acest caz pe prima linie se vor afişa N numere separate prin spaţiu: Best1, Best2, . . . , BestN

Restricţii

  • 1 ≤ C ≤ 2
  • 1 ≤ N ≤ 100000
  • Dacă C = 1, atunci 1 ≤ K ≤ N
  • Dacă C = 2, atunci K = 0
  • 1 ≤ pi ≤ N, pentru orice i cu 1 ≤ i ≤ N şi sunt distincte

Subtaskuri

  • Subtask 1 (3 puncte)
    • C = 1, N ≤ 3000, K = 1
  • Subtask 2 (3 puncte)
    • C = 1, N ≤ 100000, K = 1
  • Subtask 3 (3 puncte)
    • C = 1, N ≤ 3000, K = N
  • Subtask 4 (3 puncte)
    • C = 1, N ≤ 100 000, K = N
  • Subtask 5 (9 puncte)
    • C = 2, N ≤ 8
  • Subtask 6 (11 puncte)
    • C = 2, N ≤ 18
  • Subtask 7 (13 puncte)
    • C = 2, N ≤ 60
  • Subtask 8 (14 puncte)
    • C = 2, N ≤ 200
  • Subtask 9 (15 puncte)
    • C = 2, N ≤ 3000
  • Subtask 10 (26 puncte)
    • C = 2, N ≤ 100000

Exemplu

bisortare.inbisortare.out
1 7 1
1 2 5 6 7 4 3
7
2 7 0
2 5 1 6 7 4 3
9 7 6 7 8 10 12
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?