{"problem":{"name":"A. Codehorses T-shirts","description":{"content":"Codehorses has just hosted the second Codehorses Cup. This year, the same as the previous one, organizers are giving T-shirts for the winners. The valid sizes of T-shirts are either _\"M\"_ or from $0$","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1000A"},"statements":[{"statement_type":"Markdown","content":"Codehorses has just hosted the second Codehorses Cup. This year, the same as the previous one, organizers are giving T-shirts for the winners.\n\nThe valid sizes of T-shirts are either _\"M\"_ or from $0$ to $3$ _\"X\"_ followed by _\"S\"_ or _\"L\"_. For example, sizes _\"M\"_, _\"XXS\"_, _\"L\"_, _\"XXXL\"_ are valid and _\"XM\"_, _\"Z\"_, _\"XXXXL\"_ are not.\n\nThere are $n$ winners to the cup for both the previous year and the current year. Ksenia has a list with the T-shirt sizes printed for the last year cup and is yet to send the new list to the printing office.\n\nOrganizers want to distribute the prizes as soon as possible, so now Ksenia is required not to write the whole list from the scratch but just make some changes to the list of the previous year. In one second she can choose arbitrary position in any word and replace its character with some uppercase Latin letter. Ksenia can't remove or add letters in any of the words.\n\nWhat is the minimal number of seconds Ksenia is required to spend to change the last year list to the current one?\n\n_The lists are unordered_. That means, two lists are considered equal if and only if the number of occurrences of any string is the same in both lists.\n\n## Input\n\nThe first line contains one integer $n$ ($1 \\le n \\le 100$) — the number of T-shirts.\n\nThe $i$\\-th of the next $n$ lines contains $a_i$ — the size of the $i$\\-th T-shirt of the list for the previous year.\n\nThe $i$\\-th of the next $n$ lines contains $b_i$ — the size of the $i$\\-th T-shirt of the list for the current year.\n\nIt is guaranteed that all the sizes in the input are valid. It is also guaranteed that Ksenia can produce list $b$ from the list $a$.\n\n## Output\n\nPrint the minimal number of seconds Ksenia is required to spend to change the last year list to the current one. If the lists are already equal, print _0_.\n\n[samples]\n\n## Note\n\nIn the first example Ksenia can replace _\"M\"_ with _\"S\"_ and _\"S\"_ in one of the occurrences of _\"XS\"_ with _\"L\"_.\n\nIn the second example Ksenia should replace _\"L\"_ in _\"XXXL\"_ with _\"S\"_.\n\nIn the third example lists are equal.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Codehorses 刚刚举办了第二届 Codehorses 杯。今年和去年一样，主办方将为获胜者发放 T 恤。\n\n有效的 T 恤尺码为 _\"M\"_，或由 $0$ 到 $3$ 个 _\"X\"_ 后跟 _\"S\"_ 或 _\"L\"_ 组成。例如，尺码 _\"M\"_、_\"XXS\"_、_\"L\"_、_\"XXXL\"_ 是有效的，而 _\"XM\"_、_\"Z\"_、_\"XXXXL\"_ 是无效的。\n\n去年和今年各有 $n$ 名获奖者。Ksenia 拥有去年杯赛 T 恤尺码的列表，但尚未将今年的列表发送给印刷厂。\n\n主办方希望尽快分发奖品，因此 Ksenia 不需要从头重写整个列表，而只需对去年的列表进行一些修改。每秒她可以选择任意单词中的任意位置，并将其字符替换为某个大写拉丁字母。Ksenia 不能在任何单词中删除或添加字母。\n\nKsenia 最少需要花费多少秒才能将去年的列表修改为今年的列表？\n\n_列表是无序的_。这意味着，当且仅当两个列表中每个字符串的出现次数相同时，这两个列表被认为是相等的。\n\n第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 100$) —— T 恤的数量。\n\n接下来的 $n$ 行中，第 $i$ 行包含 $a_i$ —— 去年列表中第 $i$ 件 T 恤的尺码。\n\n接下来的 $n$ 行中，第 $i$ 行包含 $b_i$ —— 今年列表中第 $i$ 件 T 恤的尺码。\n\n保证输入中的所有尺码均有效。同时保证 Ksenia 可以从列表 $a$ 生成列表 $b$。\n\n请输出 Ksenia 为将去年列表修改为今年列表所需花费的最少秒数。如果两个列表已经相等，请输出 _0_。\n\n在第一个例子中，Ksenia 可以将 _\"M\"_ 替换为 _\"S\"_，并将其中一个 _\"XS\"_ 中的 _\"S\"_ 替换为 _\"L\"_。\n\n在第二个例子中，Ksenia 应将 _\"XXXL\"_ 中的 _\"L\"_ 替换为 _\"S\"_。\n\n在第三个例子中，两个列表相等。\n\n## Input\n\n第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 100$) —— T 恤的数量。接下来的 $n$ 行中，第 $i$ 行包含 $a_i$ —— 去年列表中第 $i$ 件 T 恤的尺码。接下来的 $n$ 行中，第 $i$ 行包含 $b_i$ —— 今年列表中第 $i$ 件 T 恤的尺码。保证输入中的所有尺码均有效。同时保证 Ksenia 可以从列表 $a$ 生成列表 $b$。\n\n## Output\n\n请输出 Ksenia 为将去年列表修改为今年列表所需花费的最少秒数。如果两个列表已经相等，请输出 _0_。\n\n[samples]\n\n## Note\n\n在第一个例子中，Ksenia 可以将 _\"M\"_ 替换为 _\"S\"_，并将其中一个 _\"XS\"_ 中的 _\"S\"_ 替换为 _\"L\"_。在第二个例子中，Ksenia 应将 _\"XXXL\"_ 中的 _\"L\"_ 替换为 _\"S\"_。在第三个例子中，两个列表相等。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 100 $, be the number of T-shirts.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ and $ B = (b_1, b_2, \\dots, b_n) $ be multisets (unordered lists) of T-shirt sizes, where each size is a string from the valid set:  \n$$\n\\mathcal{S} = \\{ \\text{\"S\"}, \\text{\"M\"}, \\text{\"L\"}, \\text{\"XS\"}, \\text{\"XL\"}, \\text{\"XXS\"}, \\text{\"XXL\"}, \\text{\"XXXS\"}, \\text{\"XXXL\"} \\}\n$$\n\n**Constraints**  \n1. All elements of $ A $ and $ B $ belong to $ \\mathcal{S} $.  \n2. The multisets $ A $ and $ B $ have the same cardinality $ n $.  \n3. Ksenia may perform character replacements only (no insertions or deletions).  \n4. The goal is to transform multiset $ A $ into multiset $ B $ with minimal total character replacements.\n\n**Objective**  \nCompute the minimal number of character replacements required to transform multiset $ A $ into multiset $ B $, where in one second one character in one string may be replaced by another uppercase Latin letter.  \n\nLet $ f: \\mathcal{S} \\to \\mathbb{Z}_{\\geq 0} $ denote the frequency function of a multiset. Define the multiset difference as:  \n$$\nD(s) = f_B(s) - f_A(s), \\quad \\forall s \\in \\mathcal{S}\n$$  \nLet $ \\mathcal{P} = \\{ s \\in \\mathcal{S} \\mid D(s) > 0 \\} $ (deficit in $ A $), and $ \\mathcal{N} = \\{ s \\in \\mathcal{S} \\mid D(s) < 0 \\} $ (surplus in $ A $).  \n\nFor each pair $ (s, t) \\in \\mathcal{N} \\times \\mathcal{P} $, define $ c(s, t) $ as the minimum number of character replacements required to transform string $ s $ into string $ t $.  \n\nThe problem reduces to finding a minimum-cost bipartite matching between surplus and deficit sizes, where the cost of matching a surplus string $ s \\in \\mathcal{N} $ to a deficit string $ t \\in \\mathcal{P} $ is $ c(s, t) $, and the total flow is $ \\sum_{s \\in \\mathcal{N}} |D(s)| = \\sum_{t \\in \\mathcal{P}} D(t) $.  \n\nLet $ \\mathcal{F} $ be the set of all feasible flow assignments $ x_{s,t} \\in \\mathbb{Z}_{\\geq 0} $, where:  \n- $ \\sum_{t \\in \\mathcal{P}} x_{s,t} = -D(s) $ for all $ s \\in \\mathcal{N} $,  \n- $ \\sum_{s \\in \\mathcal{N}} x_{s,t} = D(t) $ for all $ t \\in \\mathcal{P} $.  \n\nThen the minimal number of seconds is:  \n$$\n\\min_{\\mathcal{F}} \\sum_{s \\in \\mathcal{N}} \\sum_{t \\in \\mathcal{P}} x_{s,t} \\cdot c(s, t)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1000A","tags":["greedy","implementation"],"sample_group":[["3\nXS\nXS\nM\nXL\nS\nXS","2"],["2\nXXXL\nXXL\nXXL\nXXXS","1"],["2\nM\nXS\nXS\nM","0"]],"created_at":"2026-03-03 11:00:39"}}