Moo Language

题目描述

Farmer John 希望能更好地与他的奶牛同伴交流，因此他决定学习哞语（moo language）！ 哞语其实与英语很相似，但更为极简。词只有四种类型：名词、及物动词、不及物动词、连词。任意两个相邻的词之间必须用一个空格分隔。 标点也只有两种：句号和逗号。当句号或逗号出现在某个词之后时，它会紧跟在该词后面；如果后面还有下一个词，则标点后再跟一个空格。

一个句子必须符合以下格式之一： 类型 1：名词 + 不及物动词。 类型 2：名词 + 及物动词 + 名词（若干）。具体来说，及物动词后面至少要跟一个名词，并且除第一个跟在及物动词后的名词外，后续每个名词前都必须有一个逗号。

两个句子可以通过在它们之间放置一个连词来连接成一个复合句。生成的复合句不能再与其他句子或其他复合句继续连接。每个句子（或由两个句子连接而成的复合句）必须以句号结尾。

Farmer John 有一个词库，包含 $N$ 个单词、$C$ 个逗号和 $P$ 个句号（$1 \leq P,C\le N \leq 10^3$）。他使用某个单词或标点符号的次数不能超过它在词库中出现的次数。请帮助他输出一段句子序列，使其中包含的单词数量尽可能多。

每个输入文件包含 $T$（$1\le T\le 100$）个相互独立的测试实例。

输入格式

第一行包含 $T$，表示测试实例的数量。每个实例的输入如下： 第一行包含三个整数 $N$、$C$ 和 $P$。 接下来的 $N$ 行每行包含两个字符串。第一个字符串是 FJ 可以使用的单词本身（由至少 1 个、至多 10 个小写字母组成），第二个字符串为以下之一：noun、transitive-verb、intransitive-verb 或 conjunction，表示该单词的类型。词库中同一个单词可能出现多次，但每次出现时它的类型总是相同的。

输出格式

第一行输出最多可能使用的单词数量。 第二行输出任意一种达到最多单词数量的句子序列。任何合法的序列都会被接受。

评测对空白字符很敏感，请确保不要输出任何多余的空格，尤其是每行末尾不要有多余空格。

3
1 1 1
bessie noun
10 5 4
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
24 5 4
but conjunction
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
bob noun
impressed transitive-verb
cow noun
impressed transitive-verb
leaped intransitive-verb
elsie noun
bella noun
buttercup noun
pushed transitive-verb
mooed intransitive-verb
envy noun
john noun
nhoj noun

0

9
nhoj mooed. farmer taught elsie, bessie and john flew.
23
nhoj mooed. nhoj impressed john, farmer, elsie, bessie and cow impressed bob. bella pushed elsie and buttercup flew. envy mooed but john leaped.

提示

对于第一个测试用例，唯一合法的序列是空序列。对于后两个测试用例，可以构造一个句子序列，使用词库中的所有单词，唯独剩下一个单词未使用。 SCORING: Inputs 2-6: $N\le 10$ Inputs 7-11: $N\le 100$ Inputs 12-16: $N\le 1000$ Inputs with remainder 2 when divided by 5: There are no transitive verbs. Inputs with remainder 3 when divided by 5: There are no intransitive verbs. Inputs with remainder 4 when divided by 5: There are no conjunctions. Problem credits: Chongtian Ma

标签: USACO|2023|Bronze

来源

USACO|2023|Bronze