Ліки для Тома#12999

Ліки для Тома (Розбір)

Спершу з'ясуємо, коли приймати чергову таблетку. Нехай зараз концентрація дорівнює y \ge x. Якщо прийняти таблетку негайно, час до падіння до становитиме \log_2\frac{y + a}{x}; якщо ж дочекатися падіння до і прийняти її тоді, загальний час буде \log_2\frac{y}{x} + \log_2\frac{x + a}{x}. Порівнюючи, отримуємо y(x + a) проти x(y + a), тобто проти : при y \ge x чекати не гірше. Отже кожна таблетка, крім найпершого прийому, дається рівно в мить, коли концентрація торкається , і дає \log_2\left(1 + \frac{a_i}{x}\right) годин.

Початок — виняток: концентрація дорівнює нулю, тож перший прийом має сам дотягнути до , і він дає \log_2\frac{A}{x}, де — сума прийнятих одночасно таблеток. Тому перевищувати невигідно, і початковий набір треба брати якнайменшим і з найбільших таблеток:

Отже: відсортувати таблетки за спаданням, узяти найкоротший префікс із сумою A \ge x (якщо сума всіх менша за , відповідь ), і відповідь дорівнює

\log_2\frac{A}{x} + \sum_{i \notin \text{префікс}} \log_2\frac{x + a_i}{x}.

Складність: O(n \log n) на сортування.

Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.