Сервер олимпиад

Ставропольский государственный университет

Имя
Пароль

Server Off-Line
Server time: 15 Oct 2024 07:01:45

Форум

Задача 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. Вариант довольно сложно объяснить, я там пользовался геометрией и считал может ли поместиться первая самая большая фигура по диагонали, а потом рядом ложил след фигуру, код простой, но я реализовал алгоритм с очень большим количеством допущений, хорошо что все мои допущения оказались правильными.
Страницы: [ 1 ]
Rambler's Top100 | Карта сайта | Контакты | Copyright © 2005-2007, Ставропольский государственный университет.