Fişierul intrare/ieşire: | mediana.in, mediana.out | Sursă | Concurs IQ Academy | Clasa a 10-a |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 0.2 sec | Limită de memorie | 3072 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Mediana (clasa a 10-a)
Numim mediana unui vector cu N elemente valoarea care se află pe poziţia (N + 1) / 2 după sortarea elementelor în ordine crescătoare.
Cerinţă
Avem un vector care este iniţial gol. Se dau Q operaţii de forma:
- 1 X: adăugaţi numărul X în vector
- 2: afişaţi mediana vectorului
Date de intrare
Fişierul de intrare mediana.in conţine pe prima linie numărul natural Q, iar pe următoarele Q linii operaţiile descrise în enunţ.
Date de ieşire
În fişierul de ieşire mediana.out se vor găsi răspunsurile operaţiilor de tip 2, fiecare răspuns pe câte o linie.
Restricţii
- 1 ≤ Q ≤ 100.000
- 1 ≤ X ≤ 109
- Se garantează că prima operaţie nu este de tip 2.
Exemplu
mediana.in | mediana.out |
---|---|
10 1 2 1 3 1 1 1 4 1 5 2 1 6 1 7 1 8 2 | 3 4 |
Explicaţie
Pentru prima întrebare, vectorul este {2, 3, 1, 4, 5}. Îl vom ordona crescător: {1, 2, 3, 4, 5}. Deci mediana este 3.
Pentru cea de-a doua întrebare, vectorul ordonat crescător este {1, 2, 3, 4, 5, 6, 7, 8}. Deci mediana este 4.