A simple inverse-mapping problem.
It is similar to binary case, and one should just compute the module based on 3 instead of 2.
We first sort the array and then check the largest value a[n - 1]. If it is 1, then we just change it into 2; otherwise, we change it into 1 and sort the modified array again.
136D - Прямоугольник и квадрат
Consider all the possible division of the given 8 points, which should be 8!, and check whether we can find a feasible pattern that meets the requirements. Now, the main issue is how to determine that four points form a rectangular or square. At first, we find two neighboring sides and check whether they form a 90 degree, which can be achieved by computing their inner product. Then, we find the two pairs of oppisite sides, and check that whether the two sides belonging to each pair are the same or not. Furthermore, if all of them are the same, it is a square.
We denote the player who plays first as v and the other one as u.
After some observation, one can find that v will always try to remove 1 from left to right while u tries to remove 0 from left to right. At first, we consider the case that the given zero-one sequence does not contain any '?' and has an even length in order to illustrate the essence behind the solution.
If the number of 0s is larger than 1s, then it is obvious that the final result is 00; on the other hand, if we have more 1s than 0s, then the final result should be 11.
If the numbers of 0s and 1s are exactly the same, then we might have 01 or 10 as the final result. One can check that if the last bit is 1 then it must be 01 since no one can take away the last 1. Similarly, the final result is 10 if the last bit is 0.
Now, we generalize the above idea. At first, we consider the case where the length is odd. In fact this can be simply converted to the even case, as long as we add an extra 0 and exchange their moving order. Secondly, we consider the sequence containing '?'. This is in fact quite similar to that containing no '?'. We check whether we can have more 0s, or more 1s, or equal 0s and 1s, by converting '?' into 0s or 1s properly.
Comments (0)
