сегодня в 13:36
В Вашем распоряжении есть N квадратов со стороной 1. Сколько различных прямоугольников можно получить, используя эти квадраты (не обязательно все N)?
Два прямоугольника считаются различными, если один не может быть получен из другого поворотом или переносом. При получении прямоугольников Вы не можете деформировать квадраты или класть их друг на друга.
Решение:
Задача сводится к подсчету количества делителей числа N. Это будет соответствовать количеству прямоугольников при использовании ровно N квадратов.
Количество делителей нужно посчитать без повторов, иначе получим равные прямоугольники с точностью до поворота (для эффективности делители считаются до
).
По условию можно использовать не все N квадратов, поэтому будем подсчитывать ответ для всех чисел 1..N и суммировать результаты.
Так как в одном файле поступает сразу несколько тестов, то самый удобный подход здесь – сначала подсчитать ответы для всего диапазона 1≤N≤10000 (получается алгоритм, схожий с решетом Эратосфена), а затем при вводе очередного теста сразу выводить готовый ответ.
Два прямоугольника считаются различными, если один не может быть получен из другого поворотом или переносом. При получении прямоугольников Вы не можете деформировать квадраты или класть их друг на друга.
Решение:
Задача сводится к подсчету количества делителей числа N. Это будет соответствовать количеству прямоугольников при использовании ровно N квадратов.
Количество делителей нужно посчитать без повторов, иначе получим равные прямоугольники с точностью до поворота (для эффективности делители считаются до
).По условию можно использовать не все N квадратов, поэтому будем подсчитывать ответ для всех чисел 1..N и суммировать результаты.
Так как в одном файле поступает сразу несколько тестов, то самый удобный подход здесь – сначала подсчитать ответы для всего диапазона 1≤N≤10000 (получается алгоритм, схожий с решетом Эратосфена), а затем при вводе очередного теста сразу выводить готовый ответ.
Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.
This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers. Five Filters recommends: 'You Say What You Like, Because They Like What You Say' - http://www.medialens.org/index.php/alerts/alert-archive/alerts-2013/731-you-say-what-you-like-because-they-like-what-you-say.html
Комментариев нет:
Отправить комментарий