English · Original
Chinese · Translation
Formal · Original
Copying large hexadecimal (base 16) strings by hand can be error prone, but that doesn't stop people from doing it. You've discovered a bug in the code that was likely caused by someone making a mistake when copying such a string. You suspect that whoever copied the string did not change any of the digits in the string, nor the length of the string, but may have permuted the digits arbitrarily. For example, if the original string was 0_abc_ they may have changed it to _a_0_cb_ or 0_bca_, but not _abc_ or 0_abb_.
Unfortunately you don't have access to the original string nor the copied string, but you do know the length of the strings and their numerical absolute difference. You will be given this difference as a hexadecimal string _S_, which has been zero-extended to be equal in length to the original and copied strings. Determine the smallest possible numerical value of the original string.
## Input
Input will contain a hexadecimal string _S_ consisting only of digits 0 to 9 and lowercase English letters from _a_ to _f_, with length at most 14. At least one of the characters is non-zero.
## Output
If it is not possible, print "_NO_" (without quotes).
Otherwise, print the lowercase hexadecimal string corresponding to the smallest possible numerical value, including any necessary leading zeros for the length to be correct.
[samples]
## Note
The numerical value of a hexadecimal string is computed by multiplying each digit by successive powers of 16, starting with the rightmost digit, which is multiplied by 160. Hexadecimal digits representing values greater than 9 are represented by letters: _a_ = 10, _b_ = 11, _c_ = 12, _d_ = 13, _e_ = 14, _f_ = 15.
For example, the numerical value of 0_f_1_e_ is 0·163 + 15·162 + 1·161 + 14·160 = 3870, the numerical value of 00_f_1 is 0·163 + 0·162 + 15·161 + 1·160 = 241, and the numerical value of 100_f_ is 1·163 + 0·162 + 0·161 + 15·160 = 4111. Since 3870 + 241 = 4111 and 00_f_1 is a permutation of 100_f_, 00_f_1 is a valid answer to the second test case.
手工复制大型十六进制（基数为16）字符串容易出错，但这并不能阻止人们这样做。你发现了一个很可能由某人在复制此类字符串时出错而导致的程序漏洞。你怀疑复制字符串的人没有更改字符串中的任何数字，也没有改变字符串的长度，但可能对数字进行了任意排列。例如，如果原始字符串是 #cf_span[0abc]，他们可能将其改为 #cf_span[a0cb] 或 #cf_span[0bca]，但不会改为 #cf_span[abc] 或 #cf_span[0abb]。
不幸的是，你无法访问原始字符串或复制后的字符串，但你知道字符串的长度以及它们的数值绝对差值。你将得到这个差值作为十六进制字符串 #cf_span[S]，该字符串已被零填充至与原始字符串和复制字符串长度相等。请确定原始字符串可能的最小数值。
输入将包含一个仅由数字 #cf_span[0] 到 #cf_span[9] 和小写英文字母 #cf_span[a] 到 #cf_span[f] 组成的十六进制字符串 #cf_span[S]，长度最多为 #cf_span[14]。至少有一个字符非零。
如果不可能，请输出 "_NO_"（不含引号）。
否则，请输出对应于可能最小数值的十六进制字符串（小写），包括为保证长度正确所需的前导零。
十六进制字符串的数值通过将每个数字乘以 16 的 successive 幂次来计算，从最右边的数字开始，该数字乘以 #cf_span[160]。表示大于 #cf_span[9] 的值的十六进制数字用字母表示：#cf_span[a = 10, b = 11, c = 12, d = 13, e = 14, f = 15]。
例如，#cf_span[0f1e] 的数值为 #cf_span[0·163 + 15·162 + 1·161 + 14·160 = 3870]，#cf_span[00f1] 的数值为 #cf_span[0·163 + 0·162 + 15·161 + 1·160 = 241]，#cf_span[100f] 的数值为 #cf_span[1·163 + 0·162 + 0·161 + 15·160 = 4111]。由于 #cf_span[3870 + 241 = 4111] 且 #cf_span[00f1] 是 #cf_span[100f] 的一个排列，因此 #cf_span[00f1] 是第二个测试用例的有效答案。
## Input
输入将包含一个仅由数字 #cf_span[0] 到 #cf_span[9] 和小写英文字母 #cf_span[a] 到 #cf_span[f] 组成的十六进制字符串 #cf_span[S]，长度最多为 #cf_span[14]。至少有一个字符非零。
## Output
如果不可能，请输出 "_NO_"（不含引号）。否则，请输出对应于可能最小数值的十六进制字符串（小写），包括为保证长度正确所需的前导零。
[samples]
## Note
十六进制字符串的数值通过将每个数字乘以 16 的 successive 幂次来计算，从最右边的数字开始，该数字乘以 #cf_span[160]。表示大于 #cf_span[9] 的值的十六进制数字用字母表示：#cf_span[a = 10, b = 11, c = 12, d = 13, e = 14, f = 15]。
例如，#cf_span[0f1e] 的数值为 #cf_span[0·163 + 15·162 + 1·161 + 14·160 = 3870]，#cf_span[00f1] 的数值为 #cf_span[0·163 + 0·162 + 15·161 + 1·160 = 241]，#cf_span[100f] 的数值为 #cf_span[1·163 + 0·162 + 0·161 + 15·160 = 4111]。由于 #cf_span[3870 + 241 = 4111] 且 #cf_span[00f1] 是 #cf_span[100f] 的一个排列，因此 #cf_span[00f1] 是第二个测试用例的有效答案。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of the hexadecimal string $ S $.
Let $ D = (d_0, d_1, \dots, d_{n-1}) $ be the digit sequence of $ S $, where $ d_i \in \{0,1,\dots,9,a,b,c,d,e,f\} $, and $ d_0 $ is the leftmost (most significant) digit.
Let $ v(d_i) \in \{0,1,\dots,15\} $ be the numerical value of digit $ d_i $:
$$
v(d_i) =
\begin{cases}
d_i & \text{if } d_i \in \{0,\dots,9\} \\
10 + (d_i - 'a') & \text{if } d_i \in \{a,\dots,f\}
\end{cases}
$$
Let $ w_i = 16^{n-1-i} $ be the weight of position $ i $ (0-indexed from left).
Let $ A = (a_0, \dots, a_{n-1}) $ and $ B = (b_0, \dots, b_{n-1}) $ be two hexadecimal strings of length $ n $, such that:
- $ B $ is a permutation of $ A $,
- $ | \text{val}(A) - \text{val}(B) | = \text{val}(S) $,
- $ \text{val}(X) = \sum_{i=0}^{n-1} v(x_i) \cdot w_i $.
**Constraints**
1. $ 1 \le n \le 14 $
2. $ S \neq \text{“0”}^n $ (at least one non-zero digit)
3. $ A, B \in \{0,\dots,9,a,\dots,f\}^n $
4. $ B $ is a permutation of $ A $
5. $ |\text{val}(A) - \text{val}(B)| = \text{val}(S) $
**Objective**
Find the lexicographically smallest $ A $ (as a hexadecimal string) such that there exists a permutation $ B $ of $ A $ satisfying $ |\text{val}(A) - \text{val}(B)| = \text{val}(S) $.
If no such $ A $ exists, output "_NO_".
API Response (JSON)
{
"problem": {
"name": "F. Hex Dyslexia",
"description": {
"content": "Copying large hexadecimal (base 16) strings by hand can be error prone, but that doesn't stop people from doing it. You've discovered a bug in the code that was likely caused by someone making a mista",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF867F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Copying large hexadecimal (base 16) strings by hand can be error prone, but that doesn't stop people from doing it. You've discovered a bug in the code that was likely caused by someone making a mista...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "手工复制大型十六进制（基数为16）字符串容易出错，但这并不能阻止人们这样做。你发现了一个很可能由某人在复制此类字符串时出错而导致的程序漏洞。你怀疑复制字符串的人没有更改字符串中的任何数字，也没有改变字符串的长度，但可能对数字进行了任意排列。例如，如果原始字符串是 #cf_span[0abc]，他们可能将其改为 #cf_span[a0cb] 或 #cf_span[0bca]，但不会改为 #cf_sp...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the hexadecimal string $ S $. \nLet $ D = (d_0, d_1, \\dots, d_{n-1}) $ be the digit sequence of $ S $, where $ d_i \\in \\{0,1,\\dots,9,a,b,c...",
"is_translate": false,
"language": "Formal"
}
]
}