<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

338. Casino
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Consider the following dice game. Player rolls a regular dice (with the numbers 1 through 6 on its sides) several times and calculates total amount of points each time. Player can finish his turn after any roll. Thus, player should make at least one roll. If the sum exceeds 21, player loses. When player finishes, croupier rolls a dice using the same scheme. Player wins, if he or she has more points than croupier. More formally, if player has Sp points and croupier has Sc points, than player wins if and only if (Sp ≤ 21 and (Sc > 21 or Sc < Sp)). The optimal croupier's strategy allows casino to win in more than 2/3 cases. But Andrew found the possibility to raise his chances to win! He will play together with Big Man. Big Man will bet X euros each game, while Andrew will bet 1 euro each game. In case of the win player gets his bet doubled. In case of the loss player gets nothing.

The scheme of the game is like following.

1. Big Man rolls dice several times and stops following the "best" strategy—the strategy that would be optimal if he played with croupier and without Andrew (he is really Big and doesn't care about little Andrew).

2. Than Andrew rolls dice several times. Andrew knows the amount of points Big Man has. Andrew is very smart boy and he realizes that croupier's strategy maximizes profit of the casino. So, Andrew uses optimal strategy using all those facts.

3. Finally, croupier rolls dice several times. As mentioned above, croupier uses optimal strategy.

We call strategy  if it maximizes expected profit. If after the next roll any player or croupier have the same expected profit with the current value, he or she will prefer to roll the dice.

As Andrew calculated if X is big enough, he has almost 50 percents chance to win!

Input
The input contains one integer X (0 ≤ X ≤ 1000).

Output
Print one number—probability of Andrew's win. Your answer must be accurate up to 10-5.

Example(s)
sample input
sample output
0
0.331176

sample input
sample output
1
0.345634

%
sample input
sample output
%5
%
%0.454301
%

<|response|>
## 1. Abridged problem statement

There is a dice game similar to blackjack with limit `21`.

A player rolls a fair six-sided die at least once and may stop after any roll. If their sum exceeds `21`, they lose. After the player stops, the croupier plays by the same rules. The player wins iff:

```text
player_sum <= 21 and (croupier_sum > 21 or croupier_sum < player_sum)
```

Two players play before the croupier:

1. Big Man bets `X` euros and plays the optimal strategy he would use if Andrew did not exist.
2. Andrew bets `1` euro, sees Big Man's final score, and plays optimally.
3. The croupier then plays optimally for the casino, maximizing total expected casino profit from both bets.

If a player/croupier is indifferent between stopping and rolling, they roll.

Given `X`, output Andrew's probability of winning.

---

## 2. Key observations needed to solve the problem

### Observation 1: Work with expected value instead of probability

For Andrew's unit bet:

- if Andrew wins, his net profit is `+1`;
- if Andrew loses, his net profit is `-1`.

If Andrew wins with probability `p`, then his expected value is:

```text
EV = p * 1 + (1 - p) * (-1) = 2p - 1
```

So after computing Andrew's expected value:

```text
p = (EV + 1) / 2
```

---

### Observation 2: Only sums `0..27` matter

The maximum non-bust score is `21`.

If a player has at most `21` and rolls once more, the largest possible new score is:

```text
21 + 6 = 27
```

Therefore all DP arrays only need indices `0..27`. Scores `22..27` are bust states.

---

### Observation 3: Dynamic programming works backwards

Rolling always increases the current sum, so when computing the value for score `s`, all future states `s + 1 ... s + 6` are larger. Therefore we can compute DP values in decreasing order of score.

---

### Observation 4: Big Man ignores Andrew

Big Man uses the optimal strategy for the one-player game against the croupier. His bet size `X` does not affect his strategy because multiplying all profits by `X` does not change which action is better. So first we compute Big Man's strategy independently.

---

### Observation 5: The croupier optimizes casino profit, not Andrew's loss directly

After both Big Man and Andrew have stopped, the croupier maximizes:

```text
X * profit_from_Big_Man + profit_from_Andrew
```

Andrew's expected value must follow the croupier's casino-optimal decision. So while computing the croupier DP, we need to store two values:

```text
g[Sc] = casino's total expected profit
a[Sc] = Andrew's expected profit under the same croupier action
```

The croupier chooses actions by maximizing `g`, while `a` simply follows that choice.

---

## 3. Full solution approach based on the observations

Let `N = 28`, representing sums `0..27`.

Define a helper:

```text
roll_avg(v, s) = average of v[s + 1], ..., v[s + 6]
```

This is the expected value after one die roll from sum `s`.

### Step 1: Compute Big Man's stopping value

Suppose Big Man stops with score `Sb`. We compute the croupier's optimal response in the one-player game. Let `f[Sc]` be Big Man's expected profit when the croupier currently has score `Sc`. If `Sc > 21`, croupier busted, so `f[Sc] = +1`. For `Sc <= 21`, croupier stops (Big Man wins iff `Sc < Sb`) or rolls (`roll_value = roll_avg(f, Sc)`), and the croupier minimizes Big Man's profit, rolling on ties. Since the croupier must roll at least once, `U_b[Sb] = roll_avg(f, 0)`.

### Step 2: Compute Big Man's strategy

`V_bm[Sb] = max(U_b[Sb], roll_avg(V_bm, Sb))` for `Sb <= 21` (rolling on ties), `-1` for bust. Store his action, then simulate his final-score distribution starting from `reach[1..6] = 1/6` and pushing mass through roll states; stop states (and bust states `22..27`) collect `dist_b[Sb]`.

### Step 3: Compute Andrew's stopping value for fixed Big Man score

Fix Big Man's final score `Sb`. For each Andrew stopping score `Sa`, compute the croupier's strategy against both players using `g[Sc]` (casino total EV) and `a[Sc]` (Andrew's EV under the croupier's casino-optimal action). Boundaries at `Sc > 21` use the bust terms. For `Sc <= 21`, the croupier compares `stop_casino` (casino profit from Big Man and Andrew if it stops) against `roll_casino = roll_avg(g, Sc)`, rolling on ties; `a` follows whichever branch `g` selects. The croupier must roll once, so `stop_andrew[Sa] = roll_avg(a, 0)`.

### Step 4: Compute Andrew's optimal strategy for fixed Big Man score

`V_a[Sa] = max(stop_andrew[Sa], roll_avg(V_a, Sa))` for `Sa <= 21` (rolling on ties), `-1` for bust. Andrew must roll at least once: `andrew_ev(Sb) = roll_avg(V_a, 0)`.

### Step 5: Average over Big Man's final score distribution

```text
total_ev = sum(dist_b[Sb] * andrew_ev(Sb))
answer   = (total_ev + 1) / 2
```

The state space is tiny, so the solution is easily fast enough.

---

## 4. C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

double X;

void read() { cin >> X; }

void solve() {
    // Three sequential actors are resolved in reverse and composed. Sums live
    // in 1..27 with >21 meaning bust; EVs are in player-profit units (+1 win,
    // -1 loss). "Must roll at least once" is encoded by averaging over the
    // outcomes of one forced roll from 0. All ties break toward rolling.
    //
    // DP 1 - croupier vs Big Man alone, parametrized by Big Man's stop value
    // Sb in 1..21. Let f_b(Sc) be the player's EV from croupier state Sc; the
    // croupier picks the action that minimizes it. The boundary is
    // f_b(Sc)=+1 for Sc>21 (croupier busts). For Sc<=21 we compare
    // stop_v=-1 if Sc>=Sb else +1 (the croupier wins ties) against
    // roll_v=avg f_b(Sc+1..Sc+6), and set f_b(Sc)=min(stop_v, roll_v).
    // Big Man's EV if he stops at Sb is then U_b(Sb)=avg f_b(1..6), with
    // U_b(Sb)=-1 for Sb>21 (he already lost, no croupier rolls needed).
    //
    // DP 2 - Big Man's own stop/roll plan. Backward over his sum Sb:
    // V_bm(Sb)=max(U_b(Sb), avg V_bm(Sb+1..Sb+6)) for Sb<=21, V_bm=-1 above.
    // The argmax stored as action_bm[Sb]. A forward sweep seeded with
    // reach[1..6]=1/6 then pushes mass through roll-states and collects
    // dist_b on stop-states (1..21) and on bust states (22..27) separately.
    //
    // DP 3 - the real croupier vs both, parametrized by (Sb, Sa). The
    // croupier knows both scores and maximizes total casino EV =
    // X*(casino term from Big Man) + (casino term from Andrew). We carry
    // two scalars per croupier state: g(Sc) for casino EV and a(Sc) for
    // Andrew's own EV under whatever policy maximizes g. The key subtlety
    // is that a does not take a max/min: it just follows the action chosen
    // by g. Boundaries at Sc>21 use the bust terms directly. For Sc in
    // 21..1 we compute stop_casino, stop_andrew, roll_casino, roll_andrew,
    // pick by comparing roll_casino vs stop_casino, and assign both g and a
    // from the winning branch. Forcing one croupier roll gives Andrew's EV
    // if he stops at Sa: stop_a(Sa | Sb)=avg a(1..6).
    //
    // DP 4 - Andrew's own stop/roll plan, parametrized by Sb. Backward over
    // Sa: V_a(Sa)=max(stop_a(Sa | Sb), avg V_a(Sa+1..Sa+6)) for Sa<=21,
    // V_a=-1 above. Andrew's EV facing this Sb is andrew_ev(Sb)=avg V_a(1..6).
    //
    // Mixing those EVs over Big Man's distribution and mapping the EV in
    // [-1, 1] back to a probability gives the answer:
    //
    //   P(Andrew wins) = (sum_Sb dist_b[Sb] * andrew_ev(Sb) + 1) / 2.
    //
    // Complexity is O(21^2 * 27) - a few thousand floating-point ops.

    const int N = 28;

    auto roll_avg = [&](const vector<double>& v, int s) {
        double t = 0.0;
        for(int d = 1; d <= 6; d++) {
            t += v[s + d];
        }
        return t / 6.0;
    };

    vector<double> U_b(N, -1.0);
    for(int Sb = 1; Sb <= 21; Sb++) {
        vector<double> f(N, 0.0);
        for(int Sc = 22; Sc < N; Sc++) {
            f[Sc] = 1.0;
        }
        for(int Sc = 21; Sc >= 1; Sc--) {
            double stop_v = (Sc >= Sb) ? -1.0 : 1.0;
            double roll_v = roll_avg(f, Sc);
            f[Sc] = (roll_v <= stop_v) ? roll_v : stop_v;
        }
        U_b[Sb] = roll_avg(f, 0);
    }

    vector<double> V_bm(N, -1.0);
    vector<int> action_bm(N, 0);
    for(int Sb = N - 1; Sb >= 1; Sb--) {
        if(Sb > 21) {
            continue;
        }
        double stop_v = U_b[Sb];
        double roll_v = roll_avg(V_bm, Sb);
        if(roll_v >= stop_v) {
            V_bm[Sb] = roll_v;
            action_bm[Sb] = 1;
        } else {
            V_bm[Sb] = stop_v;
            action_bm[Sb] = 0;
        }
    }

    vector<double> reach(N, 0.0);
    for(int d = 1; d <= 6; d++) {
        reach[d] = 1.0 / 6.0;
    }
    vector<double> dist_b(N, 0.0);
    for(int Sb = 1; Sb <= 21; Sb++) {
        if(action_bm[Sb] == 1) {
            for(int d = 1; d <= 6; d++) {
                reach[Sb + d] += reach[Sb] / 6.0;
            }
        } else {
            dist_b[Sb] = reach[Sb];
        }
    }
    for(int Sb = 22; Sb < N; Sb++) {
        dist_b[Sb] = reach[Sb];
    }

    auto andrew_ev_given = [&](int Sb) {
        vector<double> stop_andrew(N, -1.0);
        for(int Sa = 1; Sa <= 21; Sa++) {
            vector<double> g(N, 0.0), a(N, 0.0);
            double big_bust = (Sb > 21) ? X : -X;
            double and_bust_casino = (Sa > 21) ? 1.0 : -1.0;
            double and_bust_andrew = (Sa > 21) ? -1.0 : 1.0;
            for(int Sc = 22; Sc < N; Sc++) {
                g[Sc] = big_bust + and_bust_casino;
                a[Sc] = and_bust_andrew;
            }
            for(int Sc = 21; Sc >= 1; Sc--) {
                double stop_big = (Sb > 21) ? X : ((Sc >= Sb) ? X : -X);
                double stop_and_c = (Sa > 21) ? 1.0 : ((Sc >= Sa) ? 1.0 : -1.0);
                double stop_and_a =
                    (Sa > 21) ? -1.0 : ((Sc >= Sa) ? -1.0 : 1.0);
                double stop_casino = stop_big + stop_and_c;
                double roll_casino = roll_avg(g, Sc);
                double roll_andrew = roll_avg(a, Sc);
                if(roll_casino >= stop_casino) {
                    g[Sc] = roll_casino;
                    a[Sc] = roll_andrew;
                } else {
                    g[Sc] = stop_casino;
                    a[Sc] = stop_and_a;
                }
            }
            stop_andrew[Sa] = roll_avg(a, 0);
        }

        vector<double> V_a(N, -1.0);
        for(int Sa = N - 1; Sa >= 1; Sa--) {
            if(Sa > 21) {
                continue;
            }
            double stop_v = stop_andrew[Sa];
            double roll_v = roll_avg(V_a, Sa);
            V_a[Sa] = (roll_v >= stop_v) ? roll_v : stop_v;
        }
        return roll_avg(V_a, 0);
    };

    double total_ev = 0.0;
    for(int Sb = 1; Sb < N; Sb++) {
        if(dist_b[Sb] == 0.0) {
            continue;
        }
        total_ev += dist_b[Sb] * andrew_ev_given(Sb);
    }

    double prob = (total_ev + 1.0) / 2.0;
    cout << fixed << setprecision(6) << prob << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


def main():
    X = float(sys.stdin.readline())

    # Scores 0..27 are enough.
    # Scores greater than 21 are bust states.
    N = 28

    def roll_avg(values, s):
        """
        Expected value after rolling one fair six-sided die
        from current score s.
        """
        return sum(values[s + d] for d in range(1, 7)) / 6.0

    # ------------------------------------------------------------
    # Step 1: Big Man's stopping values in the one-player game.
    # ------------------------------------------------------------

    # U_b[Sb] = Big Man's EV if he stops at score Sb.
    U_b = [-1.0] * N

    for Sb in range(1, 22):
        # f[Sc] = Big Man's EV when croupier currently has score Sc.
        f = [0.0] * N

        # If croupier busts, Big Man wins.
        for Sc in range(22, N):
            f[Sc] = 1.0

        # Croupier decisions, computed backwards.
        for Sc in range(21, 0, -1):
            # If croupier stops, Big Man wins only if Sc < Sb.
            stop_value = 1.0 if Sc < Sb else -1.0

            # If croupier rolls.
            roll_value = roll_avg(f, Sc)

            # Croupier minimizes Big Man's EV.
            # If equal, croupier rolls.
            f[Sc] = roll_value if roll_value <= stop_value else stop_value

        # Croupier must roll at least once.
        U_b[Sb] = roll_avg(f, 0)

    # ------------------------------------------------------------
    # Step 2: Big Man's optimal strategy.
    # ------------------------------------------------------------

    # V_bm[Sb] = Big Man's optimal EV at current score Sb.
    V_bm = [-1.0] * N

    # action_bm[Sb] = 1 means roll, 0 means stop.
    action_bm = [0] * N

    for Sb in range(N - 1, 0, -1):
        if Sb > 21:
            # Bust state.
            continue

        stop_value = U_b[Sb]
        roll_value = roll_avg(V_bm, Sb)

        # Big Man maximizes EV.
        # If equal, he rolls.
        if roll_value >= stop_value:
            V_bm[Sb] = roll_value
            action_bm[Sb] = 1
        else:
            V_bm[Sb] = stop_value
            action_bm[Sb] = 0

    # ------------------------------------------------------------
    # Step 3: Big Man's final score distribution.
    # ------------------------------------------------------------

    # reach[Sb] = probability Big Man reaches score Sb.
    reach = [0.0] * N

    # Big Man must roll once initially.
    for d in range(1, 7):
        reach[d] = 1.0 / 6.0

    # dist_b[Sb] = probability Big Man finishes with score Sb.
    dist_b = [0.0] * N

    for Sb in range(1, 22):
        if action_bm[Sb] == 1:
            # Big Man rolls.
            for d in range(1, 7):
                reach[Sb + d] += reach[Sb] / 6.0
        else:
            # Big Man stops.
            dist_b[Sb] = reach[Sb]

    # Bust states are final states.
    for Sb in range(22, N):
        dist_b[Sb] = reach[Sb]

    # ------------------------------------------------------------
    # Step 4: Andrew's optimal EV for a fixed Big Man score.
    # ------------------------------------------------------------

    def andrew_ev_given(Sb):
        """
        Compute Andrew's optimal expected profit,
        assuming Big Man's final score is Sb.
        """

        # stop_andrew[Sa] = Andrew's EV if he stops at score Sa.
        stop_andrew = [-1.0] * N

        for Sa in range(1, 22):
            # g[Sc] = casino's total EV.
            # a[Sc] = Andrew's EV under the same croupier decision.
            g = [0.0] * N
            a = [0.0] * N

            # Boundary: croupier has busted.
            for Sc in range(22, N):
                if Sb > 21:
                    # Big Man already busted, casino wins his bet.
                    casino_big = X
                else:
                    # Croupier busts, Big Man wins.
                    casino_big = -X

                # Since Sa is 1..21 here, croupier bust means Andrew wins.
                casino_andrew = -1.0
                andrew_ev = 1.0

                g[Sc] = casino_big + casino_andrew
                a[Sc] = andrew_ev

            # Croupier chooses stop/roll to maximize casino EV.
            for Sc in range(21, 0, -1):
                # Casino profit from Big Man if croupier stops.
                if Sb > 21:
                    stop_big = X
                else:
                    stop_big = X if Sc >= Sb else -X

                # Casino profit from Andrew if croupier stops.
                stop_andrew_casino = 1.0 if Sc >= Sa else -1.0

                # Andrew's own EV if croupier stops.
                stop_andrew_ev = -1.0 if Sc >= Sa else 1.0

                stop_casino = stop_big + stop_andrew_casino

                # Values if croupier rolls.
                roll_casino = roll_avg(g, Sc)
                roll_andrew_ev = roll_avg(a, Sc)

                # Croupier maximizes casino EV.
                # If equal, croupier rolls.
                if roll_casino >= stop_casino:
                    g[Sc] = roll_casino
                    a[Sc] = roll_andrew_ev
                else:
                    g[Sc] = stop_casino
                    a[Sc] = stop_andrew_ev

            # Croupier must roll at least once.
            stop_andrew[Sa] = roll_avg(a, 0)

        # Andrew's own rolling/stopping DP.
        V_a = [-1.0] * N

        for Sa in range(N - 1, 0, -1):
            if Sa > 21:
                # Bust state.
                continue

            stop_value = stop_andrew[Sa]
            roll_value = roll_avg(V_a, Sa)

            # Andrew maximizes EV.
            # If equal, he rolls.
            V_a[Sa] = roll_value if roll_value >= stop_value else stop_value

        # Andrew must roll at least once.
        return roll_avg(V_a, 0)

    # ------------------------------------------------------------
    # Step 5: Average over Big Man's final score distribution.
    # ------------------------------------------------------------

    total_ev = 0.0

    for Sb in range(1, N):
        if dist_b[Sb] > 0.0:
            total_ev += dist_b[Sb] * andrew_ev_given(Sb)

    # Convert expected value to probability.
    probability = (total_ev + 1.0) / 2.0

    print(f"{probability:.6f}")


if __name__ == "__main__":
    main()
```
