B - Black and white stones
Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits:
(details)
Shagga and Dolf like to play a game with stones, each of which is either black or white. At the beginning of the game, Dolf arranges all the stones in a single line from left to right. Then, Shagga’s goal is to reorder the stones so that all the black stones are to the left of all the white stones. To do this, he can choose any pair of stones of different color and swap their positions, paying $A$ coins to Dolf in the process. However, if the two stones whose positions he is swapping are adjacent, Dolf must give him a refund of $B$ coins, meaning that the operation will effectively cost Shagga only $A - B$ coins.
Shagga is not very bright, so he hasn’t realized yet that he will only loose coins while playing this game. However, he is aware of his limitations, so he knows that if he played optimally he would loose fewer coins than he is loosing right now, with his strategy of randomly choosing the stones he swaps in each movement. Therefore, he wants to know the minimum number of coins he will have to pay Dolf in order to get to the desired arrangement of stones, and is threatening to feed you to the goats if you don’t help him.