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