Задача 5 Новоселье из Турнир Stavsu RCI 2007 - март
Автор
Сообщение
Zakhr Новичок
Зарегистрирован: 24.08.2006 Сообщения: 12
Добавлено: 16.04.2007 16:11:28Как её решать кто знает?
Я пробовал вычитать из координат допустимые значения маленьких параллепипедов, но почемуто это не проходит, хотелось бы узнать авторское решение ну или тех кто решил её.
infom Новичок
Зарегистрирован: 13.03.2006 Сообщения: 3
Добавлено: 17.04.2007 11:30:23Задачу можно поделить на две части:
1. Отдельно решать если максимальная сторона фигур меньше чем максимальная сторона всего объема, т.е. в принципе все фигуры можно распологать сторого по координатной сетке объема
2. Если максимальная длина больше, то пытаться расположить фигуры по диагонали.
Решения:
1. Тут все довольно просто. Рекурсия, в которую передается состояние объема, номер фигуры которую пытаемся вставить и её направление. У каждой фигуры может быть шесть вариантов укладывания в объем в данную ячейку.
Мой алгоритм просто сначала сортировал все фигуры, затем вызывал рекурсию 6 раз с пустым объемом, номером фигуры 1 и направлениями с 1 по 6. Рекурсия вызывает себя же 6 раз для вставки след фигуры с уже заполненным объемом текущей фигуры и так далее. Как только успешно вставиласт последняя фигуры - выход.
2. Вариант довольно сложно объяснить, я там пользовался геометрией и считал может ли поместиться первая самая большая фигура по диагонали, а потом рядом ложил след фигуру, код простой, но я реализовал алгоритм с очень большим количеством допущений, хорошо что все мои допущения оказались правильными.
Регистрация
Забыли пароль?
