Fişierul intrare/ieşire:risc2.in, risc2.outSursăONI 2015, clasa a 9-a
AutorConstantin GalatanAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test0.03 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Risc2

Pentru a participa la un concert, n persoane s-au aşezat la coadă pe un singur rând în aşteptarea deschiderii casei de bilete. Înălţimile celor n persoane sunt toate distincte. Pe baza acestei informaţii cruciale, agenţii de securitate au decis ca din motive de ... securitate, ordinea persoanelor care aşteaptă la coadă trebuie schimbată în funcţie de înălţimile lor.
Astfel, agentii de pază vor alege, pe rând, câte o persoană şi o vor trimite la sfârşitul rândului. După fiecare operaţie de tipul acesta, să-i spunem “de mutare”, rândul se restrânge, ocupându-se poziţia rămasă liberă. Strategia agenţilor de pază este aceasta: la terminarea tuturor operaţiilor de mutare, riscul minim de securitate se obţine dacă toate persoanele aflate în dreapta persoanei celei mai înalte vor fi mai înalte decât cele aflate în stânga persoanei cele mai înalte. În plus, înalţimile persoanelor vor fi crescătoare până la poziţia k a persoanei celei mai înalte şi descrescătoare după poziţia k.
Mai exact: dacă h 1, h 2, …, h n sunt înălţimile persoanelor după finalizarea operaţiilor de mutare, atunci: există o poziţie k, cu 1 ≤ k ≤ n astfel încât h 1 < h 2 < ... h k-1 < h k > h k+1 > … > h n-1 > h n şi în plus h i < h j pentru oricare i < k şi k < j.
Deoarece o asemenea logică este greu de combătut, iar agenţii nu au aerul că vor să glumească, persoanele care aşteaptă la coadă vor accepta toate mutările impuse de către aceştia.

Cerinte

Cunoscând numărul de persoane n şi înălţimile h 1, h 2, …, h n ale acestora să se scrie un program care determină :
1. Poziţia persoanei celei mai înalte în rândul iniţial, în cazul în care nu sunt necesare operaţii de mutare.
2. Numărul minim de mutări necesare pentru ca rândul de persoane să prezinte un risc minim de securitate.

Date de intrare

Pe prima linie a fişierului de intrare risc2.in se găseşte numărul natural p a cărui valoare poate fi doar 1 sau 2.
Pe a doua linie a fişierului de intrare se află numărul natural n cu semnificaţia din enunţ.
Pe a treia linie se găsesc n numere naturale, distincte: h 1, h 2, …, h n, separate prin câte un singur spaţiu, reprezentând înălţimile persoanelor.

Date de ieşire

Fişierul de ieşire este risc2.out.

  • Dacă valoarea lui p este 1 atunci se va rezolva numai cerinţa 1. În acest caz, fişierul de ieşire va conţine pe prima linie un număr natural poz ce reprezintă poziţia persoanei celei mai înalte în rândul iniţial. Dacă rândul iniţial nu respectă condiţiile de risc minim de securitate, atunci poz este -1.
  • Dacă valoarea lui p este 2 atunci se va rezolva numai cerinţa 2. În acest caz fişierul de ieşire va conţine pe prima linie un număr natural m, reprezentând numărul minim de mutări necesare pentru a obţine risc minim de securitate.

Restricţii

  • 1 ≤ n ≤ 100 000
  • 1 ≤ h 1, h 2, …, h n ≤ 100 000
  • Persoana cea mai înaltă într-o configuraţie cu risc minim de securitate poate fi plasată pe oricare dintre poziţiile 1...n
  • Pentru 50% din teste, n ≤ 2000, iar pentru alte 40% din teste, n ≤ 10 000
  • Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerinţa a doua se acordă 80 de puncte.

Exemplu

risc2.inrisc2.outExplicatie
1
4
35 20 10 1
1
p = 1, deci se rezolvă numai cerinţa 1.
Rândul îndeplineşte condiţiile de risc minim de securitate.
Persoana cea mai înaltă se găseste pe poziţia poz = 1.
1
6
1 8 12 20 15 10
-1
p = 1, deci se rezolvă numai cerinţa 1.
Rândul NU îndeplineşte condiţiile de risc minim de securitate.
Şirul înălţimilor nu respectă condiţia ca toate valorile înălţimilor din dreapta poziţiei persoanei celei mai înalte să fie
mai mari decât toate valorile înălţimilor din stânga acesteia.
Deci poz = -1.
2
5
2 8 4 20 16
1
p = 2, deci se rezolvă numai cerinţa 2.
Se mută persoana de înălţime 8 la sfârşitul rândului.
Deci m = 1
2
6
3 19 7 30 10 25
2
p = 2, deci se rezolvă numai cerinţa 2.
Prima operaţie: se mută persoana de înălţime 19 la sfârşitul
rândului. Rândul devine: 3 7 30 10 25 19
A doua operaţie: se mută persoana de înălţime 10 la sfârşitul
rândului.
Rândul devine: 3 7 30 25 19 10
Deci m = 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?