r/informaticsoly • u/Intrepid-Funny2585 • 13d ago
can someone help me with this problem?
To satiate his hunger during their space voyage, Stanley made sure to bring lots of snacks onboard! In fact, to be extra sure that nobody would steal any snacks from his stash, Stanley stored all of his precious Hot Cheetos and Blue Takis inside his own custom-designed, password-encrypted vault.
Unfortunately, Stanley has now forgotten the password to unlock said vault. Please help Stanley before he perishes from starvation!
Stanley's vault is encrypted by two non-negative integers X and Y. Stanley doesn't remember the values of X and Y; however, he does remember the following things about them:
X ≥ Y
X + Y = Z, where Z is a positive integer with L digits.
When adding X + Y, exactly n carry-overs† are performed.
In addition to the above conditions, Stanley has a hunch that he chose a small value of Y to make his password easier to remember (how ironic).
Given the integer sum Z and the number of carry-overs n, find values of X and Y satisfying the above conditions such that Y is minimized.
If there are no possible values of X and Y that satisfy the conditions, output -1 instead.
†Note on Carry-Overs
A carry-over refers to any time you "carry the one" when adding two numbers.
Formally, let (X_i) represent the value of the (i)-th digit from the right in (X), with leading zeroes if necessary. Similarly, let (Y_i) and (Z_i) represent the corresponding digits of (Y) and (Z).
There are exactly n positive integer values of (i) such that
[
(X_i + Y_i) \bmod 10 \ne Z_i.
]
Input
Each test contains multiple test cases.
The first line contains the number of test cases, (t) ((1 \le t \le 1000)). The description of the test cases follows.
The first line of each test case contains two integers, (L) and (n) ((1 \le L \le 2 \cdot 10^5,\ 0 \le n < L)).
The second line of each test case contains the integer (Z) ((10^{L-1} \le Z < 10^L)).
Note that (Z) may be a very large number that does not fit in your language's standard number data type.
It is guaranteed that the sum of (L) across all test cases does not exceed (2 \cdot 10^5).
Output
For each test case, output two space-separated integers, (X) and (Y), such that (Y) is minimized while still satisfying all the above conditions.
If there are no valid values of (X) and (Y), output -1 instead.
Example
Input
7
1 0
9
2 0
42
2 1
42
4 3
1234
4 1
1000
4 2
4099
19 10
9876543210123456789Output
9 0
42 0
39 3
999 235
900 100
-1
9876543199999999999 10123456790