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".)