(№ 3844) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
1 2 |
1. заменить (v, w) 2. нашлось (v) |
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
Дана программа для исполнителя Редактор:
1 2 3 4 5 6 7 |
НАЧАЛО ПОКА нашлось(01) ИЛИ нашлось(02) ИЛИ нашлось(03) заменить(01, 30) заменить(02, 3103) заменить(03, 1201) КОНЕЦ ПОКА КОНЕЦ |
Известно, что исходная строка начиналась с нуля, а далее содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 31 единицу, 24 двойки и 46 троек. Сколько троек было в исходной строке?
Решение на Pyton:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# зададим циклы перебора (где а - конечное число цифр "1", b - "2", с - "3") for a in range(46): for b in range(46): for c in range(46): # зададим исходную строку s = '0' + a*'1' + b*'2' + c*'3' # запустим цикл перебора и замены while ('01' in s) or ('02' in s) or ('03' in s): s = s.replace('01','30',1) s = s.replace('02','3103',1) s = s.replace('03','1201',1) # выведем результат, удовлетворяющий условию задачи (с - количество "3" в исходной строке) if s.count('1') == 31 and s.count('2') == 24 and s.count('3') == 46: print(c) |
Решение через систему уравнений:
По условию задачи при замене могут получиться следующие конечные варианты:
01 -> 30
02 -> 3103 -> 311201 -> 311230
03 -> 1201 -> 1230.
Т.е. 01 при замене даст одну "3", 02 - две "1", одну "2" и две "3", а 03 - одну "1", одну "2" и одну "3". Обозначим количество "1" в исходной строке как a, "2" - как b, "3" - как c, и составим систему уравнений:
Ответ: 17 цифр "3"