Форум » Выполнение и анализ алгоритмов для исполнителей » Задача 12_262 и ей подобные » Ответить
Задача 12_262 и ей подобные
Тузов: Добрый день, коллеги! Начал решать 262 задачу на Исполнителя Редактор. 262) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. заменить (v, w) нашлось (v) Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Дана программа для Редактора: [pre2] ПОКА нашлось(01) ИЛИ нашлось(02) ИЛИ нашлось(03) заменить(01, 2302) заменить(02, 10) заменить(03, 201) КОНЕЦ ПОКА][/pre2]Известно, что исходная строка начиналась с нуля, а далее содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 60 единиц, 22 двойки и 17 троек. Сколько единиц было в исходной строке? Пока моей интеллектуальной энергии хватило только на анализ связи между входом и выходом. На Python: [pre2] s = '0'+'1'*2+'2'*3+'3'*4 while '01' in s or '02' in s or '03' in s: s = s.replace('01','2302',1) s = s.replace('02','10',1) s = s.replace('03','201',1) print(s)[/pre2] Итого, если s = '0'+'11'+'222'+'3333', то в ответе будет 23123111122312231223122310 Если разбить на группы: 231 231 111 2231 2231 2231 2231 0 Т.е.: каждая единица порождает: 2, 3, 1 каждая двойка порождает: 1 каждая тройка порождает: 2, 2, 3, 1 Ничего красивее перебора не придумал: [pre2] for ed in range(1,60): for dv in range(1,60): for tr in range(1,60): s = '0'+'1'*ed+'2'*dv+'3'*tr while '01' in s or '02' in s or '03' in s: s = s.replace('01','2302',1) s = s.replace('02','10',1) s = s.replace('03','201',1) ed_i = s.count('1') dv_i = s.count('2') tr_i = s.count('3') if ed_i == 60 and dv_i == 22 and tr_i == 17: print('Единиц:', ed) print('Двоек:', dv) print('Троек:', tr)[/pre2] Неужели и следующие задачи (до 270) решать в лоб подбором или есть изящное решение?
Ответов - 3
Поляков: Тузов пишет: каждая единица порождает: 2, 3, 1 каждая двойка порождает: 1 каждая тройка порождает: 2, 2, 3, 1 Вы чуть-чуть не дошли до решения. Пусть было a единиц, b двоек и c троек. Тогда в результирующей строке будет единиц: a + b + c = 60 двоек: a + 2c = 22 троек: a + c = 17 Решая систему из трёх уравнений, получаем c = 5, a = 12, b = 43.
Angel: for x in range (100): for y in range (100): for z in range (100): s='0'+x*'1'+y*'2'+z*'3' while ('01' in s) or ('02' in s) or ('03' in s): s=s.replace ('01','2302',1) s=s.replace ('02','10',1) s=s.replace ('03','201',1) if s.count('1')==40 and s.count('2')==10 and s.count('3')==8: print (x) break
Поляков: Тузов пишет: каждая единица порождает: 2, 3, 1 каждая двойка порождает: 1 каждая тройка порождает: 2, 2, 3, 1 Можно свести к системе трех линейных уравнений с тремя неизвестными. Обозначьте черех x, y, z количество единиц, двоек и троек.
полная версия страницы