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

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

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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 23.05.2011 9:57
Сообщение #2


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

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

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


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

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


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


Бывалый
***

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

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


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

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

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

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


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

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

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


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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
DarkWishmaster
сообщение 24.05.2011 12:47
Сообщение #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 - 24.05.2011 12:56


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


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

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

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


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


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


Бывалый
***

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

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


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

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

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

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


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


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

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

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


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


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


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

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

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


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

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

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


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


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

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

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


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


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


Бывалый
***

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

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


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

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


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


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

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

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


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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
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. Но тут наверное нужна и высота слитков что бы можно было один на другой ставить.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 27.05.2011 11:43
Сообщение #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 
 К началу страницы 
+ Ответить 
DarkWishmaster
сообщение 27.05.2011 12:55
Сообщение #15


Бывалый
***

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

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


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

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

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


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

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

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


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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
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). Значит, желтый и зеленый можно выкинуть из нашего списка и не заботиться о них совсем.

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

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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
DarkWishmaster
сообщение 28.05.2011 10:30
Сообщение #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 
 К началу страницы 
+ Ответить 

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

 



- Текстовая версия 17.07.2024 18:54
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"