A line contains 40 characters: 20 crosses and 20 zeros. In one move, you can swap any two adjacent characters. What is the minimum number of moves required to ensure that 20 consecutive characters are crosses?

#
For 20 crosses to stand in a row, it is necessary and sufficient for all the noughts to stand at the edges (possibly all on one side).

Evaluation. Suppose there is a string with an arbitrary arrangement of crosses and noughts. We will make allowed moves, moving the noughts to the right or left edge so that there are no crosses to the right or left of them.

For this, we will first select the rightmost and leftmost noughts. To move one of them to the edge, no more than 10 moves are required, since either to the left of the leftmost or to the right of the rightmost nought, there are no more than 10 crosses.

Next, we will take the rightmost and leftmost noughts from the remaining 19. Reasoning similarly, we get that the specified movement will again require no more than 10 moves, and so on. Thus, to achieve the required arrangement, no more than \(20 \cdot 10 = 200\) moves will be required.

Let's provide an example of the initial arrangement for the case when a smaller number of moves is insufficient. Suppose there are 10 crosses, followed by 20 noughts, and then another 10 crosses. In this case, moving each nought to the edge will require exactly 10 moves.

## Answer

In 200 moves.

Send a comment