Задача G
Недавно закончился квалификационный раунд, где командам было предложено 12 задач. Лучшие команды решили все задачи этого раунда, однако были команды, которым это не удалось.
Становиться лучше можно путем ежедневных тренировок. Поэтому вы можете участвовать в тренировке на платформе Codeforces c задачами квалификации и решать по одной задачке в день https://codeforces.com/gym/102775
Мы продолжаем разбор задачей G. Математическое равенство
В качестве слагаемых будем рассматривать числа с суммой цифр, равной 1, то есть числа вида 10m. Любое натуральное число можно представить в виде суммы таких слагаемых:
Общее количество слагаемых в таком разложении будет равно сумме цифр числа N. Таким образом, каждое натуральное число N<=1018 можно представить в виде суммы не более, чем 9 · 18 = 162 слагаемых. Осталось учесть дополнительные ограничения на количество слагаемых. Во-первых, слагаемых должно быть хотя бы 2, значит указанное разложение не подходит для чисел вида 10m, такие числа при m > 0 являются четными, поэтому их можно представить так: 10m =5·10m−1 +5·10m−1.
Во-вторых, слагаемых должно быть строго меньше N. Сумма цифр N не может быть больше N, а равенство выполняется только для однозначных чисел. Для них получаем следующие ответы:
- 4 = 2 + 2
- 6 = 3 + 3
- 8 = 4 + 4
- 9 = 3 + 3 + 3
- для 1, 2, 3, 5, 7 решения не существует.
#icpc #росмолодежь #фадм #doit #icpc #crrc
