Задача 6417. Источник: Поляков. Задание КИМ 12
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
- заменить (v, w)
- нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА НЕ нашлось (00)
заменить (02, 101)
заменить (11, 2)
заменить (012, 30)
заменить (010, 00)
КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная строка содержала ровно два нуля – на первом и на последнем месте, 50 двоек, больше 100 единиц и не содержала других цифр. После выполнения программы получилась строка, сумма цифр которой оказалась простым числом. Какое наименьшее количество единиц могло быть в исходной строке?
Решение
По всей видимости, разработчики рассчитывали, что два нуля в строке могут быть получены только за счет четвертой замены, которая уменьшает сумму в строке на единицу (первые три замены сумму в строке не меняют). Однако, для некоторых строк два нуля может дать и третья замена. Решением данной задачи является перебор различных вариантов расположения двоек и единиц для различных значений n, пока не получим сумму, являющуюся простым числом.
Python
def simple(n):
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
def algo(s):
while '00' not in s:
s = s.replace('02', '101', 1)
s = s.replace('11', '2', 1)
s = s.replace('012', '30', 1)
s = s.replace('010', '00', 1)
sm = 0
for i in s:
sm += int(i)
return sm
for n in range(101, 300):
variants = ['0' + '2' * 50 + '1' * n + '0',
'0' + '1' * n + '2' * 50 + '0',
'0' + '12' * 50 + '1' * (n - 50) + '0',
'0' + '21' * 50 + '1' * (n - 50) + '0',
'0' + '1' * (n - 50) + '12' * 50 + '0',
'0' + '1' * (n - 50) + '21' * 50 + '0',
'0' + '211' * 50 + '1' * (n - 100) + '0',
'0' + '112' * 50 + '1' * (n - 100) + '0',
'0' + '121' * 50 + '1' * (n - 100) + '0',
'0' + '1' * (n - 100) + '211' * 50 + '0',
'0' + '1' * (n - 100) + '121' * 50 + '0',
'0' + '1' * (n - 100) + '112' * 50 + '0']
for s in variants:
if simple(algo(s)):
print(n)
exit()
PascalABC
function simple(n: Integer): Boolean;
var
i: Integer;
begin
Result := True;
for i := 2 to round(sqrt(n)) do
if n mod i = 0 then
begin
Result := False;
break;
end;
end;
function replace(s, s1, s2: String): String;
var
p: Integer;
begin
result := s;
if s.Contains(s1) then
begin
p := s.IndexOf(s1) + 1;
result := s[:p] + s2 + ((p + s1.Length <= s.Length) ? s[p + s1.Length:] : '');
end
end;
function algo(s: String): Integer;
var
i: Integer;
begin
while not s.Contains('00') do
begin
s := replace(s, '02', '101');
s := replace(s, '11', '2');
s := replace(s, '012', '30');
s := replace(s, '010', '00');
end;
result := 0;
for i := 1 to s.Length do
result := result + StrToInt(s[i]);
end;
var
n: Integer;
variants: Set of String;
s: String;
begin
for n := 101 to 299 do
begin
variants := ['0' + '2' * 50 + '1' * n + '0',
'0' + '1' * n + '2' * 50 + '0',
'0' + '12' * 50 + '1' * (n - 50) + '0',
'0' + '21' * 50 + '1' * (n - 50) + '0',
'0' + '1' * (n - 50) + '12' * 50 + '0',
'0' + '1' * (n - 50) + '21' * 50 + '0',
'0' + '211' * 50 + '1' * (n - 100) + '0',
'0' + '112' * 50 + '1' * (n - 100) + '0',
'0' + '121' * 50 + '1' * (n - 100) + '0',
'0' + '1' * (n - 100) + '211' * 50 + '0',
'0' + '1' * (n - 100) + '121' * 50 + '0',
'0' + '1' * (n - 100) + '112' * 50 + '0'];
foreach s in variants do
if simple(algo(s)) then
begin
Writeln(n);
Exit;
end;
end;
end.
C++
#include <iostream>
#include <string>
using namespace std;
bool simple(int n)
{
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}
string replace(string s, string s1, string s2)
{
int p = s.find(s1);
if (p != -1)
return s.substr(0, p) + s2 + s.substr(p + s1.length(), s.length() - p - s1.length());
return s;
}
string mul(string s, int n)
{
string res = "";
for (int i = 0; i < n; i++)
res += s;
return res;
}
int algo(string s)
{
while (s.find("00") == -1)
{
s = replace(s, "02", "101");
s = replace(s, "11", "2");
s = replace(s, "012", "30");
s = replace(s, "010", "00");
}
int sum = 0;
for (int i = 0; i < s.length(); i++)
sum += (int)s[i] - 48;
return sum;
}
int main()
{
for (int n = 101; n < 300; n++)
{
string variants[12] = { "0" + mul("2", 50) + mul("1", n) + "0",
"0" + mul("1", n) + mul("2", 50) + "0",
"0" + mul("12", 50) + mul("1", n - 50) + "0",
"0" + mul("21", 50) + mul("1", n - 50) + "0",
"0" + mul("1", n - 50) + mul("12", 50) + "0",
"0" + mul("1", n - 50) + mul("21", 50) + "0",
"0" + mul("211", 50) + mul("1", n - 100) + "0",
"0" + mul("112", 50) + mul("1", n - 100) + "0",
"0" + mul("121", 50) + mul("1", n - 100) + "0",
"0" + mul("1", n - 100) + mul("211", 50) + "0",
"0" + mul("1", n - 100) + mul("121", 50) + "0",
"0" + mul("1", n - 100) + mul("112", 50) + "0" };
for (int i = 0; i < 12; i++)
if (simple(algo(variants[i])))
{
cout << n << endl;
return 0;
}
}
}
Ответ
111