Unlock The Safe Chef has a safe with N N dials. T...
Создано: 26 марта 2025 г.
Вопрос
Unlock The Safe
Chef has a safe with
N
N dials. The
i
i-th dial initially shows the digit
A
i
A
i
.
To unlock the safe, the digit shown on the
i
i-th dial should be
B
i
B
i
.
In order to achieve this, Chef can choose a dial and perform one of the following two moves on it:
UP move: Increases the number on the chosen dial by
1
- If it is
9
9 then it becomes
1
DOWN move: Decreases the number on the chosen dial by
1
- If it is
1
1 then it becomes
9
In order to not seem too suspicious, Chef thinks he has to use exactly
K
K moves to unlock the safe.
Is it possible for Chef to unlock the safe while performing exactly
K
K moves in the process?
Note that Chef is allowed to reach the target digits even before
K
K moves: however, even if he does, he must still continue making moves till he has made exactly
K
K moves - it is not allowed to stop before that.
See the example cases below for more clarity.
Input Format
The first line of input will contain a single integer
T
T, denoting the number of test cases.
Each test case consists of three lines of input.
The first line contains two space-separated integers
N
N and
K
K — the number of dials and the exact number of moves allowed.
The second line contains
N
N space-separated integers
A
1
,
A
2
,
…
,
A
N
A
1
,A
2
,…,A
N
— the initial digits on the dials.
The third line contains
N
N space-separated integers
B
1
,
B
2
,
…
,
B
N
B
1
,B
2
,…,B
N
— the target digits on the dials.
Output Format
For each test case, print the answer on a new line: YES if Chef can unlock the safe after using exactly
K
K moves, and NO otherwise.
You may print each character of the answer in either uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).
Constraints
1
≤
T
≤
1
0
5
1≤T≤10
5
1
≤
N
≤
2
⋅
1
0
5
1≤N≤2⋅10
5
0
≤
K
≤
1
0
9
0≤K≤10
9
1
≤
A
i
,
B
i
≤
9
1≤A
i
,B
i
≤9
The sum of
N
N over all test cases does not exceed
2
⋅
1
0
5
2⋅10
5
.
Sample 1:
Input
Output
6
3 2
1 2 3
2 1 4
3 7
1 2 1
2 1 9
2 1
5 6
5 6
2 9
5 6
5 6
4 10
4 6 1 7
6 5 8 9
4 12
4 6 1 7
6 5 8 9
No
Yes
No
Yes
No
Yes
Explanation:
Test case
1
1: All three dials are different, but Chef wants to unlock in two moves. This is not possible, since only one dial can be changed in one move - so after two moves at least one dial will be incorrect.
Test case
2
2: One sequence of
K
7
K=7 moves is as follows:
UP on the first dial, now the sequence is
[
2
,
2
,
1
]
[2,2,1].
DOWN on the second dial, now the sequence is
[
2
,
1
,
1
]
[2,1,1].
UP on the third dial two times, now the sequence is
[
2
,
1
,
3
]
[2,1,3].
DOWN on the third dial three times, now the sequence is
[
2
,
1
,
9
]
[2,1,9], and we've used
1
+
1
+
2
+
3
7
1+1+2+3=7 moves as needed.
Test case
3
3: We already have
A
i
B
i
A
i
=B
i
for every
i
i initially. However, we need to perform a move, which will break that equality.
Test case
4
4: We have
A
i
B
i
A
i
=B
i
for every
i
i initially, and need to make
9
9 moves. Simply perform an UP move on the first dial
9
9 times, and it will end up back where it started.
code in java without comments
Ответ
javaimport java.util.*; import java.io.*; class SafeUnlock { static int INF = 2000000000; // feasible[d][r] = true if we can achieve net difference d (mod 9) // using exactly r moves (0 <= r < 9) on one dial. static boolean[][] feasible = new boolean[9][9]; // For faster iteration, store for each d the list of r in [0..8] // such that feasible[d][r] = true. static int[][] feasibleList = new int[9][]; static void precomputeFeasible() { for(int d=0; d<9; d++){ for(int r=0; r<9; r++){ // We want to see if there exists X,Y >= 0 with X+Y=r and (X - Y) mod 9 = d. // But X+Y=r => Y = r - X => X - Y = 2X - r. // We just check X in [0..r] and see if (2X - r) mod 9 == d. boolean can = false; for(int X=0; X<=r; X++){ int diff = 2*X - r; diff = (diff % 9 + 9) % 9; if(diff == d){ can = true; break; } } feasible[d][r] = can; } } for(int d=0; d<9; d++){ ArrayList<Integer> list = new ArrayList<>(); for(int r=0; r<9; r++){ if(feasible[d][r]) list.add(r); } feasibleList[d] = new int[list.size()]; for(int i=0;i<list.size();i++){ feasibleList[d][i] = list.get(i); } } } public static void main(String[] args) throws IOException { precomputeFeasible(); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); while(T-->0){ String[] line1 = br.readLine().split(" "); int N = Integer.parseInt(line1[0]); long K = Long.parseLong(line1[1]); String[] line2 = br.readLine().split(" "); String[] line3 = br.readLine().split(" "); // We do a DP over mod 9 for the minimal sum of r_i that achieves that mod. // dp[c] = minimal sum of remainders achieving residue c. int[] dp = new int[9]; Arrays.fill(dp, INF); dp[0] = 0; for(int i=0; i<N; i++){ int A = Integer.parseInt(line2[i]); int B = Integer.parseInt(line3[i]); // d = (B - A) mod 9 in [0..8] int d = B - A; d = (d % 9 + 9) % 9; int[] arr = feasibleList[d]; int[] newDp = new int[9]; Arrays.fill(newDp, INF); for(int c=0; c<9; c++){ if(dp[c] == INF) continue; int base = dp[c]; for(int r : arr){ int c2 = (c + r) % 9; int candidate = base + r; if(candidate < newDp[c2]){ newDp[c2] = candidate; } } } dp = newDp; } int want = (int)(K % 9); // If dp[ want ] <= K, we can distribute the difference (K - dp[want]) in multiples of 9 // among the dials. That is valid if dp[want] <= K. if(dp[want] <= K) sb.append("Yes\n"); else sb.append("No\n"); } System.out.print(sb.toString()); } }