Задача 6206. Источник: Поляков. Задание КИМ 25
(Д. Статный) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Найдите все числа, не превышающие 1010, которые соответствуют маске 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