1 Ответ
Задания 9-11 класс
Задание 1. Тайна магического домино
В далёком королевстве, где магия и реальность переплетаются, существует легенда о бесконечной цепи магических костяшек домино. Эти костяшки выстроены вдоль старинной дороги и обладают особыми свойствами. Каждая костяшка расположена на координате xi и имеет магическую силу, равную hi, определяющую её способность влиять на другие костяшки.
Однажды юная волшебница Оля решила испытать силу этой цепи и толкнула первую костяшку. При падении костяшка выпускает магический импульс, который распространяется вперёд и заставляет падать все костяшки, находящиеся на координатах не больше, чем xi+hi. Каждая следующая костяшка, попавшая под действие импульса, действует аналогично, создавая эффект магической цепной реакции.
Строго говоря, при воздействии на костяшку на позиции xi будут задеты, и как следствие, выпустят уже свой магический импульс, все костяшки с такими координатами xj, что xi+hi≤xj.
К Оле решила присоединиться её подруга Яло. Она решила проверить, как поведут себя костяшки, если их толкнуть с другой стороны. Девочка толкнула последнюю костяшку, которая находилась на самой правой позиции. И вот что произошло.
Самая правая костяшка, которую толкнула Яло, выпустила магический импульс, который распространяется назад, заставляя падать костяшки, находящиеся на координатах не больших чем xi−hi. Иными словами, если костяшка на позиции xi падает, то она сама выпускает магический импульс, под воздействие которого попадают все костяшки, чьи координаты удовлетворяют условию xi−hi>xj.
Таким образом, костяшки, падающие с одной стороны, могут встретиться с костяшками, падающими с другой, при этом магические импульсы с двух сторон продолжат распространяться так же, как и до встречи. Теперь обе цепные реакции Оли и Яло идут навстречу друг другу, и вы очень хотите узнать, сколько же суммарно костяшек упадёт.
Замечание
В первом примере первая костяшка, которую толкнула Оля, не достанет до следующей (т.к. её «высота» составляет всего 2), а поэтому от импульса слева упадёт только она. Стоящая на координате 8 костяшка, которую толкнула Яло, заденет костяшку, стоящую на координате 7, которая, в свою очередь, не заденет костяшку на координате 5, т.к. её «высота» равна 1. На рисунке ниже показаны костяшки до того, как их толкнули, и их итоговое состояние (красным отмечены места, которые «задела» хотя бы одна костяшка).
ответ:
Задание 2. Покраска забора
Недавно Егор узнал, что средняя зарплата маляра в России составляет более ста тысяч рублей в месяц. Сейчас он получает немного меньше (примерно ноль рублей в месяц), а потому пошёл работать маляром.
В первый же день работы он получил свое первое задание покрасить забор, состоящий из k досок. Опишем этот процесс немного подробнее. Забор можно представить в виде k досок, стоящих в ряд. Слева от забора стоит телега, в которой есть n банок с краской, при этом i-й банки хватит ровно на ai досок.
Изначально Егор стоит слева от забора (прямо перед телегой), при этом в его руке нет банки с краской. Егор пока что не окончил вуз, поэтому набор его навыков ограничен:
Взять банку с краской. Если Егор стоит перед телегой, то он может взять в руку любую банку, в которой ещё осталась краска. Если у Егора уже была какая‑то банка в руке, то он возьмёт новую, а старую оставит у телеги. Это действие не занимает времени.
Сдвинуться вправо. После этого Егор перейдёт к следующей доске. Если Егор стоял у телеги, то после этого перемещения он будет стоять перед первой доской. При этом Егор не может сдвинуться вправо, если он уже у находится у последней доски. Это действие занимает 1 секунду.
Сдвинуться влево. После этого Егор перейдёт к предыдущей доске. Если Егор стоит у первой доски, то после этого перемещения он будет стоять перед телегой. Конечно же, Егор не может сдвинуться влево, если он стоит перед телегой. Это действие занимает 1 секунду.
Покрасить доску. Если Егор сейчас стоит перед непокрашенной доской и у него в руках есть банка с краской, то он может покрасить эту доску. Это действие занимает 1 секунду.
Раньше Егор был пасечником, а потому ему не понаслышке известна фраза «Время —— деньги!». Соответственно, он хочет как можно быстрее покрасить весь забор. Вы ведь помните, что Егор не окончил вуз? Именно поэтому вам придётся посчитать, какое минимальное время потребуется на покраску всего забора. Обратите внимание на то, что Егор имеет право закончить покраску в любом месте забора и что ему не надо после этого возвращаться к телеге.
Замечание
Рассмотрим первый пример. В заборе всего пять досок. Чтобы покрасить его как можно быстрее, Егору нужно сначала взять третью банку, потом покрасить первые две доски на это у него уйдёт 4 секунды. Затем он должен вернуться назад и взять банку, которой хватит на три доски, на это ещё 2 секунды. Затем надо докрасить забор на это он потратит ещё 8 секунд, первые две из которых будет идти рядом с уже покрашенными досками. Итого потребуется 4+2+8=14 секунд.
Во втором примере у Егора есть возможность покрасить только одну доску, но этого не хватит на покраску всего забора.
Ответ-код смотрите в картинке
