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

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

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

Найдите все числа, не превышающие 10¹⁰, которые соответствуют маске 8*80*06 и при этом без остатка делятся на 4546. В ответе запишите каждое 60-е число, считая от 1-го (1-е, 61-е, 121-е и т. д.) в порядке возрастания, справа от каждого запишите частное от его деления на 4546.

Решение

Чтобы сократить объем операций в 4,5 тыс. раз, найдем первое число кратное 4546 после минимального числа, удовлетворяющего шаблону 88006 и организуем цикл с данным шагом. Таким образом, программа не только будет работать быстрее, но и отпадет необходимость проверять кратность. Проверку соответствия числа шаблону можно осуществлять через целочисленные операции или через анализ строки. На Python возможно использование библиотеки fnmatch, но такое решение выдает результат ощутимо медленнее, чем «ручной» анализ.

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

z = 88006
while z % 4546 != 0:
    z += 1
k = 0
for n in range(z, 10 ** 10 + 1, 4546):
    if n % 100 == 6:
        x = n // 100
        flag80 = False
        while x > 9:
            if x % 100 == 80:
                flag80 = True
                x //= 100
                break
            x //= 10
        while x > 9:
            x //= 10
        if flag80 and x == 8:
            if k % 60 == 0:
                print(n, n // 4546)
            k += 1

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

z = 88006
while z % 4546 != 0:
    z += 1
k = 0
for n in range(z, 10 ** 10 + 1, 4546):
    s = str(n)
    if s[0] == "8" and s[-2:] == "06" and "80" in s[1: -2]:
        if k % 60 == 0:
            print(n, n // 4546)
        k += 1

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

from fnmatch import fnmatch
z = 88006
while z % 4546 != 0:
    z += 1
k = 0
for n in range(z, 10 ** 10 + 1, 4546):
    if fnmatch(str(n), '8*80*06'):
        if k % 60 == 0:
            print(n, n // 4546)
        k += 1

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

var
    n, x, k: Int64;
    flag80: Boolean;
begin
    n := 88006;
    while n mod 4546 <> 0 do
        n := n + 1;
    k := 0;
    while n < 10000000001 do
    begin
        if n mod 100 = 6 then
        begin
            x := n div 100;
            flag80 := False;
            while x > 9 do
            begin
                if x mod 100 = 80 then
                begin
                    flag80 := True;
                    x := x div 100;
                    break;
                end;
                x := x div 10;
            end;
            while x > 9 do
                x := x div 10;
            if flag80 and (x = 8) then
            begin
                if k mod 60 = 0 then
                    Writeln(n, ' ', n div 4546);
                k := k + 1;
            end;
        end;
        n := n + 4546;
    end;
end.

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

var
    n, k: Int64;
    s: String;
begin
    n := 88006;
    while n mod 4546 <> 0 do
        n := n + 1;
    k := 0;
    while n < 10000000001 do
    begin
        s := IntToStr(n);
        if (s[1] = '8') and (s[s.Length - 1:] = '06') and s[2:s.Length - 1].Contains('80') then
        begin
            if k mod 60 = 0 then
                Writeln(n, ' ', n div 4546);
            k := k + 1;
        end;
        n := n + 4546;
    end;
end.

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

#include <iostream>
using namespace std;
int main()
{
    int z = 88006;
    while (z % 4546 != 0)
        z++;
    int k = 0;
    for (long long n = z; n < 10000000001; n += 4546)
        if (n % 100 == 6)
        {
            long long x = n / 100;
            bool flag80 = false;
            while (x >= 9)
            {
                if (x % 100 == 80)
                {
                    flag80 = true;
                    x /= 100;
                    break;
                }
                x /= 10;
            }
            while (x > 9)
                x /= 10;
            if (flag80 && x == 8)
            {
                if (k % 60 == 0)
                    cout << n << " " << n / 4546 << endl;
                k++;
            }
        }
}

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

#include <iostream>
#include <string>
using namespace std;
int main()
{
    int z = 88006;
    while (z % 4546 != 0)
        z++;
    int k = 0;
    for (long long n = z; n < 10000000001; n += 4546)
    {
        string s = to_string(n);
        if (s[0] == '8' && s.substr(s.length() - 2, 2) == "06" &&
            s.substr(1, s.length() - 3).find("80") != -1)
        {
            if (k % 60 == 0)
                cout << n << " " << n / 4546 << endl;
            k++;
        }
    }
}

Ответ

81878006 18011
8185804906 1800661
8446518006 1858011
8780876306 1931561
8894980906 1956661