Detalii evaluare #10826467

Rezumat problemă

#1186 Risc

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.

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.

ONI 2015, Clasa a IX-a

Detalii

Problema Risc Operații I/O risc.in/risc.out
Limita timp 0.02 secunde Limita memorie Total: 4 MB / Stivă 4 MB
Id soluție #10826467 Utilizator Pâsoi Ștefan (pasoi_stefan)
Fișier risc.cpp Dimensiune 462 B
Data încărcării 08 Octombrie 2018, 23:33 Scor / rezultat 20 puncte

Evaluare


Mesaj compilare


Rezultat evaluare

Test Timp Mesaj evaluare Scor posibil Scor obținut
0 0 secunde OK. 5 5
1 0 secunde OK. 5 5
2 0 secunde OK. 5 5
3 0 secunde OK. 5 5
4 0 secunde Raspuns gresit. 3 0
5 0 secunde Raspuns gresit. 3 0
6 0 secunde Raspuns gresit. 3 0
7 0 secunde Raspuns gresit. 4 0
8 0 secunde Raspuns gresit. 4 0
9 0 secunde Raspuns gresit. 4 0
10 0 secunde Raspuns gresit. 4 0
11 0 secunde Raspuns gresit. 5 0
12 0 secunde Raspuns gresit. 5 0
13 0 secunde Raspuns gresit. 5 0
14 0 secunde Raspuns gresit. 5 0
15 0 secunde Raspuns gresit. 5 0
16 0 secunde Raspuns gresit. 5 0
17 0 secunde Raspuns gresit. 5 0
18 0 secunde Raspuns gresit. 5 0
19 0 secunde Raspuns gresit. 5 0
20 0.008 secunde Raspuns gresit. 5 0
21 0.008 secunde Raspuns gresit. 5 0
Punctaj total 20

Cum funcționează evaluarea?

www.pbinfo.ro permite evaluarea a două tipuri de probleme:

  • probleme la care rezolvarea presupune scrierea unui program complet
  • probleme la care rezolvarea presupune scrierea unei secvențe de program - câteva instrucțiuni, o listă de declarații, una sau mai multe funcții, etc.

Problema Risc face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:

  • Programul sursă este compilat folosind compilatorul corespunzător. Dacă în urma compilării se obțin erori sau avertismente, acestea sunt afișate în această pagină.
  • Dacă programul a fost compilat, executabilul obținut va fi rulat, furnizându-i-se unul sau mai multe seturi de date de intrare, în concordanță cu restricțiile specifice problemei. Pentru fiecare set de date se obține un anumit punctaj, în raport cu corectitudinea soluției tale.

Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.