![](/static/branding/mistrzostwa/map_logo.jpg)
![](/static/branding/mistrzostwa/nask_logo.png)
![](/static/branding/mistrzostwa/cp_logo.png)
![](/static/branding/mistrzostwa/uwr_logo.png)
![](/static/branding/mistrzostwa/fri_logo.png)
![](/static/branding/mistrzostwa/insert_logo.png)
Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2023
Problem description
Do ZOO mają zostać sprowadzone bardzo drapieżne tygrysy. Zostaną umieszczone w klatce, gdzie będzie można je oglądać przez kilka tygodni. Oczywiście, najlepiej byłoby, gdyby tygrysów było możliwie dużo. Problem jest taki, że tygrysy różnią się rozmiarem, niektóre są większe, a inne mniejsze. To wywołuje ryzyko, że niektóre tygrysy (większe) zjedzą inne (mniejsze).
Wiadomo, że tygrys rozmiaru K może zostać zjedzony tylko przez tygrysy rozmiaru co najmniej 2K. A zatem tygrysy rozmiarów 5 i 8 można bezpiecznie umieścić w klatce, zaś tygrysów 5 i 12 bezpiecznie w klatce umieścić nie można.
Napisz program, który: wczyta rozmiary tygrysów, wyznaczy ile maksymalnie tygrysów można zmieścić w jednej klatce i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę tygrysów. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych Ai, pooddzielanych pojedynczymi odstępami – określają one rozmiary kolejnych tygrysów.
Wyjście
W pierwszym (i jedynym) wierszu wejścia powinna się znaleźć jedna liczba całkowita – maksymalna liczba tygrysów, które można bezpiecznie umieścić razem ze sobą w klatce, aby się nie pozjadały.
Ograniczenia
1 ≤ N ≤ 1 000 000, 1 ≤ Ai ≤ 1018.
W testach wartych łącznie 40% maksymalnej punktacji zachodzi dodatkowy warunek: N ≤ 2 000.
Przykład
Input | Output | Explanation |
|
|
Wystarczy wziąć do jednej klatki tygrysy rozmiarów 5, 6, 5. |