У вас есть \(n\) прямоугольников, каждый имеет высоту \(1\). Ширина каждого прямоугольника — степень числа \(2\) (т. е. ее можно представить как \(2^x\) для некоторого неотрицательного целого \(x\)).
У вас также есть двумерная коробка ширины \(W\). Обратите внимание, что \(W\) может быть степенью числа \(2\), а может и не быть. Точно известно, что \(W\) не меньше ширины наибольшего прямоугольника.
Вы должны выбрать высоту этой коробки так, чтобы в нее можно было поместить все прямоугольники (при этом высоту необходимо минимизировать). Разрешается укладывать прямоугольники так, чтобы они не занимали все пространство коробки.
Прямоугольники нельзя вращать, кроме того, они не должны пересекаться после укладки (то есть для каждой пары прямоугольников, уложенных в коробку, их площадь пересечения должна быть нулевой).
Посмотрите пояснение для того, чтобы увидеть визуализацию условия задачи.
Примечание
Первый набор входных данных в примере разобран на следующей картинке:
На этой картинке число внутри каждого прямоугольника — это его ширина. Ширина коробки равна \(16\) (см. обозначения в нижней части картинки). Минимальная высота коробки равна \(2\) (см. обозначения в левой части картинки).
Во втором наборе входных данных можно расположить на каждом уровне по одному прямоугольнику ширины 8 и ширины 2, так потребуется всего три уровня (и высота коробки будет равна 3).