B. Game of Credit Cards

Codeforces

IDCF777B

Time2000ms

Memory256MB

Difficulty—

data structuresdpgreedysortings

English · Original

Chinese · Translation

Formal · Original

After the fourth season Sherlock and Moriary have realized the whole foolishness of the battle between them and decided to continue their competitions in peaceful game of Credit Cards. Rules of this game are simple: each player bring his favourite _n_\-digit credit card. Then both players name the digits written on their cards one by one. If two digits are not equal, then the player, whose digit is smaller gets a flick (knock in the forehead usually made with a forefinger) from the other player. For example, if _n_ = 3, Sherlock's card is 123 and Moriarty's card has number 321, first Sherlock names 1 and Moriarty names 3 so Sherlock gets a flick. Then they both digit 2 so no one gets a flick. Finally, Sherlock names 3, while Moriarty names 1 and gets a flick. Of course, Sherlock will play honestly naming digits one by one in the order they are given, while Moriary, as a true villain, plans to cheat. He is going to name his digits in some other order (however, he is not going to change the overall number of occurences of each digit). For example, in case above Moriarty could name 1, 2, 3 and get no flicks at all, or he can name 2, 3 and 1 to give Sherlock two flicks. Your goal is to find out the minimum possible number of flicks Moriarty will get (no one likes flicks) and the maximum possible number of flicks Sherlock can get from Moriarty. Note, that these two goals are different and the optimal result may be obtained by using different strategies. ## Input The first line of the input contains a single integer _n_ (1 ≤ _n_ ≤ 1000) — the number of digits in the cards Sherlock and Moriarty are going to use. The second line contains _n_ digits — Sherlock's credit card number. The third line contains _n_ digits — Moriarty's credit card number. ## Output First print the minimum possible number of flicks Moriarty will get. Then print the maximum possible number of flicks that Sherlock can get from Moriarty. [samples] ## Note First sample is elaborated in the problem statement. In the second sample, there is no way Moriarty can avoid getting two flicks.

在第四季之后，夏洛克和莫里亚蒂意识到他们之间的斗争全然愚蠢，决定继续以和平的信用卡游戏进行竞赛。这个游戏的规则很简单：每位玩家拿出自己最喜欢的 #cf_span[n] 位数字的信用卡。然后两位玩家依次报出自己卡片上的数字。如果两个数字不相等，则数字较小的玩家会从对方那里得到一记弹额头（通常用食指轻敲）。例如，若 #cf_span[n = 3]，夏洛克的卡片是 #cf_span[123]，莫里亚蒂的卡片是 #cf_span[321]，首先夏洛克报出 #cf_span[1]，莫里亚蒂报出 #cf_span[3]，于是夏洛克得到一记弹额头；接着两人都报出 #cf_span[2]，无人得到弹额头；最后夏洛克报出 #cf_span[3]，而莫里亚蒂报出 #cf_span[1]，于是莫里亚蒂得到一记弹额头。当然，夏洛克会诚实按给定顺序依次报出数字，而莫里亚蒂作为真正的反派，计划作弊。他将按某种其他顺序报出数字（但他不会改变每个数字的总出现次数）。例如，在上述例子中，莫里亚蒂可以报出 #cf_span[1]、#cf_span[2]、#cf_span[3]，从而完全不获得弹额头；或者他可以报出 #cf_span[2]、#cf_span[3]、#cf_span[1]，让夏洛克获得两次弹额头。你的目标是找出莫里亚蒂可能获得的最少弹额头数（没人喜欢弹额头），以及夏洛克可能从莫里亚蒂那里获得的最大弹额头数。注意，这两个目标不同，最优结果可能通过不同策略实现。输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1000]）——夏洛克和莫里亚蒂卡片上的数字位数。第二行包含 #cf_span[n] 个数字——夏洛克的信用卡号码。第三行包含 #cf_span[n] 个数字——莫里亚蒂的信用卡号码。首先输出莫里亚蒂可能获得的最少弹额头数，然后输出夏洛克可能从莫里亚蒂那里获得的最大弹额头数。 ## Input 输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1000]）——夏洛克和莫里亚蒂卡片上的数字位数。第二行包含 #cf_span[n] 个数字——夏洛克的信用卡号码。第三行包含 #cf_span[n] 个数字——莫里亚蒂的信用卡号码。 ## Output 首先输出莫里亚蒂可能获得的最少弹额头数，然后输出夏洛克可能从莫里亚蒂那里获得的最大弹额头数。 [samples] ## Note 第一个样例已在题目描述中详细说明。在第二个样例中，莫里亚蒂无论如何都无法避免获得两次弹额头。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of digits. Let $ S = (s_1, s_2, \dots, s_n) $ be the sequence of digits on Sherlock’s card. Let $ M = (m_1, m_2, \dots, m_n) $ be the sequence of digits on Moriarty’s card. Let $ \mathcal{P} $ be the set of all permutations of $ M $. **Constraints** 1. $ 1 \leq n \leq 1000 $ 2. $ s_i, m_i \in \{0, 1, \dots, 9\} $ for all $ i \in \{1, \dots, n\} $ **Objective** 1. **Minimum flicks for Moriarty**: Find $ \min_{\sigma \in \mathcal{P}} \sum_{i=1}^n \mathbb{I}[m_{\sigma(i)} < s_i] $ 2. **Maximum flicks for Sherlock**: Find $ \max_{\sigma \in \mathcal{P}} \sum_{i=1}^n \mathbb{I}[s_i < m_{\sigma(i)}] $ where $ \mathbb{I}[\cdot] $ is the indicator function: $ \mathbb{I}[P] = 1 $ if predicate $ P $ is true, else $ 0 $.

Samples

Input #1

3
123
321

Output #1

0
2

Input #2

2
88
00

Output #2

2
0

API Response (JSON)

{
  "problem": {
    "name": "B. Game of Credit Cards",
    "description": {
      "content": "After the fourth season Sherlock and Moriary have realized the whole foolishness of the battle between them and decided to continue their competitions in peaceful game of Credit Cards. Rules of this ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF777B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "After the fourth season Sherlock and Moriary have realized the whole foolishness of the battle between them and decided to continue their competitions in peaceful game of Credit Cards.\n\nRules of this ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在第四季之后，夏洛克和莫里亚蒂意识到他们之间的斗争全然愚蠢，决定继续以和平的信用卡游戏进行竞赛。\n\n这个游戏的规则很简单：每位玩家拿出自己最喜欢的 #cf_span[n] 位数字的信用卡。然后两位玩家依次报出自己卡片上的数字。如果两个数字不相等，则数字较小的玩家会从对方那里得到一记弹额头（通常用食指轻敲）。例如，若 #cf_span[n = 3]，夏洛克的卡片是 #cf_span[123]，莫里亚...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of digits.  \nLet $ S = (s_1, s_2, \\dots, s_n) $ be the sequence of digits on Sherlock’s card.  \nLet $ M = (m_1, m_2, \\dots, m_n) $ be the seq...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments