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