Задача 6284. Источник: Поляков. Задание КИМ 25

Страница задачи 6284

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

Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 2?5432*1, делящиеся на 1017 без остатка и содержащие хотя бы одну цифру 9. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа – результат его деления на 1017.

Решение

Наиболее оптимальным является нахождение первого числа кратного 1017 и организация цикла с данным шагом. Это уменьшает объем операций более чем в 1000 раз. Анализировать соответствие числа шаблону можно через целочисленные операции или через анализ строки. На Python возможно использование библиотеки fnmatch, но такое решение работает во много раз медленнее.

Python анализ целочисленными операциями

z = 2054321
while z % 1017 != 0:
    z += 1
for n in range(z, 10 ** 10 + 1, 1017):
    if n % 10 == 1:
        x = n
        flag9 = False
        while x >= 1000000:
            if x % 10 == 9:
                flag9 = True
            x //= 10
        if x // 10000 % 10 == 9:
            flag9 = True
        if flag9 and x % 10000 == 5432 and x // 100000 == 2:
            print(n, n // 1017)

Python анализ через строки

z = 2054321
while z % 1017 != 0:
    z += 1
for n in range(z, 10 ** 10 + 1, 1017):
    if n % 10 == 1:
        s = str(n)
        if "9" in s and s[0] == "2" and s[2:6] == "5432":
            print(n, n // 1017)

Python анализ с использованием библиотеки fnmatch

from fnmatch import fnmatch
z = 2054321
while z % 1017 != 0:
    z += 1
for n in range(z, 10 ** 10 + 1, 1017):
    s = str(n)
    if '9' in s and fnmatch(s, '2?5432*1'):
        print(n, n // 1017)

PascalABC анализ целочисленными операциями

var
    n, x: Int64;
    flag9: Boolean;
begin
    n := 2054321;
    while n mod 1017 <> 0 do
        n := n + 1;
    while n < 10000000001 do
    begin
        if n mod 10 = 1 then
        begin
            x := n;
            flag9 := False;
            while x >= 1000000 do
            begin
                if x mod 10 = 9 then
                    flag9 := True;
                x := x div 10;
            end;
            if x div 10000 mod 10 = 9 then
                flag9 := True;
            if flag9 and (x mod 10000 = 5432) and (x div 100000 = 2) then
                Writeln(n, ' ', n div 1017);
        end;
        n := n + 1017;
    end;
end.

PascalABC анализ через строки

var
    n: Int64;
    s:String;
begin
    n := 2054321;
    while n mod 1017 <> 0 do
        n := n + 1;
    while n < 10000000001 do
    begin
        if n mod 10 = 1 then
        begin
            s := IntToStr(n);
            if s.Contains('9') and (s[1] = '2') and (s[3:7] = '5432') then
                Writeln(n, ' ', n div 1017);
        end;
        n := n + 1017;
    end;
end.

C++ анализ целочисленными операциями

#include <iostream>
using namespace std;
int main()
{
    int z = 2054321;
    while (z % 1017 != 0)
        z++;
    for (long long n = z; n < 10000000001; n+=1017)
        if (n % 10 == 1)
        {
            long long x = n;
            bool flag9 = false;
            while (x >= 1000000)
            {
                if (x % 10 == 9)
                    flag9 = true;
                x /= 10;
            }
            if (x / 10000 % 10 == 9)
                flag9 = true;
            if (flag9 && x % 10000 == 5432 && x / 100000 == 2)
                cout << n << " " << n / 1017 << endl;
        }
}

C++ анализ через строки

#include <iostream>
#include <string>
using namespace std;
int main()
{
    int z = 2054321;
    while (z % 1017 != 0)
        z++;
    for (long long n = z; n < 10000000001; n+=1017)
        if (n % 10 == 1)
        {
            string s = to_string(n);
            if (s.find('9') != -1 && s[0] == '2' && s.substr(2, 4) == "5432")
                cout << n << " " << n / 1017 << endl;
        }
}

Ответ

2254325931 2216643
2454329151 2413303
2554320591 2511623
2954327031 2904943