Codeforces Round 219 (Div. 1) |
---|
Закончено |
Даны n кенгуру с сумками. У каждого кенгуру есть размер (целое число). Кенгуру может поместиться в сумке другого кенгуру тогда и только тогда, когда размер кенгуру-носителя как минимум в два раза больше размера кенгуру-пассажира.
Каждый кенгуру может нести не более одного кенгуру, а кенгуру-пассажир не может носить никаких кенгуру.
Кенгуру-пассажира не видно, когда он в сумке кенгуру-носителя. Пожалуйста, разработайте такой план рассадки кенгуру, чтобы было видно как можно меньше кенгуру.
В первой строке записано единственное целое число — n (1 ≤ n ≤ 5·105). Каждая из следующих n строк содержит целое число si — размер i-го кенгуру (1 ≤ si ≤ 105).
Выведите единственное целое число — оптимальное количество видимых кенгуру.
8
2
5
7
6
9
8
4
2
5
8
9
1
6
2
6
5
8
3
5
Название |
---|