<|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`:

\[
1-p = 0.99(1-F)^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, 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 \le 100
\]

states.

So the solution is easily fast enough.

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    double f1, f2, profit;

    cin >> n >> f1 >> f2 >> profit;

    /*
        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
    */
    vector<vector<double>> val1(n + 1, vector<double>(n + 1, 0.0));
    vector<vector<double>> val2(n + 1, vector<double>(n + 1, 0.0));
    vector<vector<double>> win1(n + 1, vector<double>(n + 1, 0.0));

    /*
        We will convert success probability p into required bribe.

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

        Therefore:

        bribe = log((1 - p) / 0.99) / log(1 - F)
    */
    double logF1 = log(1.0 - f1);
    double logF2 = log(1.0 - f2);

    const double LO = 0.01;

    /*
        p = 1 would require infinite bribe, so we use a value very close to 1.
    */
    const double HI = 1.0 - 1e-12;

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

    /*
        Computes:

        p1 * p2 * both
      + p1 * (1 - p2) * only1
      + (1 - p1) * p2 * only2

        This excludes the self-loop where both fail.
    */
    auto expected_without_loop = [](double p1, double p2,
                                    double both,
                                    double only1,
                                    double only2) {
        return p1 * p2 * both
             + p1 * (1.0 - p2) * only1
             + (1.0 - p1) * p2 * only2;
    };

    /*
        Return value of a future state.

        If the state is terminal, return the appropriate terminal value.
        Otherwise, return the already-computed DP value.
    */
    auto resolve = [&](const vector<vector<double>>& dp,
                       int a,
                       int b,
                       double p1WinsValue,
                       double p2WinsValue,
                       double tieValue) {
        if (a == n && b == n) {
            return tieValue;
        }

        if (a == n) {
            return p1WinsValue;
        }

        if (b == n) {
            return p2WinsValue;
        }

        return dp[a][b];
    };

    /*
        Ternary search for maximum of a single-peaked function on [LO, HI].
    */
    auto argmax = [&](auto func) {
        double left = LO;
        double right = HI;

        for (int it = 0; it < 80; it++) {
            double m1 = left + (right - left) / 3.0;
            double m2 = right - (right - left) / 3.0;

            if (func(m1) < func(m2)) {
                left = m1;
            } else {
                right = m2;
            }
        }

        return (left + right) / 2.0;
    };

    /*
        Process states backwards.

        From (a, b), every non-self-loop transition goes to:
        (a + 1, b + 1), (a + 1, b), or (a, b + 1).

        Therefore descending order guarantees these states are already known.
    */
    for (int a = n - 1; a >= 0; a--) {
        for (int b = n - 1; b >= 0; b--) {

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

            double onlyP1_1 = resolve(val1, a + 1, b,
                                      profit, 0.0, profit / 2.0);

            double onlyP2_1 = resolve(val1, a, b + 1,
                                      profit, 0.0, profit / 2.0);

            /*
                Future payoff values for player 2.

                From player 2's payoff perspective:
                - if player 1 finishes first, player 2 gets 0;
                - if player 2 finishes first, player 2 gets profit.
            */
            double both2 = resolve(val2, a + 1, b + 1,
                                   0.0, profit, profit / 2.0);

            double onlyP1_2 = resolve(val2, a + 1, b,
                                      0.0, profit, profit / 2.0);

            double onlyP2_2 = resolve(val2, a, b + 1,
                                      0.0, profit, profit / 2.0);

            /*
                Payoff of player 1 for fixed probabilities p1 and p2.
            */
            auto payoff1 = [&](double p1, double p2) {
                double leave = p1 + p2 - p1 * p2;
                double cost = bribe(p1, logF1);

                double future = expected_without_loop(
                    p1, p2,
                    both1,
                    onlyP1_1,
                    onlyP2_1
                );

                return (-cost + future) / leave;
            };

            /*
                Payoff of player 2 for fixed probabilities p1 and p2.
            */
            auto payoff2 = [&](double p1, double p2) {
                double leave = p1 + p2 - p1 * p2;
                double cost = bribe(p2, logF2);

                double future = expected_without_loop(
                    p1, p2,
                    both2,
                    onlyP1_2,
                    onlyP2_2
                );

                return (-cost + future) / leave;
            };

            /*
                Best response of player 1 to fixed p2.
            */
            auto bestResponse1 = [&](double p2) {
                return argmax([&](double q) {
                    return payoff1(q, p2);
                });
            };

            /*
                Best response of player 2 to fixed p1.
            */
            auto bestResponse2 = [&](double p1) {
                return argmax([&](double q) {
                    return payoff2(p1, q);
                });
            };

            /*
                Equilibrium satisfies:

                    p1 = bestResponse1(p2)
                    p2 = bestResponse2(p1)

                Substitute p2:

                    p1 = bestResponse1(bestResponse2(p1))
            */
            auto gap = [&](double p1) {
                return bestResponse1(bestResponse2(p1)) - p1;
            };

            /*
                Solve gap(p1) = 0 by bisection.
            */
            double left = LO;
            double right = HI;

            for (int it = 0; it < 100; it++) {
                double mid = (left + right) / 2.0;

                if (gap(mid) > 0.0) {
                    left = mid;
                } else {
                    right = mid;
                }
            }

            double p1 = (left + right) / 2.0;
            double p2 = bestResponse2(p1);

            /*
                Store equilibrium expected net payoffs.
            */
            val1[a][b] = payoff1(p1, p2);
            val2[a][b] = payoff2(p1, p2);

            /*
                Compute player 1's winning probability from this state.
            */
            double winBoth = resolve(win1, a + 1, b + 1,
                                     1.0, 0.0, 0.5);

            double winOnlyP1 = resolve(win1, a + 1, b,
                                       1.0, 0.0, 0.5);

            double winOnlyP2 = resolve(win1, a, b + 1,
                                       1.0, 0.0, 0.5);

            double leave = p1 + p2 - p1 * p2;

            win1[a][b] = expected_without_loop(
                p1, p2,
                winBoth,
                winOnlyP1,
                winOnlyP2
            ) / leave;
        }
    }

    cout << fixed << setprecision(9)
         << win1[0][0] << ' ' << 1.0 - win1[0][0] << '\n';

    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()
```