| Fişierul intrare/ieşire: | sport3.in, sport3.out | Sursă | Lot Ploiești Juniori 2026, Baraj 2 |
| Autor | Bogdan-Ioan Popa, Daniel Popa | Adăugată de |  Antonie Aureliu Valentin •ValiAntonie123 |
| Timp execuţie pe test | 1 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sport3
Cei N elevi din Colegiul Naţional „I. L. Caragiale” Ploieşti intră pe rând în sala de sport, în ordinea 1, 2, ..., N. Înălţimile celor N elevi sunt cunoscute şi sunt notate cu H1, H2, . . . , HN.
Profesorul de sport îi aşază în linie, în ordinea în care intră. Pentru fiecare elev care intră în sala de sport, profesorul poate să aleagă să îl aşeze la începutul liniei sau la sfârşitul liniei, cu scopul ca la final elevii să fie ordonaţi crescător după înălţime. Dacă profesorul nu are posibilitatea de a aşeza elevii în această ordine, acesta s-ar supăra, aşa că elevii trebuie să se asigure că vor intra în sală într-un mod corespunzător.
Elevii pot să se rearanjeze între ei înainte de a intra în sală, dar nu pot să se rearanjeze după ce au intrat în sală. Pentru aceasta, ei pot face operaţii de mutare.
Printr-o operaţie de mutare, un elev este mutat din poziţia în care se află într-o altă poziţie în şirul de elevi de la intrarea în sala de sport.
Cerinţă
Scrieţi un program care cunoscând numărul de elevi N, precum şi înălţimile acestora, determină numărul minim de operaţii de mutare necesare pentru a rearanja elevii, astfel încât, la intrarea lor în sala de sport, profesorul să poată aşeza elevii în ordinea crescătoare a înălţimilor.
Date de intrare
Fişierul de intrare sport3.in conţine numărul natural N pe prima linie, iar pe a doua linie conţine N numere naturale H1, H2, ..., HN, separate prin spaţii.
Date de ieşire
Fişierul de ieşire sport3.out conţine o singură linie pe care este scris numărul minim de operaţii de mutare necesare pentru a rearanja elevii conform condiţiilor din enunţ.
Restricţii şi precizări
- 1 ≤ N ≤ 250 000
- 1 ≤ Hi ≤ 109 pentru 1 ≤ i ≤ N
- Pentru teste valorând 75 de puncte, înălţimile elevilor sunt distincte.
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 12 | 1 ≤ N ≤ 15, 1 ≤ Hi ≤ 100 pentru orice 1 ≤ i ≤ N |
| 2 | 32 | 16 ≤ N ≤ 100 |
| 3 | 28 | 101 ≤ N ≤ 5000 |
| 4 | 28 | Fără restricţii suplimentare |
Exemple
| sport3.in | sport3.out |
|---|---|
| 5 3 4 2 5 1 | 0 |
| 5 10 8 8 9 12 | 1 |
Explicaţii
Pentru primul exemplu:
Elevul cu înălţimea 3 intră primul în sală, elevul cu înălţimea 4 intră la sfârşitul liniei, elevul cu înălţimea 2 intră la începutul liniei, elevul cu înălţimea 5 intră la sfârşitul liniei, iar elevul cu înălţimea 1 intră la începutul liniei. Astfel, elevii sunt aşezaţi în ordine crescătoare, deci nu sunt necesare operaţii de mutare suplimentare.
Pentru al doilea exemplu:
Este necesară o operaţie de mutare. O operaţie posibilă este ca elevul cu înălţimea 9 trebuie mutat după elevul cu înălţimea 10.
