Задача 4. Диалог нейросетей
Две нейросети ведут между собой диалог, по очереди записывая слова. Слова добавляются в конец уже существующей строки без дополнительных пробелов. Каждая из программ знает только четыре слова: «push», «pop», «in» и «offtop», то есть в итоге получится строка, составленная только из этих слов, без пробелов. Диалог будет считаться успешным, если выполнены следующие условия:
- Первое и последнее слово этого диалога «push».
- В диалоге встречаются хотя бы по одному разу все четыре слова «push», «pop», «in» и «offtop».
- В диалоге нигде не встречаются следующие подстроки (то есть подряд идущие символы): «hinp», «pinp», «popp», «npopo», «hpopi», «npu».
Например, диалог «pushpopinofftoppush» не будет успешным, так как в нём встречается подстрока «hpopi». Диалог «pushinofftoppush» не будет успешным, потому что в нём не использовано слово «pop». А диалог «pushinofftoppop» не будет успешным, потому что он не заканчивается словом «push».
Требуется найти успешный диалог, содержащий как можно меньше букв. В ответе запишите этот диалог в виде строки, содержащей только буквы (без пробелов, запятых и иных разделителей). Ваш ответ будет принят на проверку, только если он является успешным диалогом. Чем короче будет ваш диалог, тем больше баллов вы получите.
Ответ на Задачу 4.
Заметим, что в условии есть запрет на следование «poppush» — оно содержит «popp» и запрет на следование «inpush» — содержащее «npu». Отсюда следует, что окончание правильного диалога всегда будет иметь вид «offtoppush». Ещё запрещено повторение «poppop».
Остальные запреты касаются следования трёх слов подряд: запрещены «pushinpush», «pushinpop», «popinpop», «popinpush», «offtopinpush», «offtopinpop», «inpopofftop», «pushpopin».
Рассмотрим начало «pushpop». После этого нельзя поставить «in» из-за запрета «hpopi», остаётся добавить «offtop» и получить «pushpopofftop». Далее нужно добавить «in» и выйти на окончание «offtoppush», что даёт правильный диалог «pushpopofftopinofftoppush». Это один из самых коротких диалогов, он содержит минимальное число слов — 6 — и имеет длину 25 символов. Но из-за повторения длинного слова «offtop» — этот ответ не оптимален. Заметим, что «offtop» — единственное повторённое слово этом варианте диалога.
Начало «pushofftop» заведомо не может быть лучше, так как в дальнейшем мы снова должны будем использовать ещё одно вхождение «offtop» в окончании, а двойное вхождение «offtop» в ответ мы уже обсудили.
Теперь рассмотрим оптимальный вариант начала «pushin». Смысла добавлять далее «offtop» нет по причине того, что далее его придётся добавлять ещё раз для выхода, поэтому желательно здесь поставить «pop». Напрямую этого делать нельзя из-за запрета «hinp». Но ничто не запрещает ещё раз повторить короткое слово «in» и избавиться от этого запрета: «pushininpop». Но теперь нельзя сразу добавить завершение «offtoppush» из-за запрета «npopo». Поэтому ещё раз добавим слово «in» и только потом — «offtoppush». Получим самый короткий диалог «pushininpopinofftoppush». Он состоит из семи слов и имеет длину 23 символа.
Вот ещё варианты правильных диалогов из 25 символов: «pushofftoppopinofftoppush» и «pushinofftoppopofftoppush» — они так же состоят из шести слов. Остальные правильные диалоги имеют длину не менее 27 символов.
