Анализ позиций
Ошибка.
Попробуйте повторить позже
Кащей и Василиса играют в игру. Изначально пять одинаковых пустых вёдер ёмкостью стоят по кругу. За ход Кащей берёт изо рва литр воды и распределяет его по вёдрам как ему заблагорассудится, а затем Василиса опустошает любые два соседних ведра. Кащей выигрывает, если после какого-то его хода хотя бы одно из вёдер переполнится. При каких Василиса может не допустить этого?
Подсказка 1
Попробуйте поиграть за Кащея. Выработайте какую-нибудь стратегию, из нее подумайте о действиях Василисы.
Подсказка 2
Ответ а≥2. При меньших Кащей может в первое ведро наливать почти все, а остальное по капельке сливать в третье ведро. Поймите, почему это не работает при больших а.
Подсказка 3
Реализуете за Василису "жадный" алгоритм, сливая из наибольшей по объему пары вёдер.
Сначала покажем, что при емкости вёдер Кащей сможет добиться того, что ведро будет переполнено. Если то Кощею достаточно литр поместить в одно какое-то ведро.
Иначе пусть где и пусть ведра пронумерованы по кругу: соответственно. Тогда пусть Кощей наливает в первое ведро а в третье литров воды.
Василиса может опустошить только одно из ведер: либо первое, либо третье, потому что они не стоят рядом. Дальше будет действовать следующим образом: если Василиса не опустошает первое ведро, то пусть Кащей просто дольет в первое ведро литр и в нем станет поэтому это ведро переполнится. Иначе Василиса опустошила первое ведро, но тогда третье ведро осталось заполненным. Пусть Кощей также наливает в первое ведро а в третье литров воды до того момента, когда либо Василиса не опустошает первое ведро (тогда Кощей доливает в первое ведро литр и побеждает), либо в третьем ведре станет где — число раз, когда Василиса не опустошала третье ведро.
Теперь покажем, что при Василиса может не допустить переполнений. Будем играть за Василису. Всегда будем выбирать такие соседних ведра, в которых суммарно наибольшее число воды. Причем, если в нескольких парах ведер суммарно поровну воды, то действуем как угодно. Тогда мы будем каждым ходом опустошать хотя бы суммарного объема. Заметим, что тогда после опустошения будет всегда оставаться менее литров воды суммарно во всех ведрах. Тогда объем любого ведра меньше Получается, долив литр, Кащей получит ведро объемом меньше двух литров.
При
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!