Подразделы

Другие разделы

Дата и время

16/10/2024 02:55:52

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printРазбор задач

print1. Разложение

Требуется выполнить двойной цикл по `P` и `Q` и выбрать числа `P` и `Q`, минимизирующие указанное выражение, а для одинакового значения выражения – с меньшим `Q`. Так как `N\ ≤\ 10^6`, то нужно рассматривать `P` и `Q`, не превышающие тысячи, т.е. внутренняя часть цикла выполняется около 500 000 раз.
Рекомендуется для `P` и `Q` использовать тип longint, чтобы не происходило переполнение при возведении в квадрат.

print2. Игра

Решение задачи требует математических рассуждений. В указанном диапазоне существуют три числа `N`, а именно 19 (минимальное число с суммой цифр 10), 299 (минимальное число с суммой цифр 20) и 3999999999999999999999999999999999 (минимальное число с суммой цифр 300), которые являются проигрышными для игрока, делающего первый ход. Принцип рассуждения показан в задаче. Например, для числа 299 следующее число нужно выбирать в диапазоне от 20 до 298. Независимо от выбора следующий игрок может назвать число 19. Если начальное число `N` отличается от указанных чисел, то в качестве выигрышного хода нужно выбрать одно из этих чисел в зависимости от суммы цифр числа `N`.

print3. Сортировка

Выполняем рекурсивный перебор всех вариантов обмена с оптимизацией. Жадный алгоритм, который выбирает любой подходящий обмен, не приводит к успеху.

print4. Дерево

Для получения структуры выражения используется рекурсивный синтаксический разбор. После этого выражение печатается достаточно простой подпрограммой.
loading