!>problema/papusa?papusa.jpg!
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:
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.
** 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;
* 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;
h2. Cerințe:
