У вас есть b коробок и n банкнот в один доллар.
Основная идея решения аналогична той, что использовалась в задаче о золотом слитке. Вы используете бинарную систему счисления. Положите в первую коробку 1 доллар, во вторую 2, в третью — 4 и т. д. Любую нужную сумму можно представить как сумму различных степеней числа 2.
Отличие от приятной загадки с золотым бруском заключается в том, что данная головоломка проверяет, как вы «справляетесь с исключениями». Одна из сложностей связана с тем, что не все n оказываются суммой последовательных степеней числа 2. У вас, вероятно, образуется какой-то «остаток» денег после того, как вы разложите по коробкам все возможные для данного n последовательные степени числа 2. Еще одна проблема — вам может не хватить коробок.
Допустим, у вас 100 долларов. У вас будут коробки, в которые вы положите 1, 2, 4, 8,16, 32. доллара, но у вас окажется недостаточно денег для того, чтобы в следующую коробку положить 64 доллара, поскольку вы уже положили в предыдущие коробки 1 + 2 + 4 + 8 + 16 + 32 = 63 доллара. Это значит, что у вас есть остаток в 37 долларов, а это число — нечетное и никак не может быть степенью двойки.
Каким же образом вы сможете получить любую требуемую сумму от 0 долларов до 100? Используя первые шесть коробок, вы можете выплатить любую сумму от 0 до 63 долларов (чтобы выплатить 0 долларов, вы «передаете» ноль коробок!!!).
А что если вам нужно выплатить 64 доллара? Сначала вы отдаете седьмую коробку, в которой 37 долларов. Затем вычитаете 37 долларов из 64 долларов, и остается 27 долларов. Эту сумму вы можете выплатить, используя первые шесть коробок, суммы в которых соответствуют степеням числа 2. В данном конкретном случае вы отдаете коробки, сумма денег в которых равна 37, 16, 8, 2 и 1 доллару. Аналогичный принцип можно использовать для любой суммы в пределах 100 долларов.
Когда интервьюер спрашивает вас об «ограничениях» для b и n, он имеет в виду: «Каким образом вы можете определить, будет ли данный план работать для конкретных значений b и n?». Например, очевидно, что, если у вас есть миллион долларовых банкнот и всего одна коробка, такой план работать не будет. У вас недостаточно коробок для такой суммы. Обратите внимание, что обратная проблема вас не должна беспокоить: если у вас мало долларов и много коробок — все в порядке.
Вам нужно найти общую формулу, которая связывает b и n. Набросайте таблицу, показывающую, какую сумму вы можете выплатить, если у вас есть данное количество коробок.
