Question

В магазин волшебства и магии поступили в продажу новые волшебные палочки. Для того, чтобы они не просто работали, а обладали сверхсилой, нужно покупать специальные карточки. Сейчас в магазине есть такой набор: Карточка на 1 секунду сверхсилы, стоит 1 добль Карточка на 3 секунды сверхсилы, стоит 2 добля Карточка на 3 секунды сверхсилы, стоит 4 добля Карточка на 9 секунд сверхсилы, стоит 8 доблей Карточка на 14 секунд сверхсилы, стоит 16 доблей Карточка на 35 секунд сверхсилы, стоит 32 добля Карточка на 61 секунду сверхсилы, стоит 64 добля Карточка на 128 секунд сверхсилы, стоит 128 доблей Юный маг Антуан уже купил новую волшебную палочку, а теперь хочет купить несколько карточек так, чтобы в сумме они давали не меньше 189 секунд сверхсилы. Какое наименьшее количество доблей ему для этого нужно? Можно покупать карточки так, чтобы они давали больше, чем 189 секунд, если это выгоднее. Можно покупать несколько одинаковых карточек.

Answer 1

126 доблей по 3 сек вот так

Answer 2

Для решения этой задачи нужно определить, какие карточки и в каком количестве Антуану следует купить, чтобы сумма времени сверхсилы была не меньше 189 секунд.

Мы можем использовать жадный метод, покупая сначала карточки с самым большим временем сверхсилы, и двигаясь к карточкам с меньшим временем до тех пор, пока сумма времени не достигнет или превысит 189 секунд.

Начнем с самой дорогой карточки на 128 секунд сверхсилы. Мы видим, что сумма времени составит 128 секунд.

Теперь нам осталось добиться 189 - 128 = 61 секунд сверхсилы.

Следующая по стоимости карточка - это 61 секунда сверхсилы. Мы можем купить одну такую карточку, и сумма времени составит 128 + 61 = 189 секунд.

Таким образом, Антуану потребуется купить одну карточку на 128 секунд сверхсилы и одну карточку на 61 секунду сверхсилы, что составит 128 + 61 = 189 доблей.

Ответ: Антуану потребуется 189 доблей, чтобы получить не менее 189 секунд сверхсилы.