Trex#195

Trex (Editorial)

Спершу з'ясуємо, як одне заклинання змінює кількість монет. Якщо в Буратіно монет і він закопує T \le p з них, то на руках лишається p - T, а викопує він . Разом:

p \longrightarrow p + T, \qquad \text{а із сіллю} \qquad p \longrightarrow p + T + 1.

Отже, за одне заклинання з можна отримати будь-яке число з відрізка [p,\; 2p], а маючи порцію солі — ще й на одиницю більше, тобто аж до 2p + 1.

Звідси одразу два випадки неможливості: якщо S < P (монети ніколи не зменшуються) і якщо P = 0, S > 0 при K = 0 (з нуля без солі виростає лише нуль).

Тепер жадібний алгоритм. Оскільки за один крок ми можемо дострибнути до будь-якого значення в [p, 2p+1], вигідно щоразу стрибати якнайдалі, але не перестрибувати ціль:

  • якщо 2p + 1 \le S і сіль ще є — закопуємо все й солимо: T = p, нове p = 2p+1;

  • інакше, якщо 2p \le S — закопуємо все без солі: T = p, нове p = 2p;

  • інакше S \le 2p, і ми потрапляємо в ціль одним кроком: T = S - p без солі.

Чому це мінімально? З будь-якого p \le S ми гарантовано завершуємо за один крок, щойно S \le 2p. Тому мінімізувати кількість кроків — це максимізувати на кожному кроці, що жадібний вибір і робить. Сіль варто витрачати якомога раніше: додана одиниця потім подвоюється разом з усім іншим, тобто ранній «» коштує дорожче за пізній.

Кількість заклинань не перевищує приблизно \log_2 S \approx 30, бо щонайменше подвоюється (окрім початкового кроку з нуля).

Виводимо кількість заклинань, а потім для кожного — пару «скільки монет закопано» і прапорець солі. Не забудьте окремо обробити S = P: тоді відповідь нуль заклинань і жодного рядка далі.