<|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.

464. Optimal bribing
Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



It is not easy to live and do business in Russia. For example, to get approval for gas utilities installation according to Russian law you need to get project documentation from city project bureau. But to get project documentation you will be required to get approval for gas utilities installation. Even to people who don't write computer programs and don't know buzz words like "endless recursion" it is clear that to get access to gas one needs to make a wonder. For example, to give bribe or kickback.

Suppose two businessmen compete for some business project which brings them profit V. But only one businessman will be able to win the project — namely, the one who will get N approvals from bureaucrats faster than another. Every businessman gets approvals in certain order — he cannot file next document for approval while previous document is not approved. To speed the process of getting approval up, businessmen may bribe bureaucrats. A businessman may visit (and bribe) only one bureaucrat a day. Specifically, if in particular day businessman i gives to a bureaucrat bribe of b units (non-negative real number which businessman defines itself, and b may vary from day to day), probability that the bureaucrat will give him the approval at that day is 1-0.99(1-Fi)b, where Fi is businessman-specific fascination parameter (so, you see that without a bribe there is only 1 percent chance to get an approval at a particular day). If bribing was unsuccessful, businessman may try again and again (and this doesn't change behavior of bureaucrat in any way), but he loses time (remember, businessman can give only one bribe a day) and money (since even in the case of unsuccessful bribe bureaucrat takes it). If a businessman gets an approval, he can file next document for approval on the next day (and at the same day bribe and get the document approved in the case of luck). Thus, even very lucky and fascinating businessman cannot have more than one document approved in one day. The first businessman who gets N approvals wins the project and makes profit V, another gets nothing (but loss from bribing). If businessmen get all necessary approvals at the same day, we consider that the winner is determined by coin tossing (that is, each of them has the same chance to win). Every businessman knows how many approvals the other one has at any moment.

Suppose that every businessman acts optimally to maximize expected difference between profit and costs (which is the total sum of bribes paid), knowing the strategy of another player. What is the probability to win the project for each of them?

Input
Input file contains numbers N, F1, F2, V from the problem statement. N and V are integers, F1 and F2 are given with not more than two digits after decimal point (1 ≤ N ≤ 10, 0 < F1, F2 < 1, 1 ≤ V ≤ 100). Numbers will be chosen so that businessmen will have unique equilibrium combination of optimal bribing strategies (so, required probabilities will be unique as well).

Output
Write to the output file required probabilities with accuracy not less than 10-6.

Example(s)
sample input
sample output
1 0.14 0.10 20
0.618627007 0.381372993

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

Two businessmen race to obtain `N` approvals. In each state, player 1 has `a` approvals and player 2 has `b` approvals.

Each day, each businessman chooses a non-negative bribe amount. For businessman `i`, bribe `x` gives daily approval probability

\[
p = 1 - 0.99(1-F_i)^x
\]

The bribe is paid whether approval succeeds or fails.

Each businessman can obtain at most one approval per day. The first to reach `N` approvals wins profit `V`. If both reach `N` on the same day, each wins with probability `1/2`.

Both players choose bribes optimally to maximize:

\[
\text{expected profit} - \text{expected total bribes}
\]

Given `N, F1, F2, V`, output the winning probabilities of both businessmen.

Constraints:

```text
1 ≤ N ≤ 10
0 < F1, F2 < 1
1 ≤ V ≤ 100
```

The test data guarantees a unique equilibrium.

---

## 2. Key observations needed to solve the problem

### Observation 1: Use game states `(a, b)`

Let:

```text
(a, b)
```

mean player 1 already has `a` approvals and player 2 already has `b` approvals.

Only states with

```text
0 ≤ a, b < N
```

are live states. If either coordinate reaches `N`, the game ends.

From `(a, b)`, in one day, the possible next states are:

| Event | Probability | Next state |
|---|---:|---|
| both succeed | `p1 * p2` | `(a + 1, b + 1)` |
| only player 1 succeeds | `p1 * (1 - p2)` | `(a + 1, b)` |
| only player 2 succeeds | `(1 - p1) * p2` | `(a, b + 1)` |
| both fail | `(1 - p1) * (1 - p2)` | `(a, b)` |

The last case is a self-loop.

---

### Observation 2: Choose success probability instead of bribe

The bribe formula is:

\[
p = 1 - 0.99(1-F)^x
\]

Solving for `x`:

\[
x = \frac{\ln((1-p)/0.99)}{\ln(1-F)}
\]

So instead of choosing a bribe `x`, we can choose the resulting probability `p`.

Because `x ≥ 0`, the possible probability range is:

\[
p \in [0.01, 1)
\]

The lower bound `0.01` corresponds to zero bribe.

---

### Observation 3: Self-loop can be removed algebraically

Suppose we are in state `(a, b)` and players choose probabilities `p1`, `p2`.

Let `A`, `B`, `C` be player 1's future payoff after:

- `A`: both succeed,
- `B`: only player 1 succeeds,
- `C`: only player 2 succeeds.

Let `cost1` be player 1's bribe for probability `p1`.

Then player 1's expected payoff `X` satisfies:

\[
X =
-cost_1
+ p_1p_2A
+ p_1(1-p_2)B
+ (1-p_1)p_2C
+ (1-p_1)(1-p_2)X
\]

Move the self-loop term to the left:

\[
X \left(1 - (1-p_1)(1-p_2)\right)
=
-cost_1
+ p_1p_2A
+ p_1(1-p_2)B
+ (1-p_1)p_2C
\]

Define:

\[
leave = p_1 + p_2 - p_1p_2
\]

Then:

\[
X =
\frac{
-cost_1
+ p_1p_2A
+ p_1(1-p_2)B
+ (1-p_1)p_2C
}{
leave
}
\]

The same formula applies to player 2.

---

### Observation 4: Dynamic programming works backwards

Every non-self-loop transition increases at least one of `a` or `b`.

Therefore, if we process states in decreasing order of `a` and `b`, the needed future states are already computed.

For every live state `(a, b)`, store:

```text
val1[a][b] = equilibrium expected net payoff of player 1
val2[a][b] = equilibrium expected net payoff of player 2
win1[a][b] = probability that player 1 eventually wins
```

Answer:

```text
win1[0][0], 1 - win1[0][0]
```

---

### Observation 5: Each state is a small continuous two-player game

At one fixed state, future DP values are already known.

So we need to find a Nash equilibrium in two continuous variables:

```text
p1 ∈ [0.01, 1)
p2 ∈ [0.01, 1)
```

For fixed `p2`, player 1's payoff as a function of `p1` is single-peaked (the bribe cost is convex, the reward linear), so we can find player 1's best response by ternary search.

Similarly for player 2.

Let:

\[
BR_1(p_2)
\]

be player 1's best response to `p2`, and

\[
BR_2(p_1)
\]

be player 2's best response to `p1`.

At equilibrium:

\[
p_1 = BR_1(p_2)
\]

\[
p_2 = BR_2(p_1)
\]

Substitute the second equation into the first:

\[
p_1 = BR_1(BR_2(p_1))
\]

So we solve one scalar fixed-point equation:

\[
BR_1(BR_2(p_1)) - p_1 = 0
\]

The statement guarantees uniqueness, so bisection is sufficient.

---

## 3. Full solution approach based on the observations

For each state `(a, b)`:

1. Get future values for the three successful transitions:
   - `(a + 1, b + 1)`
   - `(a + 1, b)`
   - `(a, b + 1)`

2. If a future state is terminal:
   - if player 1 reaches `N` first, player 1 gets `V`, player 2 gets `0`;
   - if player 2 reaches `N` first, player 1 gets `0`, player 2 gets `V`;
   - if both reach `N`, both get expected profit `V / 2`.

3. Define payoff functions `payoff_1(p_1, p_2)` and `payoff_2(p_1, p_2)` using the self-loop-free formula.

4. Define best responses:
   - `BR1(p2)` by ternary search on `p1`;
   - `BR2(p1)` by ternary search on `p2`.

5. Find equilibrium:
   - solve `BR1(BR2(p1)) - p1 = 0` by bisection;
   - set `p2 = BR2(p1)`.

6. Store:
   - `val1[a][b] = payoff1(p1, p2)`
   - `val2[a][b] = payoff2(p1, p2)`

7. Compute `win1[a][b]` using the same probabilities and the same self-loop removal:

\[
win1[a][b] =
\frac{
p_1p_2W_A
+ p_1(1-p_2)W_B
+ (1-p_1)p_2W_C
}{
p_1+p_2-p_1p_2
}
\]

where `WA`, `WB`, `WC` are player 1's winning probabilities in the three future states.

The complexity is effectively constant for each state because the numerical searches use fixed iteration counts. There are at most `N^2 ≤ 100` states, so the solution is easily fast enough.

---

## 4. C++ implementation with detailed comments

```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;
};

int n;
double f1, f2, profit;

void read() { cin >> n >> f1 >> f2 >> profit; }

void solve() {
    // The race is a stochastic game over states (k1, k2), the number of
    // approvals each businessman already holds (0 <= ki < N while the game is
    // live; reaching N is absorbing). On a given day each player i privately
    // picks a bribe bi >= 0, succeeds with probability pi = 1 - 0.99*(1-Fi)^bi
    // (so bi = 0 still yields the base 1% chance and a larger Fi saturates
    // faster), and pays bi whether or not the bribe works. The day's four
    // outcomes move the state to (k1+1,k2+1), (k1+1,k2), (k1,k2+1) or back to
    // (k1,k2) when both fail; a player who reaches N first takes the whole
    // profit V, a same-day double finish is split by a coin toss.
    //
    // Solve the states by backward induction on remaining approvals: every
    // transition either advances a coordinate or stalls in place, so once the
    // three strictly-more-advanced neighbours are known the only self-reference
    // left is the "both fail" loop. Let V1/V2 be the equilibrium net payoff
    // (expected profit minus own future bribes) of the live state and let A, B,
    // C be player 1's payoff at the resulting states (k1+1,k2+1), (k1+1,k2),
    // (k1,k2+1), reading off V, 0 or V/2 at any neighbour that is already
    // terminal. Geometric summation over the repeated stalls gives, with
    // leave = p1 + p2 - p1*p2,
    //
    //     V1 = (-b1 + p1*p2*A + p1*(1-p2)*B + (1-p1)*p2*C) / leave,
    //
    // and the same form for V2 with player 2's A2, B2, C2.
    //
    // Writing the bribe in terms of the success probability it buys,
    // bi = ln((1-pi)/0.99)/ln(1-Fi) for pi in [0.01, 1), turns a state's
    // strategy into a point (p1, p2) and makes V1, V2 explicit functions of it.
    // Let BR1(q) be player 1's best reply when player 2 plays q, that is the p1
    // maximising V1(p1, q), and BR2(q) the p2 maximising V2(q, p2). Each value
    // is single-peaked in that player's own probability (the bribe cost is
    // convex, the reward linear), so BR1 and BR2 are located by ternary search
    // on the maximiser itself, not by rooting the first-order condition, which
    // carries extra solutions that are not the true optimum. The state's
    // equilibrium is the (unique) pair that are mutual best replies, p1 =
    // BR1(p2) and p2 = BR2(p1); substituting the second into the first
    // collapses it to the scalar fixed point p1 = BR1(BR2(p1)), solved by
    // bisection. Iterating the best replies directly is avoided because it can
    // land on a profile that is not individually rational.
    //
    // There is no linear-programming shortcut for this per-state game, which is
    // why the two structural facts above are needed. A simplex solves a
    // zero-sum matrix game, but this game is general-sum (V1 + V2 = V minus the
    // total bribes paid, which varies with play) and its payoffs are
    // transcendental in the action (the bribe enters as a log), so neither the
    // best replies nor the equilibrium are linear. What makes it tractable
    // anyway is shape: single-peakedness reduces each best reply to one concave
    // maximisation a search can solve, and because a best reply always lands in
    // [0.01, 1) the map BR1(BR2(.)) satisfies gap(0.01) >= 0 >= gap(1), so its
    // unique root is bracketed by the endpoints and a plain bisection reaches
    // it.
    //
    // The same backward sweep, replaying the equilibrium (p1, p2), propagates
    // the win probability W1 (terminal value 1, 0 or 1/2):
    //
    //     W1 = (p1*p2*Wa + p1*(1-p2)*Wb + (1-p1)*p2*Wc) / leave,
    //
    // and the answer is W1 at (0,0) against 1 - W1, since some player finishes
    // with probability 1.

    vector<vector<double>> val1(n + 1, vector<double>(n + 1));
    vector<vector<double>> val2(n + 1, vector<double>(n + 1));
    vector<vector<double>> win1(n + 1, vector<double>(n + 1));

    double l1 = log(1 - f1), l2 = log(1 - f2);
    const double lo = 0.01, hi = 1 - 1e-12;

    auto resolve = [&](const vector<vector<double>>& board, int x, int y,
                       double won, double lost, double tie) {
        if(x == n && y == n) {
            return tie;
        }
        if(x == n) {
            return won;
        }
        if(y == n) {
            return lost;
        }

        return board[x][y];
    };

    auto bribe = [](double p, double l) { return log((1 - p) / 0.99) / l; };

    auto expected = [](double p1, double p2, double both, double only1,
                       double only2) {
        return p1 * p2 * both + p1 * (1 - p2) * only1 + (1 - p1) * p2 * only2;
    };

    auto argmax = [&](auto value) {
        double x = lo, y = hi;
        for(int it = 0; it < 80; it++) {
            double m1 = x + (y - x) / 3, m2 = y - (y - x) / 3;
            if(value(m1) < value(m2)) {
                x = m1;
            } else {
                y = m2;
            }
        }

        return (x + y) / 2;
    };

    for(int a = n - 1; a >= 0; a--) {
        for(int b = n - 1; b >= 0; b--) {
            double a1 = resolve(val1, a + 1, b + 1, profit, 0.0, profit / 2);
            double b1 = resolve(val1, a + 1, b, profit, 0.0, profit / 2);
            double c1 = resolve(val1, a, b + 1, profit, 0.0, profit / 2);
            double a2 = resolve(val2, a + 1, b + 1, 0.0, profit, profit / 2);
            double b2 = resolve(val2, a + 1, b, 0.0, profit, profit / 2);
            double c2 = resolve(val2, a, b + 1, 0.0, profit, profit / 2);

            auto v1 = [&](double p1, double p2) {
                return (-bribe(p1, l1) + expected(p1, p2, a1, b1, c1)) /
                       (p1 + p2 - p1 * p2);
            };
            auto v2 = [&](double p1, double p2) {
                return (-bribe(p2, l2) + expected(p1, p2, a2, b2, c2)) /
                       (p1 + p2 - p1 * p2);
            };
            auto br1 = [&](double p2) {
                return argmax([&](double q) { return v1(q, p2); });
            };
            auto br2 = [&](double p1) {
                return argmax([&](double q) { return v2(p1, q); });
            };
            auto gap = [&](double p1) { return br1(br2(p1)) - p1; };

            double x = lo, y = hi;
            for(int it = 0; it < 100; it++) {
                double m = (x + y) / 2;
                if(gap(m) > 0) {
                    x = m;
                } else {
                    y = m;
                }
            }

            double p1 = (x + y) / 2, p2 = br2(p1);
            val1[a][b] = v1(p1, p2);
            val2[a][b] = v2(p1, p2);
            win1[a][b] = expected(
                             p1, p2, resolve(win1, a + 1, b + 1, 1.0, 0.0, 0.5),
                             resolve(win1, a + 1, b, 1.0, 0.0, 0.5),
                             resolve(win1, a, b + 1, 1.0, 0.0, 0.5)
                         ) /
                         (p1 + p2 - p1 * p2);
        }
    }

    cout << setprecision(9) << fixed << win1[0][0] << ' ' << 1 - win1[0][0]
         << '\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
import math


def solve():
    data = sys.stdin.read().strip().split()

    if not data:
        return

    n = int(data[0])
    f1 = float(data[1])
    f2 = float(data[2])
    profit = float(data[3])

    # val1[a][b] = equilibrium expected net payoff of player 1
    val1 = [[0.0 for _ in range(n + 1)] for _ in range(n + 1)]

    # val2[a][b] = equilibrium expected net payoff of player 2
    val2 = [[0.0 for _ in range(n + 1)] for _ in range(n + 1)]

    # win1[a][b] = probability that player 1 eventually wins
    win1 = [[0.0 for _ in range(n + 1)] for _ in range(n + 1)]

    # Logs used to convert success probability into bribe.
    log_f1 = math.log(1.0 - f1)
    log_f2 = math.log(1.0 - f2)

    # Minimum success probability is achieved with zero bribe.
    LO = 0.01

    # Probability 1 needs infinite bribe, so use a value just below 1.
    HI = 1.0 - 1e-12

    def bribe(p, log_f):
        """
        Convert success probability p into required bribe.

        p = 1 - 0.99 * (1 - F)^bribe

        Therefore:

        bribe = log((1 - p) / 0.99) / log(1 - F)
        """
        return math.log((1.0 - p) / 0.99) / log_f

    def expected_without_loop(p1, p2, both, only_p1, only_p2):
        """
        Expected value of the three advancing outcomes.

        Excludes the self-loop where both players fail.
        """
        return (
            p1 * p2 * both
            + p1 * (1.0 - p2) * only_p1
            + (1.0 - p1) * p2 * only_p2
        )

    def resolve(dp, a, b, p1_wins_value, p2_wins_value, tie_value):
        """
        Return value of state (a, b).

        If terminal, return the appropriate terminal value.
        Otherwise, return already-computed DP value.
        """
        if a == n and b == n:
            return tie_value

        if a == n:
            return p1_wins_value

        if b == n:
            return p2_wins_value

        return dp[a][b]

    def argmax(func):
        """
        Find maximum point of a single-peaked function on [LO, HI]
        using ternary search.
        """
        left = LO
        right = HI

        for _ in range(80):
            m1 = left + (right - left) / 3.0
            m2 = right - (right - left) / 3.0

            if func(m1) < func(m2):
                left = m1
            else:
                right = m2

        return (left + right) / 2.0

    # Process states backwards.
    for a in range(n - 1, -1, -1):
        for b in range(n - 1, -1, -1):

            # Future payoff values for player 1.
            both1 = resolve(
                val1,
                a + 1,
                b + 1,
                profit,
                0.0,
                profit / 2.0
            )

            only_p1_1 = resolve(
                val1,
                a + 1,
                b,
                profit,
                0.0,
                profit / 2.0
            )

            only_p2_1 = resolve(
                val1,
                a,
                b + 1,
                profit,
                0.0,
                profit / 2.0
            )

            # Future payoff values for player 2.
            both2 = resolve(
                val2,
                a + 1,
                b + 1,
                0.0,
                profit,
                profit / 2.0
            )

            only_p1_2 = resolve(
                val2,
                a + 1,
                b,
                0.0,
                profit,
                profit / 2.0
            )

            only_p2_2 = resolve(
                val2,
                a,
                b + 1,
                0.0,
                profit,
                profit / 2.0
            )

            def payoff1(p1, p2):
                """
                Expected net payoff of player 1 for fixed p1 and p2.
                """
                leave = p1 + p2 - p1 * p2
                cost = bribe(p1, log_f1)

                future = expected_without_loop(
                    p1,
                    p2,
                    both1,
                    only_p1_1,
                    only_p2_1
                )

                return (-cost + future) / leave

            def payoff2(p1, p2):
                """
                Expected net payoff of player 2 for fixed p1 and p2.
                """
                leave = p1 + p2 - p1 * p2
                cost = bribe(p2, log_f2)

                future = expected_without_loop(
                    p1,
                    p2,
                    both2,
                    only_p1_2,
                    only_p2_2
                )

                return (-cost + future) / leave

            def best_response1(p2):
                """
                Player 1's optimal p1 against fixed p2.
                """
                return argmax(lambda q: payoff1(q, p2))

            def best_response2(p1):
                """
                Player 2's optimal p2 against fixed p1.
                """
                return argmax(lambda q: payoff2(p1, q))

            def gap(p1):
                """
                Fixed-point equation:

                    p1 = best_response1(best_response2(p1))

                So the root of gap is an equilibrium p1.
                """
                return best_response1(best_response2(p1)) - p1

            # Bisection for equilibrium p1.
            left = LO
            right = HI

            for _ in range(100):
                mid = (left + right) / 2.0

                if gap(mid) > 0.0:
                    left = mid
                else:
                    right = mid

            p1 = (left + right) / 2.0
            p2 = best_response2(p1)

            # Store equilibrium expected payoffs.
            val1[a][b] = payoff1(p1, p2)
            val2[a][b] = payoff2(p1, p2)

            # Future winning probabilities for player 1.
            win_both = resolve(
                win1,
                a + 1,
                b + 1,
                1.0,
                0.0,
                0.5
            )

            win_only_p1 = resolve(
                win1,
                a + 1,
                b,
                1.0,
                0.0,
                0.5
            )

            win_only_p2 = resolve(
                win1,
                a,
                b + 1,
                1.0,
                0.0,
                0.5
            )

            leave = p1 + p2 - p1 * p2

            # Remove self-loop in the same way as for payoffs.
            win1[a][b] = expected_without_loop(
                p1,
                p2,
                win_both,
                win_only_p1,
                win_only_p2
            ) / leave

    ans1 = win1[0][0]
    ans2 = 1.0 - ans1

    print(f"{ans1:.9f} {ans2:.9f}")


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