1595. Заполнение коробки

Имеется коробка размера length * width * height, которую необходимо заполнить кубами. Длины сторон имеющихся кубов являются степенями двойки (1*1*1, 2*2*2, 4*4*4, 8*8*8, …). Вам задается количество имеющихся у Вас кубов размера 2ⁱ * 2ⁱ * 2ⁱ. Найти наименьшее количество кубов, которыми можно полностью заполнить коробку, или вывести -1, если этого совершить невозможно.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит значения length, width, height (1 ≤ length, width, height ≤ 10⁶), а также количество k (1 ≤ k ≤ 20) имеющихся у Вас типов кубов. Вторая строка содержит k натуральных чисел, не больших 10⁶: i-ое число задает количество кубов размера 2ⁱ * 2ⁱ * 2ⁱ (i принимает значения от 0 до k – 1), которыми Вы владеете.

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

Пример входа	Пример выхода
4 4 8 3 10 10 10 4 4 8 3 10 10 1 10 10 11 1 1099	2 9 -1

РЕШЕНИЕ

жадный алгоритм

Анализ алгоритма

Пусть cubes[i] содержит количество кубов размера 2ⁱ * 2ⁱ * 2ⁱ. Если коробка имеет размер length * width * height, а сторона куба равна len = 2ⁱ, то в коробку можно вложить максимум amount = (length / len) * (width / len) * (height / len) таких кубов. При этом если amount > cubes[i], то мы можем использовать максимум cubes[i] кубов (только те кубы, которые имеются в наличии).

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

а) коробка будет полностью заполнена;

б) все имеющиеся кубы будут вложены в коробку;

в) ни один из оставшихся кубов нельзя вложить в коробку;

Пусть уже сложено в коробку done кубов размера 2ⁱ. Известно, что в куб размера 2ⁱ можно вложить 8 кубов размера 2^i-1. Тогда при последующем вкладывании кубов размера 2^i-1 будем считать, что в коробку уже вложено 8*done кубов размера 2^i-1.

Реализация алгоритма

В массиве cubes храним информацию о кубах, которые имеются в наличии.

vector<int> cubes;

Функция minCubes возвращает наименьшее количество кубов, которыми можно полностью заполнить коробку, или -1, если этого совершить невозможно.

int minCubes(int length, int width, int height)

{

long long done = 0;

int res = 0;

for (int i = cubes.size() - 1; i >= 0; i--)

{

int len = 1 << i;

Вычисляем количество amount кубов размера 2ⁱ * 2ⁱ * 2ⁱ, которое можно положить в коробку.

int amount = (length / len) * (width / len) * (height / len);

Поскольку до этого в коробку уже положено done кубов со стороной 2ⁱ, то еще в нее может войти максимум amount – done кубов со стороной 2ⁱ.

amount -= done;

Если amount больше количества имеющихся кубов со стороной 2ⁱ, то максимум мы можем положить в коробку cubes[i] кубов.

if (amount > cubes[i]) amount = cubes[i];

К done кубов со стороной 2ⁱ кладем amount кубов с такой же длиной стороны. Далее считаем, что у нас в коробке находится (done + amount) * 8 кубов со стороной 2^i-1.

done = (done + amount) * 8;

res += amount;

}

По окончанию цикла переменная done содержит количество кубов со стороной 1/2, которое положено в коробку. Если объем положенных кубов меньше объема коробки, то заполнить коробку не удалось, поэтому возвращаем -1.

if (done < 8LL * length * width * height) return -1;

return res;

}

Основная часть программы.

while(scanf("%d %d %d %d",&length,&width,&height,&k) == 4)

{

cubes.resize(k);

for(i = 0; i < k; i++) scanf("%d",&cubes[i]);

res = minCubes(length,width,height);

printf("%d\n",res);

}