Fişierul intrare/ieşire:papusa.in, papusa.outSursăONI 2011 clasa a 5-a
AutorSuzana GalatanAdăugată deIsabela_comanComan Isabela Patricia Isabela_coman
Timp execuţie pe test1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Păpușă ( 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

papusa.inpapusa.outExplicatii
8
5 7 2 4 6 10 14 8
2
7
Raftul Iuliei conţine păpuşile de înălţimi 5, 7, 2, 4, iar al Anei păpuşile de înălţimi 6, 10, 14, 8.
Pe această aşezare Iulia şi Ana pot cumpăra păpuşile de înălţime 2 4 6 sau 5 8. Se pot cumpăra cel
mult 3 păpuşi.
Configuraţia obţinută după prima operaţie de mutare este: 7 2 4 5 8 6 10 14
Pe această aşezare Iulia şi Ana pot cumpăra păpuşile de înălţime 2 4 5 6 8 sau 2 7 6 10 14. Se
pot cumpăra cel mult 5 păpuşi.
Configuraţia obţinută după a doua operaţie 2 4 5 7 14 8 6 10. Pe această aşezare Iulia şi
Ana pot cumpăra păpuşile cu înălţimile 2 4 5 7 6 8 14 sau 2 6 10. Deci se pot cumpăra cel mult
7 păpuşi.
Configuraţia obţinută după a treia operaţie 4 5 7 2 10 14 8 6.
Pe această aşezare Iulia şi Ana pot cumpăra păpuşile cu înălţimile 2 10 sau 4 6. Deci se pot
cumpăra cel mult 2 păpuşi.
Numărul maxim de păpuşi cumpărate este 7 şi se obţine după a doua operaţie de mutare.
Trebuie sa te autentifici pentru a trimite solutii. Click aici