After simulating the sample cases, the observation to make is that if there's a R and a L next to each other, it creates an infinite back and forth exchange of children. For example if the blocks are RL and there's 2 children on R and 1 child on L, on the next cycle there's 1 child on R and 2 children on L, and the next there's 2 children on R and 1 child on L.
For each RL you find, find the number of R's behind the R and L's ahead of the L in a row. For example, for RLRRRL, for each RL, look at RLRRRL and find 1 R, and then look at RLRRRL and find 3 R's. For each of these R's, they will end up at either the R or the L depending on what second it comes to the R. For example, in RRRL (1 1 1 1), in the first cycle, it goes to (0, 1, 2, 1). The child at the 3rd R went to L and the child at the 2nd R went to the 3rd R. This child that is currently at the 3rd R will go to L, then R, then L over and over, but we only care about the even cycle since 10^100 is even. Because of this, on an even cycle, it will be at L. Then, the child on the 1st R will be on the 3rd R on an even cycle.
Example:
RRRRRRL
On an even cycle, the child at the 6th (final) R will be on the 6th R. The child at the 5th R will be on the L. The child at the 4th R will be on the 6th R. The child at the 3rd R will be on the L. The child at the 2nd R will be on the 6th R and so on. The same thing happens to the children on the L's too if there's a string of L's ahead of the L.
My solution: http://stfly.io/Bqmwg27T8
No comments:
Post a Comment