Клад Опции

[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 0:01

[TarasBer]

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

[DarkWishmaster]

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

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

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

[Lapp]

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

Ты "бери" так, как можешь )). Сделай хоть какую-то рабочую схему (а не просто "ах, 5000 перебором!"). Посмотри на результаты. И если они тебя не удовлетворят - думай, как ускорить.

Забегая вперед, скажу - я сделал перебор вчера перед сном )). Результат немного странный.. До 4000 работает как из пушки (секунды), а 5000 резко замедляется (до минут). Может, это проблемы с доступом к памяти (типа, превышается размер кэша)? Сегодня посмотрю, когда освобожусь.