Задать вопрос
@Xiran

Как решать задачу?

Условие


Новый год уже давно прошел, а Аня так и не разобрала украшенную ёлку.

Ёлка украшена шариками четырёх цветов: красными, золотистыми, зелеными и белыми. Условно ёлку по высоте можно разделить на несколько уровней: на самом верхнем, будем считать его первым, висит одна игрушка, на втором – чуть ниже первого – две игрушки, на третьем – три, и так далее. Известно, что шары вешали на ёлку строго в порядке следования цветов: красный, золотистый, зеленый, белый, снова красный, золотистый, зеленый, белый и так далее, слева-направо, сверху вниз.

Известно, что на Аниной ёлки 52 уровня игрушек.

Анин кот, Василий, решил помочь хозяйке освободить ёлку от украшений: он решил каждый день сбрасывать с ёлки по одной или несколько игрушек. Сбрасывать случайные игрушки ему было неинтересно, поэтому он выработал для себя следующее правило: за один день нужно сбросить с одного из уровней все игрушки одного цвета и по одной игрушке каждого из оставшихся на этом уровне цветов. Василий знает, что белые шары – Анины любимые, поэтому он хочет действовать так, чтобы на ёлке как можно раньше остались только белые шары, и чтобы к моменту, когда не останется шаров других цветов, белых шаров осталось как можно больше.

К концу какого дня помощи кота на ёлке останутся только белые шары, и на скольких уровнях ёлки к этому моменту останется хотя бы по одной игрушке?

В ответ укажите два целых числа без пробела – первый по счету возможный день, к вечеру которого на ёлке останутся только белые шары, и число уровней, на которых к этому моменту останется хотя бы по одной игрушке. Например, если ответ «к концу
123 дня; 45 уровней», то в ответ необходимо записать «12345».

Вообще не понятно, как именно он их мог разбирать и в каком направлении копать.
В этом и вопрос
  • Вопрос задан
  • 318 просмотров
Подписаться 1 Средний 2 комментария
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Надо сделать несколько наблюдений: во-первых, нам без разницы, в каком порядке шары на каждом уровне - важны лишь количества там шаров всех 4 цветов. Во-вторых, если на каком-то уровне остались только белые шары - то мы этот уровень больше никогда трогать не будем. В-третьих, что бы мы не делали на одном уровне - это никак не влияет на другие уровни. Поэтому можно их все рассматривать независимо. Надо решить задачу для каждого уровня отдельно и просуммировать количество дней (и единицы, если на уровне можно что-то оставить).

Рассмотрим теперь один уровень, который описан 4 числами a,b,c,d и нам надо оставить как можно больше шаров белого цвета (их d). За один ход мы можем приравнять к 0 одно из 4 чисел и вычесть по 1 из отсавшихся ненулвевых. Ясно, что нет смысла занулять d. Т.о. за 3 хода мы можем получть 0,0,0,max(0,d-3). Но, например, если у нас было 2 2 2 3, то занулив a и b мы уменьшениями на 1 зануляем и c. Т.е. для маленьких чисел имеет смысл подумать в каком порядке их занулять. Но мне лень даже думать как именно - ведь их всего 3 числа - можно тупо перебрать все 6 перестанвок и выбрать ту, в которой за наименьшее количество ходов мы их все занулим.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы