E. Playing with numbers

Codeforces

IDCF10106E

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Folan and Eltan are brothers. However, as all brothers are, they always fight. One day their mom had to go to work, so she decided to give them a task to keep them busy while she is away. She gave them two numbers S and N. She told Folan that he has to delete exactly N digits from the number S, so that the resulting number is as *small* as possible. Then, she told Eltan that he has to delete exactly N digits from the number S, so that the resulting number is as *big* as possible. Folan and Eltan are ex ACMers. They decided to write a program to solve this problem, so they can go back to fighting again. When their mom heard the evil plan, she decided to make the number S very big, and she may have added leading zeros to it. The boys were really upset because they couldn't find a way to write a program that would solve this problem fast enough before their mom returns, so they asked for your help. Can you help them with this program, so they can go back to fighting again? The first line of the input consists of a single integer t, the number of test cases. Each test case consists of two numbers S and N separated by a single space. where (0 ≤ S < 10100000) and it may contain leading zeros, and (0 ≤ N < |S|). Note that |S| means the length of the number S. For each test case, print two lines. The first line should contain the *smallest* number Folan can get after deleting exactly N digits from S. The second line should contain the *biggest* number Eltan can get after deleting exactly N digits from S. Please note that in case some of the leading zeros were not deleted, you have to print the resulting number with the remaining leading zeros. ## Input The first line of the input consists of a single integer t, the number of test cases. Each test case consists of two numbers S and N separated by a single space. where (0 ≤ S < 10100000) and it may contain leading zeros, and (0 ≤ N < |S|).Note that |S| means the length of the number S. ## Output For each test case, print two lines.The first line should contain the *smallest* number Folan can get after deleting exactly N digits from S.The second line should contain the *biggest* number Eltan can get after deleting exactly N digits from S.Please note that in case some of the leading zeros were not deleted, you have to print the resulting number with the remaining leading zeros. [samples]

**Definitions** Let $ N, M \in \mathbb{Z}_{\geq 0} $. Let $ H = \{h_1, h_2, \dots, h_N\} $ be a set of horrible words over alphabet $ \Sigma = \{a, b, c, d, e, f, g, h, i, j\} $. Let $ K = \{k_1, k_2, \dots, k_M\} $ be a set of kind words over $ \Sigma $. **Constraints** 1. No word in $ K $ may be a contiguous substring of the output string. 2. Every word in $ H $ must be a contiguous substring of the output string. 3. The output string must be over $ \Sigma $. **Objective** Find the lexicographically smallest string $ s \in \Sigma^* $ such that: - $ \forall h \in H, \, h \text{ is a substring of } s $, - $ \forall k \in K, \, k \text{ is not a substring of } s $. If no such $ s $ exists, output `"-"`.

API Response (JSON)

{
  "problem": {
    "name": "E. Playing with numbers",
    "description": {
      "content": "Folan and Eltan are brothers. However, as all brothers are, they always fight. One day their mom had to go to work, so she decided to give them a task to keep them busy while she is away. She gave th",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10106E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Folan and Eltan are brothers. However, as all brothers are, they always fight. One day their mom had to go to work, so she decided to give them a task to keep them busy while she is away.\n\nShe gave th...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, M \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ H = \\{h_1, h_2, \\dots, h_N\\} $ be a set of horrible words over alphabet $ \\Sigma = \\{a, b, c, d, e, f, g, h, i, j\\} $.  \nLet $ K = \\{k_1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments