Задача 6520. Источник: Поляков. Задание КИМ 12
(А. Богданов) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
- заменить (v, w)
- нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (37) ИЛИ нашлось (577) ИЛИ нашлось (777)
ЕСЛИ нашлось (37)
ТО заменить (37, 7)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (577)
ТО заменить (577, 73)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (777)
ТО заменить (777, 5)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход приведённой выше программе поступает строка, начинающаяся с цифры «3», а затем содержащая n цифр «7» (n > 3). Определите максимальное значение n < 100, при котором сумма цифр в строке, полученной в результате выполнения программы, – двузначное число, не имеющее общих множителей с n, кроме 1.
Решение
Перебираем значения n, начиная с максимального, формируем строку, обрабатываем ее алгоритмом и проверяем на соответствие условию. В решениях для нахождения общих множителей используются операции со множествами. Эту проверку можно осуществлять и другими способами. Например, через флаговую переменную, добавляя множители одного числа в массив и проверяя множители второго числа на наличие в этом массиве.
Python
for n in range(99, 3, -1):
s = '3' + '7' * n
while '37' in s or '577' in s or '777' in s:
if '37' in s:
s = s.replace('37', '7', 1)
if '577' in s:
s = s.replace('577', '73', 1)
if '777' in s:
s = s.replace('777', '5', 1)
sm = 0
for i in s:
sm += int(i)
if 10 <= sm <= 99:
a1 = set([i for i in range(2, n // 2 + 1) if n % i == 0])
a2 = set([i for i in range(2, sm // 2 + 1) if sm % i == 0])
if len(a1 & a2) == 0:
print(n)
break
PascalABC
var
n, sum, p: Integer;
s: String;
a1, a2: set of Integer;
begin
for n := 99 downto 4 do
begin
s := '3' + '7' * n;
while s.Contains('37') or s.Contains('577') or s.Contains('777') do
begin
if s.Contains('37') then
begin
p := s.IndexOf('37') + 1;
s := s[:p] + '7' + ((p + 2 <= s.Length) ? s[p + 2:] : '');
end;
if s.Contains('577') then
begin
p := s.IndexOf('577') + 1;
s := s[:p] + '73' + ((p + 3 <= s.Length) ? s[p + 3:] : '');
end;
if s.Contains('777') then
begin
p := s.IndexOf('777') + 1;
s := s[:p] + '5' + ((p + 3 <= s.Length) ? s[p + 3:] : '');
end;
end;
sum := 0;
for p := 1 to s.Length do
sum := sum + StrToInt(s[p]);
if (sum >= 10) and (sum <= 99) then
begin
a1 := [];
for p := 2 to n div 2 do
if n mod p = 0 then
a1 += [p];
a2 := [];
for p := 2 to sum div 2 do
if sum mod p = 0 then
a2 += [p];
if a1 * a2 = [] then
begin
Writeln(n);
break;
end;
end;
end;
end.
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
for (int n = 99; n > 3; n--)
{
string s = "3";
for (int i = 0; i < n; i++)
s += "7";
while (s.find("37") != -1 || s.find("577") != -1 || s.find("777") != -1)
{
int p = s.find("37");
if (p != -1)
s = s.substr(0, p) + "7" + s.substr(p + 2, s.length() - p - 2);
p = s.find("577");
if (p != -1)
s = s.substr(0, p) + "73" + s.substr(p + 3, s.length() - p - 3);
p = s.find("777");
if (p != -1)
s = s.substr(0, p) + "5" + s.substr(p + 3, s.length() - p - 3);
}
int sum = 0;
for (int i = 0; i < s.length(); i++)
sum += (int)s[i] - 48;
if (sum >= 10 && sum <= 99)
{
vector<int> a1, a2, a3;
for (int i = 2; i <= n / 2; i++)
if (n % i == 0)
a1.push_back(i);
for (int i = 2; i <= sum / 2; i++)
if (sum % i == 0)
a2.push_back(i);
set_intersection(a1.begin(), a1.end(), a2.begin(), a2.end(), back_inserter(a3));
if (a3.size() == 0)
{
cout << n << endl;
break;
}
}
}
}
Ответ
97