IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Клад
сообщение
Сообщение #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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(DarkWishmaster @ 23.05.2011 0:57) *
Вот задача с олимпиады.

С какой, если не секрет?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


Цитата(Lapp @ 23.05.2011 9:57) *

С какой, если не секрет?

Републиканской из Молдовы.
П.С, там сумарная площадь отверстий*

Сообщение отредактировано: DarkWishmaster -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(DarkWishmaster @ 23.05.2011 16:21) *
Републиканской из Молдовы.
Надеюсь, она уже завершилась - да?

Задачка хорошая. Как у тебя - по-прежнему ничего? Если есть хоть какие-то (самые небольшие) соображения - пиши. Я просто не знаю, где тебя толкать..

Можно так.. Для начала, замени все слитки на прямоугольники (минимальные грани). И упорядочи их (например, x<=y).


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


Цитата(Lapp @ 23.05.2011 23:04) *

Надеюсь, она уже завершилась - да?

Задачка хорошая. Как у тебя - по-прежнему ничего? Если есть хоть какие-то (самые небольшие) соображения - пиши. Я просто не знаю, где тебя толкать..

Можно так.. Для начала, замени все слитки на прямоугольники (минимальные грани). И упорядочи их (например, 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 -


Эскизы прикрепленных изображений
Прикрепленное изображение
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Замени 3х2 на 2х3, тогда пролезет в 2х4


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


Цитата(TarasBer @ 24.05.2011 13:21) *

Замени 3х2 на 2х3, тогда пролезет в 2х4

Както так:
Ну допустим сортируем так чтобы грани были наименьшие, и как дальше? 5000 слитков перебором брать?

Сообщение отредактировано: DarkWishmaster -


Эскизы прикрепленных изображений
Прикрепленное изображение
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Ну перебрать все слитки хотя бы 1 раз тебе же всё равно придётся.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(DarkWishmaster @ 24.05.2011 14:30) *
Ну допустим сортируем так чтобы грани были наименьшие, и как дальше? 5000 слитков перебором брать?

Ты "бери" так, как можешь )). Сделай хоть какую-то рабочую схему (а не просто "ах, 5000 перебором!"). Посмотри на результаты. И если они тебя не удовлетворят - думай, как ускорить.

Забегая вперед, скажу - я сделал перебор вчера перед сном )). Результат немного странный.. До 4000 работает как из пушки (секунды), а 5000 резко замедляется (до минут). Может, это проблемы с доступом к памяти (типа, превышается размер кэша)? Сегодня посмотрю, когда освобожусь.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Ну вот, выдалась минута..
Добавил чистку на каждом шагу, теперь максимальная конфигурация (заданная случайным образом) считается ровно 3 сек (на моем компе). Думаю, на этом можно пока остановиться - проверить я все равно не могу )).


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


Цитата(Lapp @ 25.05.2011 3:42) *

Ну вот, выдалась минута..
Добавил чистку на каждом шагу, теперь максимальная конфигурация (заданная случайным образом) считается ровно 3 сек (на моем компе). Думаю, на этом можно пока остановиться - проверить я все равно не могу )).


Сортируем, потом по каким критериям брать слитки?
Можно взять слиток с наибольшей площадью, а на нем ставить все остальные менее большие слитки так что-бы всё совпало, потом из чего осталось опять выбираем самый большой слиток и.т
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(DarkWishmaster @ 26.05.2011 18:46) *
Сортируем, потом по каким критериям брать слитки?
Можно взять слиток с наибольшей площадью, а на нем ставить все остальные менее большие слитки так что-бы всё совпало, потом из чего осталось опять выбираем самый большой слиток и.т
Это немного лучше, но все равно ты еще не навел порядок в мыслях.

Говори точнее. Что и по чему сортируем, что значит авыражение "на нем ставить"? Перед написанием кода весьма желательно достичь полной ясности в алгоритме. И уж конечно, в терминах. Даже если алгоритм не вполне определен, оперировать нужно строгими понятиями.

Жду четкого описания. Из того, что ты сказал в предыдущем посте, я мало, что понял. А строить догадки - извини, не тот случай.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


так как нам нужна что бы площадь была наименьшей, то будем использовать только 2 ребра, те которые дают минимальную площадь:
1x2x2 -> 1x2
5x3x2 -> 2x3
1x4x4 -> 1x4 и.т
Потом всё это сортируем в порядке убывания размера площади:
2x3
1x4
1x2
Теперь надо их поставить так что-бы площадь была наименьшей. Я тут думаю взять самый большой кусок:
2x3 и дальше ставить на нем слитки ( если так вообще можно). слиток 1х4 нельзя ставить, так как 4>3, зато можно както поставить 1х2 что-бы было место для 1х4. Но тут наверное нужна и высота слитков что бы можно было один на другой ставить.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(DarkWishmaster @ 27.05.2011 11:49) *
так как нам нужна что бы площадь была наименьшей, то будем использовать только 2 ребра, те которые дают минимальную площадь:
Так, хорошо. Но этого недостаточно. То, что ты пишешь дальше, видимо, подразумевает, что ты все же полученную пару (x,y) переставляешь так, чтобы всегда соблюдалось x<=y:
Цитата
1x2x2 -> 1x2
5x3x2 -> 2x3
1x4x4 -> 1x4 и.т
Это важно (я об этом писал выше). Без этого ты (например) будешь считать 2х3 и 3х2 разными, хотя это одинаковые слитки и пролезут в одну дырку.

Цитата
Потом всё это сортируем в порядке убывания размера площади:
2x3
1x4
1x2
А это зачем? Обосновывай свои действия.

Цитата
Теперь надо их поставить так что-бы площадь была наименьшей. Я тут думаю взять самый большой кусок:
2x3 и дальше ставить на нем слитки ( если так вообще можно). слиток 1х4 нельзя ставить, так как 4>3, зато можно както поставить 1х2 что-бы было место для 1х4. Но тут наверное нужна и высота слитков что бы можно было один на другой ставить.
Это я не понял. Ничего не надо ставить "один на другой". Все слитки просовываются в дырки поодиночке. Разберись с условием до конца. Или я тебя не понял?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


Цитата(Lapp @ 27.05.2011 11:43) *

Это я не понял. Ничего не надо ставить "один на другой". Все слитки просовываются в дырки поодиночке. Разберись с условием до конца. Или я тебя не понял?

Ну так если в каждую дырку только один слиток ставить, то значит пример не правильный, как поставить поодиночке эти слитки чтобы площадь 8 была:
1x4x4
5x3x2
1x2x2
1x4+2x3+1x2=12
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Не имелось в виду, что по одному слитку на дырку. Слитки просовываются по одному. Может, все в одну дырку. Но ставить их друг на друга - нафига?


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Влад, смотри, вот тебе пример.

Есть слитки (максимальный размер уже отброшен)
красный 1 х 8
желтый 6 х 1
зеленый 2 х 3
синий 5 х 2

Сначала поворачиваем их так, чтоб первое число было не больше второго:
красный 1 х 8
желтый 1 х 6
зеленый 2 х 3
синий 2 х 5

Нарисуем их так, чтоб левый нижний угол совпал: Прикрепленное изображение (масштаб не очень хорошо выдержан, извини)

Из рисунка ясно, что желтый заведомо пролезет в ту дырку, в которую пролез красный, и та же самая ситуация с зеленым и синим (для опредлелния этого как раз и нужна упорядоченость x<=y). Значит, желтый и зеленый можно выкинуть из нашего списка и не заботиться о них совсем.

Остаются красный и синий: Прикрепленное изображение

Вопрос: что выгоднее - сделать отдельную дырку для каждого (по его размерам) или же одну большую дырку (я дополнил тонкой линией), в которую пролезут оба?

Ответ на этот вопрос зависит от соотношения площадей розовой (двойная польза) и голубой (бесполезная площадь) частей дырки. Если голубая меньше розовой, то - да, выгодно. Если наоборот - невыгодно. Если равны - все равно )).

Но этот вопрос (как и ответ на него) чисто для удовлетворения любознательности. Для решения перебором это все не нужно. Просто обсчитываешь оба случая и сравниваешь результаты. Все )).


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


Цитата(Lapp @ 28.05.2011 5:41) *

Влад, смотри, вот тебе пример.

Есть слитки (максимальный размер уже отброшен)
красный 1 х 8
желтый 6 х 1
зеленый 2 х 3
синий 5 х 2

Сначала поворачиваем их так, чтоб первое число было не больше второго:
красный 1 х 8
желтый 1 х 6
зеленый 2 х 3
синий 2 х 5

Нарисуем их так, чтоб левый нижний угол совпал: Прикрепленное изображение (масштаб не очень хорошо выдержан, извини)

Из рисунка ясно, что желтый заведомо пролезет в ту дырку, в которую пролез красный, и та же самая ситуация с зеленым и синим (для опредлелния этого как раз и нужна упорядоченость x<=y). Значит, желтый и зеленый можно выкинуть из нашего списка и не заботиться о них совсем.

Остаются красный и синий: Прикрепленное изображение

Вопрос: что выгоднее - сделать отдельную дырку для каждого (по его размерам) или же одну большую дырку (я дополнил тонкой линией), в которую пролезут оба?

Ответ на этот вопрос зависит от соотношения площадей розовой (двойная польза) и голубой (бесполезная площадь) частей дырки. Если голубая меньше розовой, то - да, выгодно. Если наоборот - невыгодно. Если равны - все равно )).

Но этот вопрос (как и ответ на него) чисто для удовлетворения любознательности. Для решения перебором это все не нужно. Просто обсчитываешь оба случая и сравниваешь результаты. Все )).

Спасибо огромное! Теперь понял, пойду писать код.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 2:04
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name