Задача №115187. Космическое происшествие
Вы являетесь членом экипажа космического корабля «Гиперион», и недавно вы попали в ожесточённое космическое сражение, из которого чудом выбрались. Однако реактор вашего корабля получил серьёзные повреждения и перегрелся, из-за чего запустилась экстренная система охлаждения.
Реактор корабля состоит из \(n\) независимых блоков, каждый из которых имеет свою температуру, которая выражается целым числом градусов. Чтобы он мог работать стабильно, каждый блок должен иметь строго отрицательную температуру. Благодаря достижениям науки, система охлаждения за один цикл охлаждает \(n - 1\) блок на \(B\) градусов, а один оставшийся — на \(A\) градусов.
Система охлаждения не пострадала, но из-за повреждений корабельный компьютер не может рассчитать минимальное необходимое количество циклов для полного охлаждения реактора, и только вы можете решить эту непростую задачу.
Первая строка содержит три целых числа \(n\), \(A\), \(B\) (\(1 \le n \le 100\,000\), \(1 \le A, B \le 10^9\)) — количество блоков в реакторе и параметры \(A\) и \(B\).
Следующая строка содержит \(n\) целых чисел \(t_1,\ t_2,\ \ldots,\ t_n\) (\(-10^9 \le t_i \le 10^9\)), где \(t_i\) — температура \(i\)-го блока в реакторе.
Выведите единственное число — минимальное число циклов до полного охлаждения реактора.
В четвертом тестовом примере система охлаждения может на первом цикле охладить первый блок на 4, а остальные на 2, тогда получатся следующие температуры блоков: \(\{1, 3, -1, -2\}\), а на следующем цикле охладить второй блок на 4, после чего температуры всех блоков станут отрицательными.
Тесты к этой задаче состоят из 6 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп.
| Доп. ограничения | |||||||
| Группа | Баллы | \(n\) | \(t_i\) | \(A\) | \(B\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | – | Тесты из условия. |
| 1 | 15 | \(n \le 5\) | \(|t_i| \le 5\) | \(A \le 5\) | \(B \le 5\) | – | |
| 2 | 16 | – | – | \(A = 1\) | \(B = 2\) | – | |
| 3 | 10 | – | – | – | – | – | A=B |
| 4 | 15 | n = 2 | – | – | – | – | |
| 5 | 24 | \(n \le 500\) | \(|t_i| \le 500\) | \(A \le 500\) | \(B \le 500\) | 0, 1 | |
| 6 | 20 | – | – | – | – | 0 – 5 | |
5 1 2 1 2 3 4 5
3
3 42 42 -273 -273 -273
0
1 3 2 9
4
4 4 2 5 5 1 0
2