| Codeforces Round 127 (Div. 1) |
|---|
| Закончено |
Широко известный в узких кругах белорусский олимпиадник Леша решил немного подзаработать, чтобы купить себе квартиру площадью на один квадратный метр больше. Для этого он хочет составить и провести Super Rated Match (SRM) на сайте Torcoder.com. Но вот беда — суровый торкодерский координатор Иван не принимает ни одной Лешиной задачи, называя каждую обидным словом «боян». И вот после очередной предложенной задачи дело чуть не дошло до взаимной обиды.
Вам предлагается выступить в роли справедливого судьи и определить, действительно ли задача является настолько инновационно новой, как уверен в этом Леша, или все-таки Иван прав, и похожая задача уже встречалась в прошедших SRM.
Вам даны описания Лешиной задачи и задач из архива сайта Torcoder.com. Описание каждой задачи представляет собой последовательность слов. При этом гарантируется, что слова в Лешиной задаче не повторяются, в то время как описание задачи из архива может содержать произвольное количество повторяющихся слов.
«Похожесть» Лешиной задачи на некоторую задачу из архива определим следующим образом. Среди всех перестановок слов предлагаемой задачи выберем ту, которая встречается в задаче из архива в качестве подпоследовательности. Если таких перестановок несколько, выберем ту, число инверсий в которой минимально. Тогда «похожесть» задачи можно записать в виде 
, где n — количество слов в задаче Леши, а x — количество инверсий в выбранной перестановке. Обратите внимание, что «похожесть» p — положительное число.
Задачу назовем инновационно новой, если среди задач из архива Ивана не найдется ни одной задачи, которая содержит в себе в качестве подпоследовательности некоторую перестановку слов Лешиной задачи.
Рассудите ребят, определив, является ли предлагаемая задача новой, либо указав задачу из архива, которая больше всего напоминает Лешину задачу.
Первая строка содержит число n (1 ≤ n ≤ 15) — количество слов в Лешиной задаче. Во второй строке находятся n слов, разделенных пробелом — краткое описание задачи.
Третья строка содержит число m (1 ≤ m ≤ 10) — количество задач в архиве Torcoder.com. Следующие m строк содержат описания задач в формате «k s1 s2 ... sk», где k (1 ≤ k ≤ 500000) — количество слов в задаче, а si — слово задачи.
Слова из описаний всех задач содержат не более 10 строчных латинских букв. Гарантируется, что суммарная длина слов в описаниях всех задач не превышает 500015.
В случае, если Лешина задача является инновационно новой, выведите строку «Brand new problem!» (без кавычек).
В противном случае в первой строке выведите номер задачи из архива, наиболее похожей на Лешину задачу. Если таких задач несколько, выведите ту, номер которой минимальный. Во второй строке выведите строку из символов [:, символа |, повторенного p раз, и символов :], где p — «похожесть» этой задачи на Лешину. Задачи нумеруются начиная с единицы в том порядке, в котором они заданы во входных данных.
4
find the next palindrome
1
10 find the previous palindrome or print better luck next time
1
[:||||||:]
3
add two numbers
3
1 add
2 two two
3 numbers numbers numbers
Brand new problem!
4
these papers are formulas
3
6 what are these formulas and papers
5 papers are driving me crazy
4 crazy into the night
1
[:||||:]
3
add two decimals
5
4 please two decimals add
5 decimals want to be added
4 two add decimals add
4 add one two three
7 one plus two plus three equals six
3
[:|||:]
Напомним, что количество инверсий — это количество пар слов, которые в перестановке идут не в том порядке, в котором они шли в исходной задаче. Так, например, если исходная задача была «add two numbers», то перестановка «numbers add two» содержит две инверсии — пары слов «numbers» и «add», а также «numbers» и «two».
Последовательность b1, b2, ..., bk называется подпоследовательностью последовательности a1, a2, ..., an, если найдется такой набор индексов 1 ≤ i1 < i2 < ... < ik ≤ n, что aij = bj. Иными словами, последовательность b может быть получена из a путем вычеркивания некоторых элементов.
В первом тесте первая задача содержит в качестве подпоследовательности перестановку «find the palindrome next», в которой количество инверсий равно 1 (слова «palindrome» и «next»).
Во втором тесте ни одна из задач не содержит в себе в качестве подпоследовательности перестановку слов задачи, предлагаемой Лешей.
