![]() |
![]() |
LLL |
![]()
Сообщение
#1
|
Группа: Пользователи Сообщений: 1 Пол: Женский Репутация: ![]() ![]() ![]() |
Помогите, пожалуйста, решить задачу: (задача олимпиадная 10 класс)
на поле размером N*M (1<=N<=10,1<=M<=15) расставляются 4 корабля: однопалубный, 2-палубный,3-палубный и 4-палубный.Корабли могут располагатся вертикально и горизонтально, не соприкасаясь друг с другом углами и границами. Требуется определить количество вариантов расположения кораблей на игровом поле. |
![]() ![]() |
andriano |
![]()
Сообщение
#2
|
Гуру ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: ![]() ![]() ![]() |
Ну, вообще-то этой функции еще надо передавать текущее поле с уже расставленными ранее кораблями.
Оцениваем: (8*13)^4~117000000. Многовато. В этих условиях 1 час будет работать программа или 10 - разница существенная. Так что, думаю, во внутреннем цикле от вызова функции лучше отказаться. Я думаю, все возможные расстановки кораблей (по одному) можно заготовить заранее. 4 вложенных цикла - что ж, пока не предложено лучшего, будем исходить из этого алгоритма. А внутри - вычисление условия единственным выражением. Поле с находящимися на нем кораблями можно представить 13-ю байтами. Это либо 4 32-разрядных числа, либо 2 регистра ММХ. Собственно, логически умножаем конфигурацию поля на конфигурацию нового корабля, после чего складываем все элемены и сравниваем с 0. Если 0 - корабль поставлен удачно. Т.е. за 7 простых операций получаем ответ, можно разместить корабль или нет. Это намного дешевле вызова функции. |
Lapp |
![]()
Сообщение
#3
|
![]() Уникум ![]() ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: ![]() ![]() ![]() |
Это либо 4 32-разрядных числа, либо 2 регистра ММХ. andriano неисправим.. Хлебом не корми - дай ускорить асфальтовый каток )). А тебя просили об этом? ![]() Вариант без всякой оптимизации (тупой перебор по всем клеткам массива boolean с рекурсией без отсечений) у меня отработал меньше, чем за полминуты (проц 1.8ГГц). Я даже не стал отключать range check.. )) Ответ получился такой: 64998706. Я только не уверен, правильно ли будет выкладывать тут код олимпиадной задачи.. LLL, пожалуйста, скажи - что это за олимпиада, где и когда она проходила/проходит? А также скажи, плз, какие в условии ограничения на время и память. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
![]() ![]() |
![]() |
Текстовая версия | 13.07.2025 5:03 |