Клад |
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 - Эскизы прикрепленных изображений |
TarasBer |
Сообщение
#6
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Замени 3х2 на 2х3, тогда пролезет в 2х4
-------------------- |
DarkWishmaster |
Сообщение
#7
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
Замени 3х2 на 2х3, тогда пролезет в 2х4 Както так: Ну допустим сортируем так чтобы грани были наименьшие, и как дальше? 5000 слитков перебором брать? Сообщение отредактировано: DarkWishmaster - Эскизы прикрепленных изображений |
TarasBer |
Сообщение
#8
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Ну перебрать все слитки хотя бы 1 раз тебе же всё равно придётся.
-------------------- |
Lapp |
Сообщение
#9
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Ну допустим сортируем так чтобы грани были наименьшие, и как дальше? 5000 слитков перебором брать? Ты "бери" так, как можешь )). Сделай хоть какую-то рабочую схему (а не просто "ах, 5000 перебором!"). Посмотри на результаты. И если они тебя не удовлетворят - думай, как ускорить. Забегая вперед, скажу - я сделал перебор вчера перед сном )). Результат немного странный.. До 4000 работает как из пушки (секунды), а 5000 резко замедляется (до минут). Может, это проблемы с доступом к памяти (типа, превышается размер кэша)? Сегодня посмотрю, когда освобожусь. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
Сообщение
#10
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Ну вот, выдалась минута..
Добавил чистку на каждом шагу, теперь максимальная конфигурация (заданная случайным образом) считается ровно 3 сек (на моем компе). Думаю, на этом можно пока остановиться - проверить я все равно не могу )). -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
DarkWishmaster |
Сообщение
#11
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
Ну вот, выдалась минута.. Добавил чистку на каждом шагу, теперь максимальная конфигурация (заданная случайным образом) считается ровно 3 сек (на моем компе). Думаю, на этом можно пока остановиться - проверить я все равно не могу )). Сортируем, потом по каким критериям брать слитки? Можно взять слиток с наибольшей площадью, а на нем ставить все остальные менее большие слитки так что-бы всё совпало, потом из чего осталось опять выбираем самый большой слиток и.т |
Lapp |
Сообщение
#12
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Сортируем, потом по каким критериям брать слитки? Это немного лучше, но все равно ты еще не навел порядок в мыслях.Можно взять слиток с наибольшей площадью, а на нем ставить все остальные менее большие слитки так что-бы всё совпало, потом из чего осталось опять выбираем самый большой слиток и.т Говори точнее. Что и по чему сортируем, что значит авыражение "на нем ставить"? Перед написанием кода весьма желательно достичь полной ясности в алгоритме. И уж конечно, в терминах. Даже если алгоритм не вполне определен, оперировать нужно строгими понятиями. Жду четкого описания. Из того, что ты сказал в предыдущем посте, я мало, что понял. А строить догадки - извини, не тот случай. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
DarkWishmaster |
Сообщение
#13
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
так как нам нужна что бы площадь была наименьшей, то будем использовать только 2 ребра, те которые дают минимальную площадь:
1x2x2 -> 1x2 5x3x2 -> 2x3 1x4x4 -> 1x4 и.т Потом всё это сортируем в порядке убывания размера площади: 2x3 1x4 1x2 Теперь надо их поставить так что-бы площадь была наименьшей. Я тут думаю взять самый большой кусок: 2x3 и дальше ставить на нем слитки ( если так вообще можно). слиток 1х4 нельзя ставить, так как 4>3, зато можно както поставить 1х2 что-бы было место для 1х4. Но тут наверное нужна и высота слитков что бы можно было один на другой ставить. |
Lapp |
Сообщение
#14
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
так как нам нужна что бы площадь была наименьшей, то будем использовать только 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. Но тут наверное нужна и высота слитков что бы можно было один на другой ставить. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
DarkWishmaster |
Сообщение
#15
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
Это я не понял. Ничего не надо ставить "один на другой". Все слитки просовываются в дырки поодиночке. Разберись с условием до конца. Или я тебя не понял? Ну так если в каждую дырку только один слиток ставить, то значит пример не правильный, как поставить поодиночке эти слитки чтобы площадь 8 была: 1x4x4 5x3x2 1x2x2 1x4+2x3+1x2=12 |
TarasBer |
Сообщение
#16
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Не имелось в виду, что по одному слитку на дырку. Слитки просовываются по одному. Может, все в одну дырку. Но ставить их друг на друга - нафига?
-------------------- |
Lapp |
Сообщение
#17
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Влад, смотри, вот тебе пример.
Есть слитки (максимальный размер уже отброшен) красный 1 х 8 желтый 6 х 1 зеленый 2 х 3 синий 5 х 2 Сначала поворачиваем их так, чтоб первое число было не больше второго: красный 1 х 8 желтый 1 х 6 зеленый 2 х 3 синий 2 х 5 Нарисуем их так, чтоб левый нижний угол совпал: (масштаб не очень хорошо выдержан, извини) Из рисунка ясно, что желтый заведомо пролезет в ту дырку, в которую пролез красный, и та же самая ситуация с зеленым и синим (для опредлелния этого как раз и нужна упорядоченость x<=y). Значит, желтый и зеленый можно выкинуть из нашего списка и не заботиться о них совсем. Остаются красный и синий: Вопрос: что выгоднее - сделать отдельную дырку для каждого (по его размерам) или же одну большую дырку (я дополнил тонкой линией), в которую пролезут оба? Ответ на этот вопрос зависит от соотношения площадей розовой (двойная польза) и голубой (бесполезная площадь) частей дырки. Если голубая меньше розовой, то - да, выгодно. Если наоборот - невыгодно. Если равны - все равно )). Но этот вопрос (как и ответ на него) чисто для удовлетворения любознательности. Для решения перебором это все не нужно. Просто обсчитываешь оба случая и сравниваешь результаты. Все )). -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
DarkWishmaster |
Сообщение
#18
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
Влад, смотри, вот тебе пример. Есть слитки (максимальный размер уже отброшен) красный 1 х 8 желтый 6 х 1 зеленый 2 х 3 синий 5 х 2 Сначала поворачиваем их так, чтоб первое число было не больше второго: красный 1 х 8 желтый 1 х 6 зеленый 2 х 3 синий 2 х 5 Нарисуем их так, чтоб левый нижний угол совпал: (масштаб не очень хорошо выдержан, извини) Из рисунка ясно, что желтый заведомо пролезет в ту дырку, в которую пролез красный, и та же самая ситуация с зеленым и синим (для опредлелния этого как раз и нужна упорядоченость x<=y). Значит, желтый и зеленый можно выкинуть из нашего списка и не заботиться о них совсем. Остаются красный и синий: Вопрос: что выгоднее - сделать отдельную дырку для каждого (по его размерам) или же одну большую дырку (я дополнил тонкой линией), в которую пролезут оба? Ответ на этот вопрос зависит от соотношения площадей розовой (двойная польза) и голубой (бесполезная площадь) частей дырки. Если голубая меньше розовой, то - да, выгодно. Если наоборот - невыгодно. Если равны - все равно )). Но этот вопрос (как и ответ на него) чисто для удовлетворения любознательности. Для решения перебором это все не нужно. Просто обсчитываешь оба случая и сравниваешь результаты. Все )). Спасибо огромное! Теперь понял, пойду писать код. |
Текстовая версия | 17.06.2024 13:54 |