Yesterday's Div3. E but not really!

Revision en1, by broadway, 2021-05-06 13:01:53

You are playing the game "Blasting The Sheep". The goal of the game is to blast off all sheep in the current level. The level in the game is described by a string of length n, consisting of the characters '.' (empty space) and '*' (sheep).

In one move, you can perform one of the following actions:
- Move any sheep one square to the left or one square to the right, if the corresponding square exists and is empty. This will take A units of time.
- Use the Blasters over a continuous substring consisting only those cells that currently harbor a sheep. This will take B units of time.

The game ends as soon as there no sheep on the level.
For example, if n=6 and the level is described by the string "**.*..", then the following game scenario is possible:

- The sheep at position 4 moves to the right, the state of the level: "**..*."
- The sheep at position 2 moves to the right, the state of the level: "*.*.*."
- The sheep at position 1 moves to the right, the state of the level: ".**.*."
- Use Blasters over the substring s[2:3], the state of the level: "....*."
- Use Blasters over the substring s[5:5], the state of the level: "......"
- the sheep are blasted away into oblivion and the game ends.


For a given level, determine the minimum time in which you can complete the level.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English broadway 2021-05-06 13:01:53 1461 Initial revision (published)