Блог пользователя machine_solution

Автор machine_solution, 24 минуты назад, По-русски

И снова привет, Codeforces! С ощутимым перерывом, но всё же выходит следующий разбор из серии "Как додуматься до..."

Этот пост посвящён задаче B2. Юкари Якумо и камни границы из Div 2 раунда, которую я встретил в параллельном Div 1 раунде на первой позиции и, немного удивившись сложности, решил подготовить небольшой рассказ о ней.

Задача имеет первую часть и формулируется следующим образом: у героя есть суммарно $$$n \leq 100$$$ камней, какие-то маленькие, какие-то большие, но мы не знаем сколько каких. В задаче есть две операции. За операцию, обозначаемую символом '+', герой может выбрать какой-то камень. Если он маленький, то становится большим, а иначе большой камень раздваивается в два больших. Для операции символа '-' большой камень становится маленьким, а маленький камень удаляется.

Но вот какие операции будут выполняться выбираем мы: мы готовим строку из '+' и '-' длины от 1 до 999 и передаём герою. Он выбирает в ней префикс и выполняет операции из него слева направо, максимизируя итоговое количество камней после всех операций.

Фактически, герой говорит в ответ на строку, префикс какой длины максимизирует итоговое количество камней при оптимальном выполнении операции. Если таких несколько, то сообщает длину наименьшего из них. Требуется по этому ответу понять, сколько у героя маленьких камней, а сколько больших.

Фууух, так много слов на условие пока что у меня не уходило. Ну что ж, давайте разбираться. Мы герою — строку. Он для каждого префикса понимает сколько камней может получить, исполнив префикс, и сообщает нам оптимальный префикс. А понимаем ли мы сами по префиксу, сколько можно обеспечить камней?

Вопрос 1: Если нам дана фиксированная строка, какое наибольшее число камней можно получить, выполнив команды в ней слева направо?

Подсказка 1.1
Ответ 1.1
Подсказка 1.2
Ответ 1.2
Подсказка 1.3
Ответ 1.3

Итак, мы поняли как считается ответ, выдаваемый системой, в зависимости от стартового числа камней. Получилось довольно удобным то, что это правило довольно простое. Но нам всё ещё нужно научиться выдавать такую строку, по ответу на которую можно однозначно определить количество камней обоих типов у героя.

Так как суммарное число камней известно, я предлагаю пытаться установить, сколько больших камней было у героя. Но так как сходу не ясно как это сделать, давайте чуть упростим задачу

Вопрос 2: Если бы вам можно было сделать не 1 запрос, а несколько, как тогда восстановить количество больших камней?

Подсказка 2.1
Подсказка 2.2
Ответ 2.2
Подсказка 2.3
Ответ 2.3

Вопрос 3: Как теперь справиться за 1 запрос?

Подсказка 3.1
Ответ 3.1
Ответ 3.2

Вот и всё, теперь мы научились решать такую забавную интерактивную задачу. Надеюсь, вам понравилось читать разбор и думать над задачей в процессе. Желаю всем читателям дальнейших успехов на раундах Codeforces!

Замечание: Если вам понравился этот пост, то, возможно, вам понравится контент из телеграм-канала, в который я выкладываю свою подготовку к финалу ICPC 2026. Переходите по ссылке

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
15 минут назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем machine_solution (предыдущая версия, новая версия, сравнить).