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