Question

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
- символ «?» означает ровно одну произвольную цифру;
- символ «*» означает любую последовательность цифр произвольной длины (в том числе пустую).

Например, маске `123*4?5` соответствуют числа `123405` и `12300405`.

Среди натуральных чисел, не превышающих $10^{10}$, найдите все числа, соответствующие маске `1?2157*4`, делящиеся на 2024 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 2024.

Accepted Answer

142157664 70236
1021575544 504731
1121571264 554136
1221577104 603546
1321572824 652951
1421578664 702361
1521574384 751766
1621570104 801171
1721575944 850581
1821571664 899986
1921577504 949396

Answer

Идея решения: перебрать все числа, кратные 2024, до $10^{10}$ и проверить соответствие маске `1?2157*4` с помощью регулярного выражения.

Маска `1?2157*4` означает:
- первая цифра — 1;
- вторая цифра — любая (0–9);
- третья–шестая цифры — 2157;
- далее — любая последовательность цифр (включая пустую);
- последняя цифра — 4.

В регулярном выражении это записывается как `1[0-9]2157[0-9]*4`.

Перебираем все числа, кратные 2024, начиная с первого такого числа, не меньшего чем $1021574$ (минимальное число, соответствующее маске). Для каждого проверяем условие маски и делимость на 2024 (которая гарантирована по построению).

```python
import re

for n in range(2024, 10**10, 2024):
    if re.fullmatch('1[0-9]2157[0-9]*4', str(n)):
        print(n, n // 2024)
```

Сложность: $O\left(\frac{10^{10}}{2024}ight) \approx O(5 	imes 10^6)$ — приемлемо.

Задание №25ПрограммированиеЕГЭ по информатике