Клад Опции

[DarkWishmaster]

Привет. Вот задача с олимпиады.
Кладоискатели нашли в одном из замкнутых помещений средневекого замка N золотых слитков различных размеров. Каждый слиток представляем прямоугольный паралелипипед с рамзерами X*Y*Z. Для того чтобы извлечь слитки из замка, кладоискатели должны пробить в каменой стене одно или больше прямоугольных отверстий, которые не должны иметь точек соприкосновения. Слиток можно извлечь через отверстие только в том случае если , если ширина и высота отверстия равны или больше чем ширина и высота одной из прямоугольных граней паралелипипеда. Очевидно, слитки можно переворачивать произвольным образом.
Для того что-бы облегчить себе работу, кладоискатели желают что-бы площадь пробиваемых отверстий была наименьшей.
Пример:
n=3
1 4 4
5 3 2
1 2 2
Минимальная площадь: S=8
Вообще нету никаких идей на счет этой задачи. Может у вас есть? Только не надо сразу код, можно просто алгоритм.
1<=n<=5000;
1<=x,y,z<=10000;
время выполнения не должно превышать 3 сек.
обьем оперативной памяти не должен превышать 32 мегабайт.

Сообщение отредактировано: DarkWishmaster - 23.05.2011 4:01

[TarasBer]

Замени 3х2 на 2х3, тогда пролезет в 2х4

[DarkWishmaster]

Замени 3х2 на 2х3, тогда пролезет в 2х4

Както так:
Ну допустим сортируем так чтобы грани были наименьшие, и как дальше? 5000 слитков перебором брать?

Сообщение отредактировано: DarkWishmaster - 24.05.2011 17:32