Клад |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Клад |
DarkWishmaster |
22.05.2011 23:57
Сообщение
#1
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
Привет. Вот задача с олимпиады.
Кладоискатели нашли в одном из замкнутых помещений средневекого замка 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 |
Lapp |
28.05.2011 5:41
Сообщение
#2
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Влад, смотри, вот тебе пример.
Есть слитки (максимальный размер уже отброшен) красный 1 х 8 желтый 6 х 1 зеленый 2 х 3 синий 5 х 2 Сначала поворачиваем их так, чтоб первое число было не больше второго: красный 1 х 8 желтый 1 х 6 зеленый 2 х 3 синий 2 х 5 Нарисуем их так, чтоб левый нижний угол совпал: (масштаб не очень хорошо выдержан, извини) Из рисунка ясно, что желтый заведомо пролезет в ту дырку, в которую пролез красный, и та же самая ситуация с зеленым и синим (для опредлелния этого как раз и нужна упорядоченость x<=y). Значит, желтый и зеленый можно выкинуть из нашего списка и не заботиться о них совсем. Остаются красный и синий: Вопрос: что выгоднее - сделать отдельную дырку для каждого (по его размерам) или же одну большую дырку (я дополнил тонкой линией), в которую пролезут оба? Ответ на этот вопрос зависит от соотношения площадей розовой (двойная польза) и голубой (бесполезная площадь) частей дырки. Если голубая меньше розовой, то - да, выгодно. Если наоборот - невыгодно. Если равны - все равно )). Но этот вопрос (как и ответ на него) чисто для удовлетворения любознательности. Для решения перебором это все не нужно. Просто обсчитываешь оба случая и сравниваешь результаты. Все )). -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 28.04.2024 10:25 |