Block Game

题目描述

农夫约翰正在尝试通过给奶牛一组通常供学龄前儿童使用的 $N$ 个拼写板来教它们阅读（$1 \leq N \leq 100$）。每个拼写板的两面各有一个单词和一张图片。例如，一面可能有单词 'cat' 并配有一张猫的图片，另一面可能有单词 'dog' 并配有一张狗的图片。当这些拼写板放在地上时，会显示出 $N$ 个单词。通过翻转其中一些拼写板，可以露出另一组不同的 $N$ 个单词。

为了帮助奶牛拼写，农夫约翰想制作一些木块，每个木块上刻有一个字母表中的字母。他希望为每个字母制作足够多的木块，使得无论拼写板朝上的一面显示的是哪一组 $N$ 个单词，奶牛都能够用这些木块拼出所有这些单词。例如，如果 $N=3$ 且朝上的单词是 'box'、'cat' 和 'car'，那么奶牛至少需要 1 个 'b' 木块、1 个 'o' 木块、1 个 'x' 木块、2 个 'c' 木块、2 个 'a' 木块、1 个 't' 木块以及 1 个 'r' 木块。

请帮助农夫约翰确定：对于字母表中的每个字母，他最少需要准备多少个木块，才能保证不论每块板显示哪一面，奶牛都能拼出可见的全部 $N$ 个单词。

输入格式

第 1 行包含整数 $N$。 接下来的 $N$ 行中，每行包含用空格分隔的 2 个单词，表示同一块拼写板两面的单词。每个单词是一个长度不超过 10 的小写字母字符串。

输出格式

请输出 26 行。第 1 行输出需要的 'a' 木块数量。第 2 行输出需要的 'b' 木块数量，依此类推。

3
fox box
dog cat
car bus

2
2
2
1
0
1
1
0
0
0
0
0
0
0
2
0
0
1
1
1
1
0
0
1
0
0

提示

在这个例子中，有 $N = 3$ 块拼写板，因此朝上的单词集合共有 $2^3 = 8$ 种可能： fox dog car fox dog bus fox cat car fox cat bus box dog car box dog bus box cat car box cat bus 我们需要为字母表中的每个字母准备足够的木块，以便无论出现这 8 种情形中的哪一种，都能拼出全部三个单词。 题目来源致谢：Viktoriia Schwartz

标签: USACO|2016|Bronze

来源

USACO|2016|Bronze