== include(page="template/taskheader" task_id="permutare") ==
Lavinia are o afinitate pentru permutări, aşa că ea împreună cu Andrei au propus următorul joc:
Dându-se un număr $N$ şi $N+1$ elemente din mulţimea ${0, 1, -1}$ trebuie să generaţi o permutare de lungime $2*N+1$, care să respecte următoarele condiţii:
* Dacă elementul $x$ din şirul dat este $0$, mediana primelor $2*x-1$ elemente din permutare trebuie să fie egală cu media primelor $2*x-1$ elemente din permutare.
* Dacă elementul $x$ din şirul dat este $1$, mediana primelor $2*x-1$ elemente din permutare trebuie să fie mai mică decât media primelor $2*x-1$ elemente din permutare.
* Dacă elementul $x$ din şirul dat este $-1$, mediana primelor $2*x-1$ elemente din permutare trebuie să fie mai mare decât media primelor $2*x-1$ elemente din permutare.
Poveste şi cerinţă...
h2. Date de intrare
În fişierul de intrare $permutare.in$ se găseşte numărul natural $N$ cu semnificaţia din enunţ. Pe următoarea linie se vor afla $N+1$ numere din mulţimea ${0, 1, -1}$ având seminificaţia din enunţ.
Fişierul de intrare $permutare.in$ ...
h2. Date de ieşire
În fişierul de ieşire $permutare.out$ se vor găsi $2*N+1$ numere naturale reprezentând elementele permutării cerute.
În fişierul de ieşire $permutare.out$ ...
h2. Restricţii
* $N ≤ 100.000$
* Pentru $50%$ din teste $N ≤ 2.000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. permutare.in |_. permutare.out |
| 4
0 -1 0 1 0
| 3 5 6 7 4 9 2 1 8
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Pentru primele $3$ elemente media este $14/3 = 4.66$, iar mediana $5$, deci mediana este mai mare decât media.
Pentru primele $5$ elemente media este $25/5$, iar mediana $5$, deci mediana este egală cu media.
Pentru primele $7$ elemente media este $36/7 = 5.1$, iar mediana este $5$, deci media este mai mare decât mediana.
...
== include(page="template/taskfooter" task_id="permutare") ==
