The perfect combo (if you turn the cannon, chance and some of The Crew cards right side up). In this combo, you must defeat the army of blue balloons. You will recruit these 8 knights led by Sir Regendruppel de Wraakzuchtige as crew for your holy quest. IJzeren Hein will train them in the closed defense to make them unstoppable. Then, they will use his cannon to defeat the blue balloon army completely. As this might not be entirely legal, you will use your get-out-of-jail-free-card to evade prison. You are playing the card game Building A Perfect Combo, which combines elements from Risk, The Crew, Catan, and Monopoly. This game consists of multiple playing rounds in which you must find the best combination. Before each round, the cards are shuffled and each player is dealt $$$n$$$ cards. Just like in any card game, the players start by orienting the cards right side up before playing the game. Unfortunately, this can be an annoying time-consuming task, as many of those flippin' cards are upside down! To prevent losing unnecessary time on this task, you want to determine the optimal orienting strategy.
If each card orientation was independently uniformly right side up or upside down, then you would look at the cards one by one and flip them if they are upside down. However, often, many cards have the same orientation, due to the way the cards are collected for shuffling between rounds. Thus, after you go through half of your hand, and you had to flip almost every card, it would make more sense to flip the other cards (that you have not yet seen) all at once before moving on.
To model this, assume that there exists some real number $$$p \in [0,1]$$$ chosen uniformly at random, such that each of the $$$n$$$ cards is upside down with probability $$$p$$$, independent of the others. The value of $$$p$$$ is fixed beforehand, but unknown to you. To orient your cards right side up, you look at each card one by one. For each card $$$i$$$, if it is right side up, it takes $$$x$$$ milliseconds to register this and move on to card $$$i + 1$$$. Otherwise, you can either flip card $$$i$$$ and move on, or flip cards $$$i, i + 1, \dots, n$$$ all at once (while keeping their order the same) and move on. Flipping one card takes $$$y$$$ milliseconds, and flipping all your remaining cards takes $$$z$$$ milliseconds.
Determine the expected time to turn all cards the right side up using an optimal strategy.
The input consists of:
- One line with an integer $$$n$$$ ($$$1\leq n \leq {1000}$$$), the number of cards.
- One line with three integers $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \leq x \lt y \lt z \leq {10^9}$$$), the time in milliseconds for each of the three card moves, respectively: moving on from a card that is right side up, flipping the current card, and flipping all your remaining cards.
Output the minimum possible expected time in milliseconds to turn all cards the right side up.
Your answer should have an absolute or relative error of at most $$${10^{-9}}$$$.
10 200 400 2000
3000
2 200 800 1000
1000
10 250 500 1000
3580.952381
In the first sample, the optimal strategy is to never flip all your remaining cards. Then the expected time per card is $$$300$$$ milliseconds, so the total expected time is $$$3$$$ seconds. In the second sample, the optimal strategy is to flip both cards if the first is upside down.
