310447: CF1835A. k-th equality
Description
Consider all equalities of form $a + b = c$, where $a$ has $A$ digits, $b$ has $B$ digits, and $c$ has $C$ digits. All the numbers are positive integers and are written without leading zeroes. Find the $k$-th lexicographically smallest equality when written as a string like above or determine that it does not exist.
For example, the first three equalities satisfying $A = 1$, $B = 1$, $C = 2$ are
- $1 + 9 = 10$,
- $2 + 8 = 10$,
- $2 + 9 = 11$.
An equality $s$ is lexicographically smaller than an equality $t$ with the same lengths of the numbers if and only if the following holds:
- in the first position where $s$ and $t$ differ, the equality $s$ has a smaller digit than the corresponding digit in $t$.
Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases. The description of test cases follows.
The first line of each test case contains integers $A$, $B$, $C$, $k$ ($1 \leq A, B, C \leq 6$, $1 \leq k \leq 10^{12}$).
Each input file has at most $5$ test cases which do not satisfy $A, B, C \leq 3$.
OutputFor each test case, if there are strictly less than $k$ valid equalities, output $-1$.
Otherwise, output the $k$-th equality as a string of form $a + b = c$.
ExampleInput7 1 1 1 9 2 2 3 1 2 2 1 1 1 5 6 42 1 6 6 10000000 5 5 6 3031568815 6 6 6 1000000000000Output
2 + 1 = 3 10 + 90 = 100 -1 9 + 99996 = 100005 -1 78506 + 28543 = 107049 -1Note
In the first test case, the first $9$ solutions are: $\langle 1, 1, 2 \rangle, \langle 1, 2, 3 \rangle, \langle 1, 3, 4 \rangle, \langle 1, 4, 5 \rangle, \langle 1, 5, 6 \rangle, \langle 1, 6, 7 \rangle, \langle 1, 7, 8 \rangle, \langle 1, 8, 9 \rangle, \langle 2, 1, 3 \rangle$.
Int the third test case, there are no solutions as the smallest possible values for $a$ and $b$ are larger than the maximal possible value of $c$ — $10 + 10 = 20 > 9$.
Please note that whitespaces in the output matter.
Input
题意翻译
我们考虑所有的形式上满足 $a + b = c$ 的等式。其中数字 $a$ 有 $A$ 个位,$b$ 有 $B$ 个位,$c$ 有 $C$ 个位。 (注:所有的数字都是正整数,并且没有前导零。) 现在你的任务是:找到第 $k$ 小字典序的等式,或者断言它不存在。 例如,满足 $A = 1, B = 1, C = 2$ 的前三小字典序的等式为: - $1 + 9 = 10$ - $2 + 8 = 10$ - $2 + 9 = 11$Output
这个题目是关于找出特定形式等式的字典序第k小的等式。给定的等式形式为 \( a + b = c \),其中 \( a \) 有 \( A \) 位数字,\( b \) 有 \( B \) 位数字,\( c \) 有 \( C \) 位数字。所有数字都是正整数,并且书写时没有前导零。需要找出当以字符串形式书写时,字典序第 \( k \) 小的等式,或者确定它不存在。
输入数据格式:
每个测试包含多个测试用例。输入的第一行包含一个整数 \( t \)(\( 1 \leq t \leq 10^3 \)),表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含整数 \( A \),\( B \),\( C \),\( k \)(\( 1 \leq A, B, C \leq 6 \),\( 1 \leq k \leq 10^{12} \))。
每个输入文件最多有5个测试用例,这些测试用例不满足 \( A, B, C \leq 3 \)。
输出数据格式:
对于每个测试用例,如果有少于 \( k \) 个有效的等式,输出 -1。
否则,输出字典序第 \( k \) 小的等式,形式为 \( a + b = c \)。
注意:
输出中的空格是重要的。题目大意: 这个题目是关于找出特定形式等式的字典序第k小的等式。给定的等式形式为 \( a + b = c \),其中 \( a \) 有 \( A \) 位数字,\( b \) 有 \( B \) 位数字,\( c \) 有 \( C \) 位数字。所有数字都是正整数,并且书写时没有前导零。需要找出当以字符串形式书写时,字典序第 \( k \) 小的等式,或者确定它不存在。 输入数据格式: 每个测试包含多个测试用例。输入的第一行包含一个整数 \( t \)(\( 1 \leq t \leq 10^3 \)),表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含整数 \( A \),\( B \),\( C \),\( k \)(\( 1 \leq A, B, C \leq 6 \),\( 1 \leq k \leq 10^{12} \))。 每个输入文件最多有5个测试用例,这些测试用例不满足 \( A, B, C \leq 3 \)。 输出数据格式: 对于每个测试用例,如果有少于 \( k \) 个有效的等式,输出 -1。 否则,输出字典序第 \( k \) 小的等式,形式为 \( a + b = c \)。 注意: 输出中的空格是重要的。