Codeforces Round 531 (Div. 3) |
---|
Закончено |
Вы — милиционер и играете в игру со Славиком. Игра является пошаговой, а каждый шаг состоит из двух фаз. Во время первой фазы вы делаете ход, а во время второй фазы Славик делает ход.
Есть $$$n$$$ дверей, прочность $$$i$$$-й двери изначально равна $$$a_i$$$.
Во время вашего хода вы можете попробовать выпилить одну из дверей. Если вы выбираете дверь $$$i$$$ и ее текущая прочность равна $$$b_i$$$, то ее прочность становится $$$max(0, b_i - x)$$$ (значение $$$x$$$ задано).
Во время хода Славика он пробует запилить одну из дверей. Если он выбирает дверь $$$i$$$ и ее текущая прочность равна $$$b_i$$$, то ее прочность становится $$$b_i + y$$$ (значение $$$y$$$ задано). Славик не может запиливать двери с текущей прочностью $$$0$$$.
Игра длится $$$10^{100}$$$ шагов. Если какой-то игрок не может сделать свой ход, то он его пропускает.
Ваша задача — максимизировать количество дверей с прочностью $$$0$$$ в конце игры. Можете считать, что Славик хочет минимизировать количество таких дверей. Чему равно это количество, если вы оба играете оптимально?
Первая строка входных данных содержит три целых числа $$$n$$$, $$$x$$$ и $$$y$$$ ($$$1 \le n \le 100$$$, $$$1 \le x, y \le 10^5$$$) — количество дверей, значение $$$x$$$ и значение $$$y$$$ соответственно.
Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$), где $$$a_i$$$ равно изначальной прочности $$$i$$$-й двери.
Выведите одно целое число — количество дверей с прочностью $$$0$$$ в конце игры, если и вы, и Славик играете оптимально.
6 3 2 2 3 1 3 4 2
6
5 3 3 1 2 4 2 3
2
5 5 6 1 2 6 10 3
2
Вопросы по поводу оптимальной стратегии будут игнорироваться.
Название |
---|