Fișierul intrare/ieșire	papusa.in, papusa.out	Sursă	ONI 2011 clasa a 5-a
Autor	Susana Gălățan	Adăugată de	Coman Isabela Patricia • Isabela_coman
Timp de execuție pe test	1 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	3

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

Vezi soluțiile trimise | Statistici

Păpușa (clasa a 5-a)

Păpușa Matrioșka este o jucărie din lemn, goală pe dinăuntru. De aceea, în interiorul său poate fi introdusă oricare altă păpușă Matrioșka de înălțime mai mică. La un magazin de suveniruri se găsesc n păpuși Matrioșka așezate în șir, în număr egal, pe două rafturi alăturate. Pe raftul din stânga sunt expuse prima jumătate de păpuși, situate în șir pe pozițiile 1, 2,…, n/2, iar raftul din dreapta ultima jumătate de păpuși, situate în șir pe pozițiile n/2+1,…, n. Prin notația n/2 se înțelege jumătatea numărului n. Ana și Iulia vor să cumpere cât mai multe păpuși Matrioșka, dar tatăl lor le impune următoarele reguli:

• Iulia are voie să aleagă păpuși din raftul din stânga, iar Ana din raftul din dreapta
• Dacă de pe un raft se cumpără mai multe păpuși, atunci ele se vor afla pe poziții consecutive pe raft;
• Prima păpușă cumpărată de o fetiță va avea înălțimea mai mică decât cea de a doua, a doua decât cea de a treia și așa mai departe astfel încât fiecare păpușă să poate fi introdusă în următoarea păpușă cumpărată;
• Ultimele păpuși cumpărate trebuie să se situeze doar la capetele rafturilor și în plus:
  • dacă ultima păpușă cumpărată de Iulia este pe poziția 1 atunci ultima păpușă cumpărată de Ana trebuie să fie pe poziția n;
  • dacă ultima păpușă cumpărată de Iulia este pe poziția n/2 atunci ultima păpușă cumpărată de Ana trebuie să fie pe poziția n/2+1.

Pentru a putea să aleagă cât mai multe păpuși respectând regulile impuse de tatăl lor, fetițelor li se permite să execute în același timp
următoarea operație, până se revine la așezarea inițială a păpușilor:

• Iulia mută păpușa de pe poziția 1 pe poziția n/2, deplasând cu o poziție spre stânga toate celelalte păpuși din raftul său;
• Ana mută păpușa de pe poziția n pe poziția n/2+1, deplasând cu o poziție spre dreapta toate celelalte păpuși din raftul său;

Cerințe:

Pentru a le ajuta pe Iulia și Ana să achiziționeze împreună un număr maxim de păpuși, scrieți un program care citește un număr natural n și înălțimile celor n păpuși și determină:
a) numărul M de operații efectuate concomitent de fetițe;
b) numărul maxim P de păpuși care vor fi cumpărate.

Date de intrare

Fișierul text papusa.in conține pe prima linie un număr natural par n, reprezentând numărul de păpuși. Pe linia a doua sunt n numere naturale separate prin câte un spațiu, reprezentând înălțimile păpușilor situate pe cele două rafturi, în ordine de la poziția 1 la n.

Date de ieșire

Fișierul de ieșire papusa.out va conține:
a) pe prima linie, numărul natural M;
b) pe a doua linie, numărul natural P.

Restricții

• 2 ≤ n ≤ 1000, n este număr par
• 1 ≤ înălțimile păpușilor ≤ 10000
• Dacă numărul maxim de păpuși se obține fără a face operații de mutare atunci M = 0
• Pentru toate testele de intrare există o singură configurație pentru care se poate cumpăra un număr maxim de păpuși

Pentru rezolvarea cerinței a) se acordă 40% din punctaj, pentru rezolvarea cerinței b) 60% din punctaj

Exemplu