← 返回题目列表

Codeforces · 202/B

B. 全新的简单问题

中文机器翻译题面 查看原题

一位广为人知的白俄罗斯体育程序员Lesha决定赚点钱买一套大一平方米的公寓。为此,他想在 Torcoder.com 网站上制作并进行超级评分比赛 (SRM)。但有一个问题——严格的 Torcoder 协调员 Ivan 不接受 Lesha 的任何问题,称他们每个人都是冒犯性的词“欺骗”(即重复)。有一天,他们差点因为另一个伊万无法接受的问题而争吵起来。

请您充当公正的法官,确定该问题是否确实是全新的,或者 Ivan 是正确的并且该问题与以前的 SRM 中使用的问题有些相似。

您将获得 Lesha 问题和每个 Torcoder.com 存档问题的描述。每个问题的描述都是一个单词序列。此外,保证Lesha的问题没有重复的单词,而存档问题的描述可能包含任意数量的重复单词。

Lesha的问题和一些存档问题之间的“相似之处”可以发现如下。在 Lesha 问题中的所有单词排列中,我们选择档案问题中出现的一个作为子序列。如果存在多个这样的排列,我们选择反转次数最少的一个。那么问题的“相似度”可以写为 $$p = \frac{n(n-1)}{2} - x + 1$$,其中 n 是 Lesha 问题中的单词数,x 是所选排列中的反转数。请注意,“相似度”p 始终是正整数。

如果 Ivan 的档案中没有一个问题包含 Lesha 问题中的单词排列作为子序列,则该问题被称为全新问题。

帮助男孩们确定所提出的问题是否是新的,或者从档案中指定与 Lesha 的问题最相似的问题,否则。

输入

第一行包含一个整数 n (1 ≤ n ≤ 4) — Lesha 问题中的单词数。第二行包含 n 个空格分隔的单词——问题的简短描述。

第三行包含一个整数 m (1 ≤ m ≤ 10) — Torcoder.com 档案中的问题数量。接下来的 m 行包含问题的描述为“ks1 s2 ... sk”,其中 k (1 ≤ k ≤ 20) 是问题中的单词数,si 是问题描述的单词。

所有问题描述中的所有单词包含的小写英文字母不超过 10 个。

输出

如果 Lesha 的问题是全新的,则打印字符串“Brand new Problem!” (不带引号)。

否则,在第一行打印与 Lesha 问题最相似的存档问题的索引。如果存在多个此类问题,则打印索引最小的一个。在第二行打印一个由字符 [:, 字符 | 组成的字符串。重复 p 次,并包含字符 :],其中 p 是该问题与 Lesha 问题之间的“相似度”。存档问题按照输入中给出的顺序从 1 开始编号。

示例

输入 #1

4
find the next palindrome
1
10 find the previous palindrome or print better luck next time

输出 #1

1
[:||||||:]

输入 #2

3
add two numbers
3
1 add
2 two two
3 numbers numbers numbers

输出 #2

Brand new problem!

输入 #3

4
these papers are formulas
3
6 what are these formulas and papers
5 papers are driving me crazy
4 crazy into the night

输出 #3

1
[:||||:]

输入#4

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

输出#4

3
[:|||:]

注意

让我们提醒您,倒装的数量是排列中遵循的单词对的数量,而不是按照其原始顺序。因此,例如,如果原始问题是“两个数字相加”,则排列“数字相加两个”包含两个反转——词对“数字”和“加”、“数字”和“二”。

序列 b1, b2, ..., bk 是序列 a1, a2, ..., an 的子序列,如果存在这样一组索引 1 ≤ i1 < i2 < ... < ik ≤ n 且 aij = bj (换句话说,如果可以通过删除 a 的一些元素从 a 获得序列 b)。

在第一个测试用例中,第一个问题包含“查找下一个回文”排列作为子序列,其中反转数等于 1(单词“回文”和“下一个”)。

在第二个测试用例中,不存在包含 Lesha 问题中的单词排列作为子序列的问题。