E. Largest Beautiful Number

Codeforces

IDCF946E

Time1000ms

Memory256MB

Difficulty—

greedyimplementation

English · Original

Chinese · Translation

Formal · Original

_Yes, that's another problem with definition of "beautiful" numbers_. Let's call a positive integer _x_ _beautiful_ if its decimal representation without leading zeroes contains even number of digits, and there exists a permutation of this representation which is palindromic. For example, 4242 is a beautiful number, since it contains 4 digits, and there exists a palindromic permutation 2442. Given a positive integer _s_, find the largest beautiful number which is less than _s_. ## Input The first line contains one integer _t_ (1 ≤ _t_ ≤ 105) — the number of testcases you have to solve. Then _t_ lines follow, each representing one testcase and containing one string which is the decimal representation of number _s_. It is guaranteed that this string has even length, contains no leading zeroes, and there exists at least one beautiful number less than _s_. The sum of lengths of _s_ over all testcases doesn't exceed 2·105. ## Output For each testcase print one line containing the largest beautiful number which is less than _s_ (it is guaranteed that the answer exists). [samples]

_是的，这是另一个关于“美丽”数字定义的问题_。我们称一个正整数 #cf_span[x] 为 _美丽的_，如果它的十进制表示（不含前导零）包含偶数个数字，并且存在一种对该表示的排列，使其成为回文。例如，#cf_span[4242] 是一个美丽的数字，因为它包含 #cf_span[4] 个数字，并且存在一个回文排列 #cf_span[2442]。给定一个正整数 #cf_span[s]，找出小于 #cf_span[s] 的最大的美丽数字。第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 105]) —— 表示你需要解决的测试用例数量。接下来 #cf_span[t] 行，每行代表一个测试用例，包含一个字符串，该字符串是数字 #cf_span[s] 的十进制表示。保证该字符串具有偶数长度，不含前导零，且至少存在一个小于 #cf_span[s] 的美丽数字。所有测试用例中 #cf_span[s] 的长度总和不超过 #cf_span[2·105]。对于每个测试用例，输出一行，包含小于 #cf_span[s] 的最大的美丽数字（保证答案存在）。 ## Input 第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 105]) —— 表示你需要解决的测试用例数量。接下来 #cf_span[t] 行，每行代表一个测试用例，包含一个字符串，该字符串是数字 #cf_span[s] 的十进制表示。保证该字符串具有偶数长度，不含前导零，且至少存在一个小于 #cf_span[s] 的美丽数字。所有测试用例中 #cf_span[s] 的长度总和不超过 #cf_span[2·105]。 ## Output 对于每个测试用例，输出一行，包含小于 #cf_span[s] 的最大的美丽数字（保证答案存在）。 [samples]

**Definitions** Let $ s \in \mathbb{Z}^+ $ be a positive integer with even decimal length and no leading zeros. A number $ x \in \mathbb{Z}^+ $ is *beautiful* if: - Its decimal representation has even length and no leading zeros. - There exists a permutation of its digits that forms a palindrome. **Constraints** 1. $ 1 \le t \le 10^5 $ 2. For each test case, $ s $ is given as a string of even length $ \ell \ge 2 $, with no leading zeros. 3. The sum of all $ \ell $ over test cases $ \le 2 \cdot 10^5 $. 4. There exists at least one beautiful number $ < s $. **Objective** For each test case, find the largest beautiful number $ x < s $.

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "E. Largest Beautiful Number",
    "description": {
      "content": "_Yes, that's another problem with definition of \"beautiful\" numbers_. Let's call a positive integer _x_ _beautiful_ if its decimal representation without leading zeroes contains even number of digits",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF946E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_Yes, that's another problem with definition of \"beautiful\" numbers_.\n\nLet's call a positive integer _x_ _beautiful_ if its decimal representation without leading zeroes contains even number of digits...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "_是的，这是另一个关于“美丽”数字定义的问题_。\n\n我们称一个正整数 #cf_span[x] 为 _美丽的_，如果它的十进制表示（不含前导零）包含偶数个数字，并且存在一种对该表示的排列，使其成为回文。例如，#cf_span[4242] 是一个美丽的数字，因为它包含 #cf_span[4] 个数字，并且存在一个回文排列 #cf_span[2442]。\n\n给定一个正整数 #cf_span[s]，找出小...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\mathbb{Z}^+ $ be a positive integer with even decimal length and no leading zeros.  \nA number $ x \\in \\mathbb{Z}^+ $ is *beautiful* if:  \n- Its decimal representation ha...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments