Diferențe pentru problema/iepurasi1 între reviziile #20 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. În fapt, comisia 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"._

_[*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:_

$5 4 *2* 1 3$
$5 4 3 2 1$

_Există, însă, un mod de a sorta cu numai trei operații [*tap*]:

_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$

_Acestea fiind spuse, am adăugat problema la arhivă pentru completitudine (și poate și ca un exemplu de _așa nu_ :-)_

_Î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!

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:

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