{"problem":{"name":"C. Heroes","description":{"content":"The year of 2012 is coming... According to an ancient choradrican legend in this very year, in 2012, Diablo and his brothers Mephisto and Baal will escape from hell, and innumerable hordes of demons ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF80C"},"statements":[{"statement_type":"Markdown","content":"The year of 2012 is coming...\n\nAccording to an ancient choradrican legend in this very year, in 2012, Diablo and his brothers Mephisto and Baal will escape from hell, and innumerable hordes of demons will enslave the human world. But seven brave heroes have already gathered on the top of a mountain Arreat to protect us mere mortals from the effect of this terrible evil.\n\nThe seven great heroes are: amazon _Anka_, barbarian _Chapay_, sorceress _Cleo_, druid _Troll_, necromancer _Dracul_, paladin _Snowy_ and a professional hit girl _Hexadecimal_. Heroes already know how much experience will be given for each of the three megabosses: _a_ for Mephisto, _b_ for Diablo and _c_ for Baal.\n\nHere's the problem: heroes are as much as seven and megabosses are only three! Then our heroes decided to split into three teams, where each team will go to destroy their own megaboss. Each team member will receive a of experience, rounded down, where _x_ will be the amount of experience for the killed megaboss and _y_ — the number of people in the team.\n\nHeroes do not want to hurt each other's feelings, so they want to split into teams so that the difference between the hero who received the maximum number of experience and the hero who received the minimum number of experience were minimal. Since there can be several divisions into teams, then you need to find the one in which the total amount of liking in teams were maximum.\n\nIt is known that some heroes like others. But if hero _p_ likes hero _q_, this does not mean that the hero _q_ likes hero _p_. No hero likes himself.\n\nThe total amount of liking in teams is the amount of ordered pairs (_p_, _q_), such that heroes _p_ and _q_ are in the same group, and hero _p_ likes hero _q_ (but it is not important if hero _q_ likes hero _p_). In case of heroes _p_ and _q_ likes each other and they are in the same group, this pair should be counted twice, as (_p_, _q_) and (_q_, _p_).\n\nA team can consist even of a single hero, but it is important that every megaboss was destroyed. All heroes must be involved in the campaign against evil. None of the heroes can be in more than one team.\n\nIt is guaranteed that every hero is able to destroy any megaboss alone.\n\n## Input\n\nThe first line contains a single non-negative integer _n_ (0 ≤ _n_ ≤ 42) — amount of liking between the heroes. Next _n_ lines describe liking in the form \"_p likes q_\", meaning that the hero _p_ likes the hero _q_ (_p_  ≠  _q_). Every liking is described in the input exactly once, no hero likes himself.\n\nIn the last line are given three integers _a_, _b_ and _c_ (1 ≤ _a_, _b_, _c_ ≤ 2·109), separated by spaces: the experience for Mephisto, the experience for Diablo and experience for Baal.\n\nIn all the pretests, except for examples from the statement, the following condition is satisfied: _a_ = _b_ = _c_.\n\n## Output\n\nPrint two integers — the minimal difference in the experience between two heroes who will receive the maximum and minimum number of experience points, and the maximal total amount of liking in teams (the number of friendships between heroes that end up in one team).\n\n**When calculating the second answer, the team division should satisfy the difference-minimizing contraint. I.e. primary you should minimize the difference in the experience and secondary you should maximize the total amount of liking.**\n\n[samples]\n\n## Note\n\n**A note to first example:** it the first team should be _Dracul_, _Troll_ and _Anka_, in the second one _Hexadecimal_ and _Snowy_, and in the third _Cleo_ и _Chapay_.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"2012年即将来临...\n\n根据古老的Choradrican传说，就在2012年这一年，Diablo和他的兄弟Mephisto与Baal将从地狱逃脱，无数恶魔军团将奴役人类世界。但七位勇敢的英雄已聚集在Arreat山顶，保护我们这些凡人免受这可怕邪恶的影响。\n\n七位伟大英雄分别是：亚马逊战士 _Anka_、野蛮人 _Chapay_、女巫 _Cleo_、德鲁伊 _Troll_、死灵法师 _Dracul_、圣骑士 _Snowy_ 和职业女杀手 _Hexadecimal_。英雄们已经知道击败每个三大首领所获得的经验值：#cf_span[a] 为 Mephisto，#cf_span[b] 为 Diablo，#cf_span[c] 为 Baal。\n\n问题是：英雄有七位，而三大首领只有三位！于是英雄们决定分成三支队伍，每支队伍负责摧毁一个三大首领。每位队员将获得 $\\left\\lfloor \\frac{x}{y} \\right\\rfloor$ 的经验，其中 #cf_span[x] 是被击败的三大首领所给予的经验值，#cf_span[y] 是该队伍的人数。\n\n英雄们不希望伤害彼此的感情，因此他们希望将队伍划分得使获得最多经验的英雄与获得最少经验的英雄之间的差值尽可能小。由于可能存在多种划分方式，你需要找出其中 #cf_span(class=[tex-font-style-underline], body=[队伍中总喜爱值]) 最大的一种。\n\n已知某些英雄喜欢其他英雄。但如果英雄 #cf_span[p] 喜欢英雄 #cf_span[q]，并不意味着英雄 #cf_span[q] 也喜欢英雄 #cf_span[p]。没有任何英雄喜欢自己。\n\n队伍中的总喜爱值是指有序对 #cf_span[(p, q)] 的数量，满足英雄 #cf_span[p] 和 #cf_span[q] 在同一队伍中，且英雄 #cf_span[p] 喜欢英雄 #cf_span[q]（至于英雄 #cf_span[q] 是否喜欢英雄 #cf_span[p] 则无关紧要）。如果英雄 #cf_span[p] 和 #cf_span[q] 互相喜欢且在同一队伍中，这一对应被计算两次，即作为 #cf_span[(p, q)] 和 #cf_span[(q, p)]。\n\n一支队伍甚至可以仅由一名英雄组成，但重要的是每个三大首领都必须被摧毁。所有英雄都必须参与对抗邪恶的行动。没有任何英雄可以属于多于一支队伍。\n\n保证每位英雄单独一人也能击败任何三大首领。\n\n第一行包含一个非负整数 #cf_span[n] (#cf_span[0 ≤ n ≤ 42]) —— 英雄之间的喜爱关系数量。接下来 #cf_span[n] 行以 \"_p likes q_\" 的形式描述喜爱关系，表示英雄 _p_ 喜欢英雄 _q_（_p_ #cf_span[ ≠ ] _q_）。每条喜爱关系在输入中仅出现一次，没有任何英雄喜欢自己。\n\n最后一行给出三个整数 #cf_span[a], #cf_span[b] 和 #cf_span[c] (#cf_span[1 ≤ a, b, c ≤ 2·109])，用空格分隔：分别表示击败 Mephisto、Diablo 和 Baal 所获得的经验值。\n\n在所有预测试用例中（除题目示例外），满足条件：#cf_span[a = b = c]。\n\n请输出两个整数：英雄之间获得的最大经验与最小经验之差的最小值，以及在满足上述最小差值约束的前提下，队伍中总喜爱值的最大值。\n\n*计算第二个答案时，队伍划分必须满足最小化经验差值的约束。即首要目标是最小化经验差值，次要目标是最大化总喜爱值。*\n\n*第一个示例说明：第一支队伍应为 _Dracul_、_Troll_ 和 _Anka_，第二支为 _Hexadecimal_ 和 _Snowy_，第三支为 _Cleo_ 和 _Chapay_。*\n\n## Input\n\n第一行包含一个非负整数 #cf_span[n] (#cf_span[0 ≤ n ≤ 42]) —— 英雄之间的喜爱关系数量。接下来 #cf_span[n] 行以 \"_p likes q_\" 的形式描述喜爱关系，表示英雄 _p_ 喜欢英雄 _q_（_p_ #cf_span[ ≠ ] _q_）。每条喜爱关系在输入中仅出现一次，没有任何英雄喜欢自己。最后一行给出三个整数 #cf_span[a], #cf_span[b] 和 #cf_span[c] (#cf_span[1 ≤ a, b, c ≤ 2·109])，用空格分隔：分别表示击败 Mephisto、Diablo 和 Baal 所获得的经验值。在所有预测试用例中（除题目示例外），满足条件：#cf_span[a = b = c]。\n\n## Output\n\n请输出两个整数：英雄之间获得的最大经验与最小经验之差的最小值，以及在满足上述最小差值约束的前提下，队伍中总喜爱值的最大值。*计算第二个答案时，队伍划分必须满足最小化经验差值的约束。即首要目标是最小化经验差值，次要目标是最大化总喜爱值。*\n\n[samples]\n\n## Note\n\n*第一个示例说明：第一支队伍应为 _Dracul_、_Troll_ 和 _Anka_，第二支为 _Hexadecimal_ 和 _Snowy_，第三支为 _Cleo_ 和 _Chapay_。*","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ H = \\{h_1, h_2, \\dots, h_7\\} $ be the set of seven heroes.  \nLet $ E = (a, b, c) \\in \\mathbb{Z}_{>0}^3 $ be the experience values for the three megabosses (Mephisto, Diablo, Baal).  \nLet $ L \\subseteq H \\times H $ be the set of directed liking relations, with $ |L| = n $, $ 0 \\leq n \\leq 42 $, and $ (p,q) \\in L \\Rightarrow p \\ne q $, and no self-loops.\n\nLet $ \\mathcal{P} $ be the set of all partitions of $ H $ into three non-empty labeled teams $ (T_1, T_2, T_3) $, where each team corresponds to one of the three bosses (order matters).\n\nFor a partition $ P = (T_1, T_2, T_3) \\in \\mathcal{P} $, define:\n\n- The experience per hero in team $ i $: $ x_i = \\left\\lfloor \\frac{e_i}{|T_i|} \\right\\rfloor $, where $ e_i \\in \\{a,b,c\\} $ is assigned to team $ i $ (bijection between teams and bosses).\n- The **experience difference**: $ D(P) = \\max_{i \\in \\{1,2,3\\}} x_i - \\min_{i \\in \\{1,2,3\\}} x_i $\n- The **total liking**: $ L(P) = \\sum_{(p,q) \\in L} \\mathbf{1}_{\\exists i \\in \\{1,2,3\\} : p \\in T_i \\land q \\in T_i} $\n\n**Constraints**  \n1. Each team $ T_i \\neq \\emptyset $, and $ T_1 \\cup T_2 \\cup T_3 = H $, $ T_i \\cap T_j = \\emptyset $ for $ i \\ne j $.  \n2. Each boss experience $ a, b, c $ is assigned to exactly one team (i.e., all permutations of assigning $ (a,b,c) $ to the three teams are allowed).  \n3. All hero assignments are fixed: $ |H| = 7 $, and every hero belongs to exactly one team.\n\n**Objective**  \nFind the partition $ P^* = (T_1^*, T_2^*, T_3^*) $ and assignment of boss experiences $ \\sigma \\in S_3 $ to teams such that:\n\n1. **Primary**: Minimize $ D(P) = \\max_i \\left\\lfloor \\frac{\\sigma(e_i)}{|T_i|} \\right\\rfloor - \\min_i \\left\\lfloor \\frac{\\sigma(e_i)}{|T_i|} \\right\\rfloor $  \n2. **Secondary**: Among all partitions achieving the minimal $ D(P) $, maximize $ L(P) = \\sum_{(p,q) \\in L} \\mathbf{1}_{\\exists i : p,q \\in T_i} $\n\nOutput: $ \\left( \\min D(P), \\max_{P : D(P) = \\min D} L(P) \\right) $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF80C","tags":["brute force","implementation"],"sample_group":[["3\nTroll likes Dracul\nDracul likes Anka\nSnowy likes Hexadecimal\n210 200 180","30 3"],["2\nAnka likes Chapay\nChapay likes Anka\n10000 50 50","1950 2"]],"created_at":"2026-03-03 11:00:39"}}