Fișierul intrare/ieșire	iepurasi1.in, iepurasi1.out	Sursă	ONI 2014, clasa a 5-a
Autor	Sanda Junea	Adăugată de	Mihai Tutu • mihai.tutu
Timp de execuție pe test	0.5 sec	Limită de memorie	5120 KB
Scorul tău	N/A	Dificultate	3.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Iepurași 1 (clasa a 5-a)

Notă importantă: problema este o variantă a unei probleme clasice, numită pancake sorting. Această problemă este NP-hard, 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”.

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

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

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

• 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.

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.

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:

1. Numărul minim de operații TAP necesare rearanjării iepurașilor;
2. 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ș.

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.

Date de ieșire

Fișierul de ieșire iepurasi1.out va conține pe prima linie un număr reprezentând numărul minim de operații TAP necesare rearanjării iepurașilor.
A doua linie va conține un număr reprezentând 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), respectiv cel mai mare număr aflat pe o față albă a unui cartonaș, în cazul în care toate cartonașele au fost întoarse (la toate fiind vizibilă fața albă).

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.

Exemple