Зробимо болото великим знову!#12979

Зробимо болото великим знову! (Розбір)

Author:

Petro Tarnavskyi

Solved by:

First to solve:

2Popici1Arici

Suppose we want to equalize the preferred temperature of all the swamp creatures to a target temperature (the initial temperature of some of the creatures).

Let be the number of creatures whose preferred temperature is different from . To change all creatures’ temperatures to , we need at least evenings. This is because, in one evening, we can change the temperature of at most one creature to . Thus, each creature with a different temperature requires its own evening to change.

If there are at least two neighboring creatures with the target temperature , we can use them to propagate further. Specifically, for any neighbor of these two creatures, we can change their temperature to in one evening. Using this, we can iterate clockwise around the circle:

Initially, there might not be two neighbors with the temperature . However, if we can find any group of three consecutive creatures where one creature’s temperature can be changed to , we can create two neighbors with . After that, the propagation process is the same as mentioned above.

If there is no triplet where a creature’s temperature can be changed to , it means we need at least cnt + 1 evenings to change all temperatures to . This extra evening is required to create a group of three consecutive creatures where one creature’s temperature can be changed to . Suppose we have a triplet of consecutive creatures with temperatures x, y, z, where (without loss of generality) y \le x \le z. In this case, we can change to . After this operation, we change to , creating two consecutive creatures with the target temperature , enabling the propagation process to continue as before.

Thus, to solve the problem, we only need to determine if at least one group of three consecutive creatures where one creature’s temperature can be changed to . This determines whether the answer is or cnt + 1.

Runtime: .