B. Beautiful Now

Codeforces

IDCF10211B

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Anton has a positive integer n, however, it quite looks like a mess, so he wants to make it beautiful after k swaps of digits. Let the decimal representation of n as (x1x2... xm)10 satisfying that 1 ≤ x1 ≤ 9, 0 ≤ xi ≤ 9 (2 ≤ i ≤ m), which means . In each swap, Anton can select two digits xi and xj (1 ≤ i ≤ j ≤ m) and then swap them if the integer after this swap has no leading zero. Could you please tell him the minimum integer and the maximum integer he can obtain after k swaps? The first line contains one integer T, indicating the number of test cases. Each of the following T lines describes a test case and contains two space-separated integers n and k. 1 ≤ T ≤ 100, 1 ≤ n, k ≤ 109. For each test case, print in one line the minimum integer and the maximum integer which are separated by one space. ## Input The first line contains one integer T, indicating the number of test cases.Each of the following T lines describes a test case and contains two space-separated integers n and k.1 ≤ T ≤ 100, 1 ≤ n, k ≤ 109. ## Output For each test case, print in one line the minimum integer and the maximum integer which are separated by one space. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ i \in \{1, \dots, T\} $: - Let $ n_i \in \mathbb{Z}^+ $ be the positive integer, with decimal representation $ d_{i,1}d_{i,2}\dots d_{i,m_i} $, where $ m_i = \lfloor \log_{10} n_i \rfloor + 1 $, $ 1 \leq d_{i,1} \leq 9 $, and $ 0 \leq d_{i,j} \leq 9 $ for $ 2 \leq j \leq m_i $. - Let $ k_i \in \mathbb{Z}^+ $ be the number of allowed digit swaps. **Constraints** 1. $ 1 \leq T \leq 100 $ 2. $ 1 \leq n_i \leq 10^9 $, so $ 1 \leq m_i \leq 10 $ 3. $ 1 \leq k_i \leq 10^9 $ **Objective** For each test case $ i $, compute: - $ \min_i $: the lexicographically smallest integer obtainable from $ d_{i,1}d_{i,2}\dots d_{i,m_i} $ using exactly $ k_i $ swaps of digits, such that no leading zero is introduced. - $ \max_i $: the lexicographically largest integer obtainable under the same constraints. Output $ \min_i $ and $ \max_i $ for each test case.

API Response (JSON)

{
  "problem": {
    "name": "B. Beautiful Now",
    "description": {
      "content": "Anton has a positive integer n, however, it quite looks like a mess, so he wants to make it beautiful after k swaps of digits. Let the decimal representation of n as (x1x2... xm)10 satisfying that 1 ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10211B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Anton has a positive integer n, however, it quite looks like a mess, so he wants to make it beautiful after k swaps of digits.\n\nLet the decimal representation of n as (x1x2... xm)10 satisfying that 1 ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ i \\in \\{1, \\dots, T\\} $:  \n- Let $ n_i \\in \\mathbb{Z}^+ $ be the positive integer, with decimal represent...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments