Question

1) Есть кучка из 1057 орехов. За одну операцию можно любую из уже имеющихся кучек разделить на две. Если при этом получатся две неравные кучки, то взимается штраф 1 рубль. Какова наименьшая возможная сумма штрафа, которую придется заплатить, чтобы получить 1057 кучек по одному ореху в каждом? 2) Во дворце шаха Мансура нужно повесить 15 зеркал различных размеров и форм. Для этого мастером древесных работ было заготовлено и повешено 15 рам для них, а стекольщиком — вырезано ровно 15 зеркал нужной формы и размера. Но мастер, который устанавливает зеркала, не знает, что они уже вырезаны по размерам рам. Поэтому он работает так: подходит к очередной раме и перебирает неиспользованные зеркала до тех пор, пока не найдет достаточно большое (то есть либо в точности подходящее, либо такое, из которого можно вырезать подходящее), если же такого зеркала нет, то переходит к следующей раме, и так, пока не обойдет все рамы. Составлять зеркало из нескольких частей нельзя. Какое максимальное число рам может остаться пустыми?помогите плиззз

Answer 1

1057=1024+33=1024+32+1
Отделяем 1 орех, платим 1 руб. Отделяем 32, платим 1 руб. Дальше делим 32 ореха пополам, на кучки по 16, по 8, по 4, по 2 и по 1.
И за все это не платим ничего, потому что каждый раз делим кучку на 2 одинаковые.
Кучку 1024 ореха мы тоже делим пополам, вплоть до 1 ореха, и тоже не платим ничего.
Задачу про зеркала я не знаю, как решать, она намного труднее.

Answer 2

1) Для решения этой задачи мы можем использовать метод жадного алгоритма. Начинаем с исходной кучки из 1057 орехов. Нам нужно получить 1057 кучек по одному ореху в каждой.

Штраф взимается только в случае, когда при делении кучки на две получаются две неравные кучки. Значит, на каждом шаге мы должны делить кучку на две равные части.

Пусть у нас есть N кучек. На первом шаге делим исходную кучку на две равные части. Теперь у нас есть две кучки по 528 орехов каждая. Получается, что на первом шаге мы заплатим 1 рубль штрафа, так как получили две неравные кучки.

На втором шаге мы должны разделить каждую из двух кучек по 528 орехов на две равные части. Таким образом, у нас будет 4 кучки по 264 ореха каждая. Снова получаем две неравные кучки и платим 1 рубль штрафа.

Продолжая делить каждую кучку по 528 орехов на две равные части, на каждом шаге мы получаем две неравные кучки и платим 1 рубль штрафа.

Количество шагов, которые нам нужно совершить, чтобы получить 1057 кучек по одному ореху, можно выразить следующим образом:

1057 / 2^k = 1, где k - количество шагов, N - исходное количество кучек.

Решаем это уравнение относительно k и получаем:

k = log2(N)

Таким образом, для 1057 кучек нам понадобится выполнить k = log2(1057) ≈ 10 шагов.

Значит, наименьшая возможная сумма штрафа будет равна количеству шагов, умноженному на 1 рубль: 10 * 1 = 10 рублей.

2) Для решения этой задачи мы можем использовать метод перебора. Воспользуемся алгоритмом жадного выбора, описанным в условии задачи.

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

Если подходящего зеркала нет, переходим к следующей раме.

Повторяем этот процесс до тех пор, пока не обойдем все рамы.

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

В данной задаче у нас есть 15 рам и 15 зеркал. На первом шаге мы устанавливаем любое зеркало в первую раму.

Затем, при переборе неиспользованных зеркал для следующей рамы, мы обязательно найдем подходящее, так как каждая рама имеет соответствующее зеркало.

Таким образом, все 15 зеркал будут установлены в 15 рам. Значит, максимальное число пустых рам будет равно 0.