Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
Вернуться
Тема: Вопрос по задаче 1098. Шахматная расстановка. Сделал рекурсией: ставлю фигуру на подходящую позицию (сначала, если есть - ферзь, затем - ладья). Затем пробую поставить следующую - ее ставим только в одну из следующих ячеек (начиная со следующей строки). Если строк осталось меньше, чем фигур - расстановка невозможна (т.к. каждая фигура выкинет строчку). Если все фигуры расставлены возвращаю 1. Подскажите, можно ли этот алгоритм улучшить или решение принципиально другое? Я еще думал над вариантом, когда ставим сначала все фигуры, как будто, они ладьи, а затем ищем число способов заменить ладьи на ферзи, но это тоже долго работает
1
  1  Жуков Александр И, 22 марта 2018 г. 10:18:10
      Спасибо буду знать
  2  Беляев Сергей Николаевич, 20 марта 2018 г. 11:33:10
      Это не чит, это известный прием, иногда использующийся при решении олимпиадных задач.
  3  Жуков Александр И, 19 марта 2018 г. 9:51:03
      Я вообщем-то так и сделал уже. Весьма странный подход, особенно с учетом того, что время на решение задачи 2 секунды. Т.е. никакого эффективного алгоритма не существует? Просто это выглядит как чит?
  4  Беляев Сергей Николаевич, 19 марта 2018 г. 5:00:44
      Это решение нужно использовать в качестве предподсчета (precalc), т.е. написать программу, которая найдет все решения при всех возможных значениях n, q и r. Таковых будет не более 1000, что позволит создать статический массив в другой программе, которую Вы и закачаете в качестве решения.
1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483