← 返回题目列表

Codeforces · 77/A

A. 英雄

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

2012年即将到来...

根据这一年的古老的乔拉迪卡传说,2012年,暗黑破坏神和他的兄弟墨菲斯托和巴尔将从地狱中逃脱,无数的恶魔大军将奴役人类世界。但是七位勇敢的英雄已经聚集在亚瑞特山顶上,以保护我们这些凡人免受这种可怕邪恶的影响。

七大英雄分别是:亚马逊安卡、野蛮人查佩、女术士克莱奥、德鲁伊巨魔、死灵法师德拉库尔、圣骑士斯诺伊和职业杀手十六进制。英雄们已经知道三个巨型 Boss 分别会获得多少经验:a 代表墨菲斯托,b 代表暗黑破坏神,c 代表巴尔。

问题来了:英雄多达七个,而超级大佬只有三个!然后我们的英雄决定分成三队,每队将去摧毁自己的超级boss。每个团队成员都会获得 $$\frac{x}{y}$$ 的经验,向下舍入,其中 x 是被杀死的巨型 Boss 的经验量,y 是团队中的人数。

英雄们不想伤害彼此的感情,所以他们希望分成小队,以便获得最大经验值的英雄和获得最小经验值的英雄之间的差异最小。由于团队可以分为多个组,因此您需要找到团队中点赞总数最大的一个团队。

众所周知,有些英雄喜欢其他英雄。但是如果英雄p喜欢英雄q,这并不意味着英雄q喜欢英雄p。没有哪个英雄喜欢自己。

团队中的总喜欢量是有序对 (p, q) 的数量,使得英雄 p 和 q 在同一组中,并且英雄 p 喜欢英雄 q(但英雄 q 是否喜欢英雄 p 并不重要)。如果英雄 p 和 q 彼此喜欢并且他们在同一组中,则该对应该被计算两次,即(p,q)和(q,p)。

一个团队甚至可以由一个英雄组成,但重要的是每个超级 Boss 都被摧毁。所有英雄都必须参与到对抗邪恶的行动中。任何英雄都不能在多个队伍中。

保证每个英雄都能够单独摧毁任何超级boss。

输入

第一行包含一个非负整数 n (0 ≤ n ≤ 42) — 英雄之间的喜欢程度。接下来的n行以“p喜欢q”的形式描述喜欢,这意味着英雄p喜欢英雄q(p≠q)。每个喜好都在输入中被描述一次,没有英雄喜欢自己。

最后一行给出三个整数a、b和c(1≤a、b、c≤2·109),用空格分隔:Mephisto的经验、Diablo的经验和Baal的经验。

在所有预测试中,除了语句中的示例外,都满足以下条件:a = b = c。

输出

打印两个整数 - 将获得最大和最小经验值的两个英雄之间的最小经验差异,以及团队中的最大喜好总数(最终在一个团队中的英雄之间的友谊数量)。

计算第二个答案时,团队划分应满足差异最小化约束。 IE。首先你应该最小化体验的差异,其次你应该最大化喜欢的总量。

示例

输入 #1

3
Troll likes Dracul
Dracul likes Anka
Snowy likes Hexadecimal
210 200 180

输出 #1

30 3

输入 #2

2
Anka likes Chapay
Chapay likes Anka
10000 50 50

输出 #2

1950 2

注意

第一个例子的注释:第一支队伍应该是 Dracul、Troll 和 Anka,第二支队伍应该是 Hexadecimal 和 Snowy,第三支队伍应该是 Cleo и Chapay。