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