Synnerg Lifeform#5704
У науковій лабораторії вчені виявили новий вид крихітних живих форм і назвали їх "сінерги". Наразі відомо небагато про сінерги, але деякі факти такі:
Існує більше одного типу сінергів.
Кожен новонароджений сінерг має однакову тривалість життя.
Два сінерги (певних типів) можуть подовжити свою тривалість життя, об'єднавшись разом, що також перетворить їх у новий цільовий сінерг. Тривалість життя цього нового цільового сінерга дорівнює сумі тривалостей життя обох джерел, помноженій на коефіцієнт підсилення. Тип цього нового цільового сінерга може відрізнятися від його джерел. З багатьох експериментів вчені виявили набір правил для опису об'єднання кожної пари сінергів. Деякі з цих правил можна показати у наступній таблиці.
Коли вчені розташовують два або більше новонароджених сінергів у послідовність, кожен сінерг у цій послідовності намагатиметься об'єднатися з тим, що зліва або справа (і зробити послідовність коротшою). Цей процес об'єднання буде продовжуватися знову і знову (рекурсивно). Може бути багато можливих способів об'єднання вхідної послідовності, що також впливають на тривалість життя кожного об'єднаного сінерга.
Для прикладу кроків об'єднання, будь ласка, дивіться наступну таблицю.
У першому прикладі, на першому кроці є послідовність із новонароджених сінергів "a a b b", де їх тривалості життя відповідно "1 1 1 1". На другому кроці ці сінерги об'єднуються у послідовність з двох сінергів "aa[a a] bb[b b]" (використовуючи правило № та ), де тривалість життя aa дорівнює 2=(1+1) \cdot 1, а тривалість життя bb дорівнює 6=(1+1) \cdot 3. На третьому кроці "aa bb" об'єднуються у "x[aa bb]" (використовуючи правило №), де його тривалість життя дорівнює 16=(6+2) \cdot 2.
У другому прикладі, на першому кроці, початкова послідовність така сама, як у першому прикладі. Але вони альтернативно об'єднуються у "AA[a a] bb[b b]" (використовуючи правило № та замість цього), де їх тривалості життя 34=(1+1) \cdot 17 та 6=(1+1) \cdot 3 відповідно. Ця послідовність також є кінцевою, що означає, що вона не може бути об'єднана далі, але це не повністю об'єднана послідовність. Однак, ця альтернативна кінцева послідовність має довшу тривалість життя порівняно з кінцевою послідовністю в першому прикладі.
Третій і четвертий приклади також показують альтернативні способи об'єднання послідовності "a c a c". Зверніть увагу, що кожне правило не чутливе до порядку його джерел.
Мета
Вчені хотіли б, щоб ви створили програму, яка може знайти всі сінерги з найвищою тривалістю життя, які можуть бути створені шляхом об'єднання заданої послідовності новонароджених сінергів. Рішення не завжди може бути тим, що повністю об'єднане. Також прийнятне часткове або об'єднання підпослідовності.
Вхідні дані є стандартним введенням, яке містить частини даних, розділених порожнім рядком.
Перша частина - це набір правил об'єднання.
Кожен рядок у цій першій частині містить одне з правил об'єднання.
Кожне правило складається з полів, розділених пробілами.
Перші поля - це ціль, джерело і джерело відповідно. Кожне поле - це ім'я сінерга, яке представлене рядком не більше ніж буквено-цифрових символів.
Останнє поле - це коефіцієнт підсилення, який є додатним цілим числом, меншим або рівним .
Друга частина - це набір вхідних послідовностей сінергів.
Кожен рядок у цій другій частині містить одну вхідну послідовність сінергів.
Кожна вхідна послідовність - це послідовність сінергів, розділених пробілами.
Порожній рядок після другої частини є завершенням введення.
Для кожної вхідної послідовності запишіть частини виходу наступним чином:
У першому рядку запишіть загальну кількість сінергів з найвищою тривалістю життя, за якою йде пробіл, а потім максимальна тривалість життя цих сінергів.
У наступних рядках запишіть кожне з рішень в окремому рядку. Кожне рішення містить поля, розділених пробілами. Це сінерг, його початкова і кінцева позиція. Якщо є два або більше рішень, вони повинні бути відсортовані в порядку зростання. Пріоритет порівняння при сортуванні — це -ге поле, -тє поле і -ше поле (або початкова позиція, кінцева позиція і сінерг). Для порівнянь при сортуванні порівняння -го і -го поля базується на числових значеннях, а -ше поле базується на алфавітному/лексикографічному (ASCII) порядку.
Додаткові пояснення
У цьому прикладі є правил і вхідних послідовностей.
Для першого випадку, навіть якщо є завершене об'єднання "x[aa[a a] bb[b b]]" (починаючи з до ), його тривалість життя становить лише 16 (= \{(1+1) \cdot 1 + (1+1) \cdot 3\} \cdot 2) разів від новонародженого, що менше, ніж для "AA[a a]" починаючи з до .
Для другого випадку є рішення. Перше — "AA" починаючи з до . Друге — "x" починаючи з до .
Для третього випадку є лише одне рішення. "x" зараз є єдиним переможцем (з балами).
Для четвертого і п'ятого випадків (частини) результати були об'єднані згідно з останнім правилом. Оскільки кожне правило не чутливе до порядку його джерел, будь-яке правило застосовується, якщо обидва його джерела знайдені. ("c c a 3" дорівнює "c a c 3".)
Приклад 1