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

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

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

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

Решение

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

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

z = 909798
while z % 50068 != 0:
    z += 1
for n in range(z, 10 ** 10 + 1, 50068):
    if n % 10 == 8:
        x = n
        flag0 = False
        while x >= 100000:
            if x % 10 == 0:
                flag0 = True
            x //= 10
        if x // 1000 % 10 == 0:
            flag0 = True
        if flag0 and x % 1000 == 979 and x // 10000 == 9:
            print(n, n // 50068)

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

z = 909798
while z % 50068 != 0:
    z += 1
for n in range(z, 10 ** 10 + 1, 50068):
    if n % 10 == 8:
        s = str(n)
        if "0" in s and s[0] == "9" and s[2:5] == "979":
            print(n, n // 50068)

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

from fnmatch import fnmatch
z = 909798
while z % 50068 != 0:
    z += 1
for n in range(z, 10 ** 10 + 1, 50068):
    s = str(n)
    if '0' in s and fnmatch(s, '9?979*8'):
        print(n, n // 50068)

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

var
    n, x: Int64;
    flag0: Boolean;
begin
    n := 909798;
    while n mod 50068 <> 0 do
        n := n + 1;
    while n < 10000000001 do
    begin
        if n mod 10 = 8 then
        begin
            x := n;
            flag0 := False;
            while x >= 100000 do
            begin
                if x mod 10 = 0 then
                    flag0 := True;
                x := x div 10;
            end;
            if x div 1000 mod 10 = 0 then
                flag0 := True;
            if flag0 and (x mod 1000 = 979) and (x div 10000 = 9) then
                Writeln(n, ' ', n div 50068);
        end;
        n := n + 50068;
    end;
end.

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

var
    n: Int64;
    s:String;
begin
    n := 909798;
    while n mod 50068 <> 0 do
        n := n + 1;
    while n < 10000000001 do
    begin
        if n mod 10 = 8 then
        begin
            s := IntToStr(n);
            if s.Contains('0') and (s[1] = '9') and (s[3:6] = '979') then
                Writeln(n, ' ', n div 50068);
        end;
        n := n + 50068;
    end;
end.

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

#include <iostream>
#include <string>
using namespace std;
int main()
{
    int z = 909798;
    while (z % 50068 != 0)
        z++;
    for (long long n = z; n < 10000000001; n+= 50068)
        if (n % 10 == 8)
        {
            long long x = n;
            bool flag0 = false;
            while (x >= 100000)
            {
                if (x % 10 == 0)
                    flag0 = true;
                x /= 10;
            }
            if (x / 1000 % 10 == 0)
                flag0 = true;
            if (flag0 && x % 1000 == 979 && x / 10000 == 9)
                cout << n << " " << n / 50068 << endl;
        }
}

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

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

Ответ

9097906348 181711
9297928008 185706