A. AquaMoon and Two Arrays
Solution:
Just simulate the process.
For each time, find the i,j where a[i]>b[i] and a[j]<b[j]. Just apply the operation for this i, j.
Code:
Java
C++
B. AquaMoon and Stolen String
Solution:
Just simulate the process.
Scan from left to right, for each one, just check which char not present.
Code:
Java
C++
C. AquaMoon and Strange Sort
Solution:
If one of the friends need to move, and if we want the direction not change, then the number of moves of this friend must be even. So, the final direction only depends on the parity of the initial position and the target position.
And obviously if we do not worry about the direction, then there must be a solution. We just need sort it from left to right.
So, we just need count the parity of initial state and the parity after sorting for each number. If the parity is the same, then the answer is YES.
Code:
Java
C++
D. AquaMoon and Chess
Solution:
First, we can note that, for any pair of two consecutive 1, after some operations, it must can be move to any position. For example, 01100100, the consecutive 1 must can be move to the right, so that 00010011.
But we also notice that, even the consecutive 1 can move to the right, but it will affect the single 1's position.
If there is only one pair of consecutive 1, then actually the position of the single 1 only depends on the consecutive 1.
If there are more pairs of consecutive 1, for example two pairs, 01100100110. We can find that: actually, the position of single 1 still depend on the consecutive 1, like 00001011110.
Now this problem is transfer to for these consecutive 1, how many different ways to insert it into original array.
For example, 01100100, we remove the single 1 first, because it does not impact the result, we get 0110000. Of course, the 0 can be inserted, and 11 also can be inserted. So, in this example, there are 6 positions can be inserted and there 1 one pair need to insert to these positions. So, the result is $C_6^1$.
Code:
Java
C++
