KingdomAndPassword
SRM 548 · 2012-06-05 · by fushar
SRM 548 · 2012-06-05 · by fushar · Dynamic Programming
Problem Statement
Problem Statement
King Dengklek has a special room protected by a password. The password is a positive integer that does not contain the digit zero. You are given the old password as a long oldPassword. King Dengklek has been using this password for a long time. Now, he wants to create a new password. You are also given a int[] restrictedDigits. The tradition in the kingdom insists that:
Return the new password X. If there are multiple solutions, return the one for which |oldPassword - X| is minimized. If there are still two possible solutions, return the smaller one. If there is no valid new password at all, return -1 instead.
- The digits in the new password are a permutation of the digits in oldPassword.
- For each i, the i-th most significant digit (0-based index) of the new password is not restrictedDigits[i].
Return the new password X. If there are multiple solutions, return the one for which |oldPassword - X| is minimized. If there are still two possible solutions, return the smaller one. If there is no valid new password at all, return -1 instead.
Notes
- |x| denotes the absolute value of x. For example, |3| = |-3| = 3.
- The new password may be equal to the old password (see example 2).
Constraints
- oldPassword will be between 1 and 10^16 - 1, inclusive.
- oldPassword will not contain the digit zero.
- restrictedDigits will contain the same number of elements as the number of digits in oldPassword.
- Each element of restrictedDigits will be between 1 and 9, inclusive.
Examples
0)
548
{5, 1, 8}
Returns: 485
1)
7777
{4, 7, 4, 7}
Returns: -1
The only possible new password is 7777. Since digit 7 is restricted in two positions, this new password cannot be created.
2)
58
{4, 7}
Returns: 58
3)
172
{4, 7, 4}
Returns: 127
Both 127 and 217 are valid passwords. No other valid password is closer to 172 than these two. In this situation, King Dengklek will choose the smaller one.
4)
241529363573463
{1, 4, 5, 7, 3, 9, 8, 1, 7, 6, 3, 2, 6, 4, 5}
Returns: 239676554423331
Submissions are judged against all 85 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class KingdomAndPassword with a public method long long newPassword(long long oldPassword, vector<int> restrictedDigits) · 85 test cases · 2 s / 256 MB per case