Question

Асем нужно составить N-значный пароль из цифр. Она решила, что это будет N-значное число, которое делится без остатка на сумму своих цифр. Но оказалось, что таких чисел несколько. Помогите Асем определить для любого N количество таких чисел (N<=5). Помогите, это олимпиада!​

Answer 1

Ответ:

Однозначное

1

Двузначное

40

Трёхзначное

111

Четырехзначное

1120

Пятизначное

12115

Answer 2

Для нахождения N-значных чисел, которые делятся на сумму своих цифр без остатка, можно воспользоваться следующим подходом:

1. Начнем с N = 1. Для однозначных чисел такие числа всегда существуют, так как любая однозначная цифра делится на саму себя без остатка.

2. Для N > 1, начнем перебирать все N-значные числа (с N цифрами) и проверять, делится ли каждое из них на сумму своих цифр без остатка. Если делится, то это число удовлетворяет условию.

3. Важно учесть, что сумма цифр N-значного числа может быть в интервале от 1 (все цифры равны 1) до 9 * N (все цифры равны 9). Таким образом, нужно перебирать возможные суммы цифр от 1 до 9 * N и для каждой суммы найти все N-значные числа, которые делятся на эту сумму без остатка.

4. Для нахождения таких чисел, можно воспользоваться вложенными циклами. Сначала перебираем возможные суммы цифр (от 1 до 9 * N), а затем для каждой суммы генерируем все N-значные числа, у которых сумма цифр равна этой сумме.

5. Для каждого N подсчитываем количество подходящих чисел и выводим результат.

Давайте рассмотрим примеры для N от 1 до 5:

1. N = 1: Любая однозначная цифра подходит, так что ответ равен 9 (от 1 до 9).

2. N = 2: Для каждой суммы цифр от 2 до 18 найдем соответствующие числа:

   • Сумма 2: 11
   • Сумма 3: 12
   • Сумма 4: 13, 22
   • Сумма 5: 14, 23, 32
   • Сумма 6: 15, 24, 33, 42
   • Сумма 7: 16, 25, 34, 43, 52
   • Сумма 8: 17, 26, 35, 44, 53, 62
   • Сумма 9: 18, 27, 36, 45, 54, 63, 72
   • Сумма 10: 72, 81
   • Сумма 11: 11
   • Сумма 12: 12

   Общее количество таких чисел для N = 2: 15.

3. N = 3: Для каждой суммы цифр от 3 до 27 найдем соответствующие числа (количество чисел будет больше для N = 3):

   • Сумма 3: 111
   • Сумма 4: 112, 121, 211
   • Сумма 5: 113, 131, 311, 122, 212, 221
   • Сумма 6: 114, 141, 411, 123, 132, 213, 231, 312, 321
   • Сумма 7: ...

   Подсчитываем количество таких чисел для N = 3.

4. Продолжаем этот алгоритм для N = 4 и N = 5.

Это задача для программирования. Алгоритм позволяет найти количество таких чисел для каждого N, и вы можете использовать программу для автоматического подсчета.