Решение задачи Средний класс с Codeforces
Без пояснения   Просмотров: 162
Давным-давно Берляндия была маленькой страной, в которой проживало только n человек. Каждый из них имел некоторое количество сбережений: у i-го человека было ai бурлей.
Правительство считало человека богатым, если у него было хотя бы x бурлей. Чтобы увеличить количество богатых людей в Берляндии, решили провести несколько реформ. Каждая реформа выглядела следующим образом:
правительство выбирает некоторое подмножество людей (возможно, всех);
правительство забирает все сбережения у выбранных людей и перераспределяет их среди выбранных людей поровну.
Например, представим сбережения как список [5,1,2,1]: если правительство выбирает 1-го и 3-го человека, то оно, сначала заберет у них все 5+2=7 бурлей, а потом вернет каждому по 3.5 бурлей. В результате сбережения примут вид [3.5,1,3.5,1].
Много информации было потеряно с того времени, поэтому мы не знаем, сколько реформ было проведено и на ком. Все, что мы можем — это попросить вас посчитать максимально возможное количество богатых людей после некоторого (возможно нулевого) количества реформ.
Правительство считало человека богатым, если у него было хотя бы x бурлей. Чтобы увеличить количество богатых людей в Берляндии, решили провести несколько реформ. Каждая реформа выглядела следующим образом:
правительство выбирает некоторое подмножество людей (возможно, всех);
правительство забирает все сбережения у выбранных людей и перераспределяет их среди выбранных людей поровну.
Например, представим сбережения как список [5,1,2,1]: если правительство выбирает 1-го и 3-го человека, то оно, сначала заберет у них все 5+2=7 бурлей, а потом вернет каждому по 3.5 бурлей. В результате сбережения примут вид [3.5,1,3.5,1].
Много информации было потеряно с того времени, поэтому мы не знаем, сколько реформ было проведено и на ком. Все, что мы можем — это попросить вас посчитать максимально возможное количество богатых людей после некоторого (возможно нулевого) количества реформ.