Diferențe pentru problema/iepurasi1 între reviziile #4 si #43

== include(page="template/taskheader" task_id="iepurasi1") ==

_[*Notă importantă*]: problema este o variantă a unei probleme clasice, numită ["pancake sorting":https://en.wikipedia.org/wiki/Pancake_sorting]. Această problemă este ["NP-hard":https://www.i-programmer.info/news/112-theory/3280-pancake-flipping-is-hard-np-hard.html], deci, evident, nu are ce căuta la clasa a cincea, sau, ca idee, la nici o clasă, întrucât omenirea nu cunoaște un algoritm polinomial pentru ea. Faptul că ea a fost dată la ONI clasa a 5-a arată lipsa de competență a comisiei științifice de clasa a cincea. În fapt, comisia științifică a fost, la acel moment, prevenită că problema este NP-hard, dar a ales să ignore acest lucru cu mențiunea "noi nu știm ce e aia"._
 
_Dacă aveți îndoieli în legătură cu cele spuse mai sus, să considerăm următorul exemplu:_
 
$1 2 5 3 4$
 
_Dacă sortăm numerele descrescător conform soluției comisiei, un select sort în care la fiecare pas mutăm maximul la coadă și apoi îl punem pe poziție, vom obține cinci pași (am îngroșat numerele pe care facem operația [*tap*]):_
 
$1 2 *5* 3 4$
$*1* 2 4 3 5$
$5 3 *4* 2 1$
$5 *3* 1 2 4$
$5 4 *2* 1 3$
$5 4 3 2 1$
 
_Există, însă, un mod de a sorta cu numai trei operații [*tap*]:_
 
$1 2 5 *3* 4$
$1 2 *5* 4 3$
$*1* 2 3 4 5$
$5 4 3 2 1$
 
_În plus, chiar și [*un test al comisiei este greșit*], testul 10:_
 
$6 9 8 7 10$
 
_Soluția oficială rezolvă testul în cinci pași, dar există soluție în patru pași, aplicând *tap* pe, respectiv, numerele 6, 7, 9, 6._
 
_Acestea fiind spuse, am adăugat problema la arhivă pentru completitudine (și poate și ca un exemplu de [*așa nu*]_ 🙂[_)_]
 
<p><br />
<p><br />
<p><br />
<p><br />
<p><br />
<p><br />
<p><br />
<p><br />
 
!>problema/iepurasi1?problema_iepurasi.png!
 

Se construiește un șir de numere naturale care respectă restricțiile:

* primul numpr din șir este 9;

* primul număr din șir este 9;

* numerele se generează în ordine strict crescătoare;
* șirul conține toate numerele formate doar cu cifrele 7,8 și 9 cu proprietatea că numărul cifrelor 9 este mai mare sau egal decât numărul cifrelor 8 și numărul cifrelor 8 este mai mare sau egal decât numărul cifrelor 7.
Primii 14 termeni ai șirului, în ordine, sunt: 9, 89, 98, 99, 789, 798, 879, 897, 899, 978, 987, 989, 998, 999.

Pornind de la aceste numere, Liv a inventat un joc interactiv. *N* iepurași sunt așezați în șir, fiecare având câte un cartonaș. Fiecare cartonaș are două fețe, o față albă pe care este inscripționat un număr din acest șir și o față gri, pe care este inscripționată poziția acelui număr în șir, poziții numerotate în ordine, începând cu valoarea 1.
h2. Exemple
Cartonașul care are pe fața gri inscripționat numărul 1 va avea pe fața albă inscripționat numărul 9, iar cartonașul care are pe fața gri inscripționat numărul 5 va avea pe fața albă inscripționat numărul 789.

Iepurașii sunt așezați într-o ordine oarecare și țin cartonașele astfel încât să se vadă fața gri. Jocul constă în a rearanja iepurașii de la stânga la dreapta, descrescător după numerele inscripționate pe fețele gri, având la dispoziție doar operația TAP pe un iepuraș. Când se aplică operația TAP unui iepuraș, atunci secvența de iepurași, începând de la cel pe care s-a făcut TAP și până la sfârșitul șirului (spre dreapta), este oglindită (ca în imaginea de mai sus). După oglindire, toți iepurașii din acea secvență țin cartonașele astfel încât să se vadă fața albă. Se dorește aplicarea unui număr cât mai mic de operații TAP pentru rearanjarea iepurașilor.
h2. Cerință

Scrieți un program care să citească numerele naturale *N* (reprezentând numărul de iepurași) și *a1, a2,...,an* (reprezentând în ordine, numerele inscripționate pe fețele gri) și care să determine:
a) Numărul minim de operații TAP necesare rearanjării iepurașilor;
b) Cel mai mic număr aflat pe o față albă care nu se vede, în cazul în care au rămas cartonașe neîntoarse. Dacă toate cartonașele au fost întoarse (la toate fiind vizibilă fața albă) se va afișa cel mai mare număr aflat pe o față albă a unui cartonaș.

Scrieți un program care să citească numerele naturale *N* (reprezentând numărul de iepurași) și *a[~1~], a[~2~], ..., a[~n~]* (reprezentând în ordine, numerele inscripționate pe fețele gri) și care să determine:
 
# Numărul minim de operații TAP necesare rearanjării iepurașilor;
# Cel mai mic număr aflat pe o față albă care nu se vede, în cazul în care au rămas cartonașe neîntoarse. Dacă toate cartonașele au fost întoarse (la toate fiind vizibilă fața albă) se va afișa cel mai mare număr aflat pe o față albă a unui cartonaș.

h2. Date de intrare
Fișierul de intrare $iepurasi1.in$ conține pe prima linie numărul natural *N* reprezentând numărul de iepurași.

A doua linie a fișierului conține, în ordine, cele *N* numere: *a1, a2,...,an* separate prin câte un spațiu, reprezentând în ordine, numerele inscripționate pe fețele gri ale cartonașelor.

A doua linie a fișierului conține, în ordine, cele *N* numere: *a[~1~], a[~2~], ..., a[~n~]* separate prin câte un spațiu, reprezentând în ordine, numerele inscripționate pe fețele gri ale cartonașelor.

h2. Date de ieșire

h2. Restricții
* $2 ≤ *N* ≤ 10000$

* $1 ≤ *N* ≤ 10000 (1≤i≤N);$
* $*N*, a1, a2,...,an sunt numere naturale;$
* $pentru rezolvarea cerinței a) se acordă 50% din punctaj, iar pentru cerința b) se acordă 50% din punctaj.$

* $1 ≤ *a[~i~]* ≤ 10000 (1≤i≤N);$
* $*N*, *a[~1~], a[~2~], ..., a[~n~]* sunt numere naturale;$
* $pentru rezolvarea cerinței 1 se acordă 50% din punctaj, iar pentru cerința 2 se acordă 50% din punctaj.$

h2. Exemple

table(example).

table(example).

|_. iepurasi1.in |_. iepurasi1.out |_. Explicație |
| 5
14 5 8 9 10