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