## 1. Abridged problem statement

For each input integer `N` (`1 ≤ N ≤ 50`), two players play a zero-sum game.

- vot secretly chooses `a` from `1..N`.
- Goryinyich, without knowing `a`, chooses `b` from `1..N`.
- If `|a - b| = 1`, Goryinyich gains `$1`.
- Otherwise, Goryinyich loses `$1`.

Both players play optimally, possibly using randomized strategies. For every `N`, output Goryinyich’s expected gain as an irreducible fraction in the format:

```text
Case #k: numerator/denominator
```

Input contains up to 10 test cases.



## 2. Detailed editorial

The long first game in the statement is irrelevant. The real problem is the second game.

We have a finite two-player zero-sum game. Let the payoff to Goryinyich be:

\[
P[a][b] =
\begin{cases}
1, & |a-b|=1 \\
-1, & \text{otherwise}
\end{cases}
\]

vot chooses the row `a`, Goryinyich chooses the column `b`.

By the minimax theorem, the optimal expected gain is the value of this matrix game.

---

### Reformulating the payoff

Define an adjacency matrix of a path graph on `N` vertices:

\[
A[a][b] =
\begin{cases}
1, & |a-b|=1 \\
0, & \text{otherwise}
\end{cases}
\]

Then:

\[
P[a][b] = 2A[a][b] - 1
\]

So if Goryinyich uses probability distribution `q` over choices `b`, and vot chooses a fixed `a`, the probability that Goryinyich wins is:

\[
q_{a-1} + q_{a+1}
\]

where missing indices outside `1..N` are treated as `0`.

The expected payoff is:

\[
2(q_{a-1} + q_{a+1}) - 1
\]

Goryinyich wants to maximize the minimum winning probability over all possible `a`.

Let:

\[
\alpha = \max_q \min_a (q_{a-1} + q_{a+1})
\]

Then the answer is:

\[
2\alpha - 1
\]

---

### Computing `α`

We need:

\[
\max t
\]

subject to:

\[
q_{a-1} + q_{a+1} \ge t
\]

for all `a`, and:

\[
\sum q_i = 1,\quad q_i \ge 0
\]

Instead of solving this LP directly, scale by `t`.

Let:

\[
x_i = \frac{q_i}{t}
\]

Then constraints become:

\[
x_{a-1} + x_{a+1} \ge 1
\]

and:

\[
\sum x_i = \frac{1}{t}
\]

Therefore maximizing `t` is equivalent to minimizing:

\[
\gamma = \sum x_i
\]

under:

\[
x_{a-1} + x_{a+1} \ge 1,\quad x_i \ge 0
\]

Then:

\[
\alpha = \frac{1}{\gamma}
\]

This is a fractional covering problem on a path.

---

### Splitting by parity

The constraint for vertex `a` uses only neighbors of opposite parity.

So variables on even positions cover odd positions, and variables on odd positions cover even positions. The LP splits into two independent path-like covering problems.

The resulting closed form is:

#### Case `N = 1`

There is no `b` such that `|a-b|=1`, so Goryinyich always loses.

\[
\alpha = 0
\]

Answer:

\[
-1
\]

#### Case `N` is odd

Let:

\[
N = 2m + 1
\]

Then:

\[
\gamma = m + 1 = \frac{N+1}{2}
\]

So:

\[
\alpha = \frac{2}{N+1}
\]

Answer:

\[
2\alpha - 1 = \frac{4}{N+1} - 1 = \frac{3-N}{N+1}
\]

#### Case `N` is divisible by `4`

Let:

\[
N = 4k
\]

Then:

\[
\gamma = \frac{N}{2}
\]

So:

\[
\alpha = \frac{2}{N}
\]

Answer:

\[
2\alpha - 1 = \frac{4}{N} - 1 = \frac{4-N}{N}
\]

#### Case `N ≡ 2 mod 4`

Then:

\[
\gamma = \frac{N}{2} + 1 = \frac{N+2}{2}
\]

So:

\[
\alpha = \frac{2}{N+2}
\]

Answer:

\[
2\alpha - 1 = \frac{4}{N+2} - 1 = \frac{2-N}{N+2}
\]

Finally, reduce the fraction.

---

### Relation to the provided C++ solution

The provided C++ solution uses a general simplex implementation instead of the closed form.

It directly solves the linear program:

\[
\max v
\]

such that for every possible vot choice `a`:

\[
\sum_b q_b P[a][b] \ge v
\]

and:

\[
\sum_b q_b = 1,\quad q_b \ge 0
\]

The value `v` is exactly Goryinyich’s optimal expected gain.

Because simplex assumes nonnegative variables and `≤` constraints, the code:

1. Substitutes the last probability using:

   \[
   q_N = 1 - \sum_{j<N} q_j
   \]

2. Splits the unrestricted variable `v` into:

   \[
   v = v_+ - v_-
   \]

3. Runs two-phase simplex.

The computed decimal value is then converted to a small rational fraction.



## 3. Provided C++ solution with detailed comments

```cpp
#include <bits/stdc++.h> // Includes almost all standard C++ headers.

// #include <coding_library/math/simplex.hpp>

using namespace std;

// Output operator for pairs: prints "first second".
template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

// Input operator for pairs: reads "first second".
template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

// Input operator for vectors: reads every element of the vector.
template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

// Output operator for vectors: prints all elements separated by spaces.
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

// Generic simplex solver for linear programs.
//
// It solves problems of the form:
//
// maximize     objective * x
// subject to   constraints[i] * x <= rhs[i]
//              x[j] >= 0
//
// T is usually long double here.
template<class T = long double>
class Simplex {
  public:
    // Possible outcomes of the linear program.
    enum class Status { OPTIMAL, INFEASIBLE, UNBOUNDED };

    // Result returned by the simplex solver.
    struct Result {
        Status status = Status::INFEASIBLE; // Default status.
        T value = 0;                        // Optimal objective value.
        vector<T> x;                        // Optional optimal variable values.
    };

    // Floating-point tolerance.
    static T eps() { return T(1e-9); }

    // Large infinity-like value.
    static T inf() {
        // If T is floating point, use real infinity.
        if constexpr(is_floating_point_v<T>) {
            return numeric_limits<T>::infinity();
        }

        // Otherwise use a large integer value.
        return numeric_limits<T>::max() / T(4);
    }

    // Solve the LP:
    //
    // maximize objective^T x
    // subject to constraints x <= rhs
    //            x >= 0
    //
    // If recover_x is true, also reconstruct an optimal x.
    Result solve(
        const vector<vector<T>>& constraints,
        const vector<T>& rhs,
        const vector<T>& objective,
        bool recover_x = false
    ) {
        Result res; // Initially infeasible.

        // m = number of constraints.
        m = (int)rhs.size();

        // n = number of original variables.
        n = (int)objective.size();

        // If there are no constraints, x = 0 is feasible and optimal
        // unless the objective is unbounded; this implementation returns 0.
        if(m == 0) {
            res.status = Status::OPTIMAL;

            if(recover_x) {
                res.x.assign(n, 0);
            }

            return res;
        }

        // Number of original variables plus slack variables.
        const int slack = n + m;

        // Index of the RHS column in the tableau.
        const int rhs_col = n + m + 1;

        // Total tableau width:
        // original variables + slack variables + artificial marker + RHS.
        const int width = n + m + 2;

        // N stores the variable index associated with each non-basic column.
        N.assign(width - 1, -1);

        // B stores the variable index associated with each basic row.
        B.assign(m + 1, 0);

        // D is the simplex tableau.
        //
        // Rows:
        // 0..m-1 = constraints
        // m      = real objective
        // m+1    = auxiliary objective for phase 1
        D.assign(m + 2, vector<T>(width, 0));

        // Fill constraint rows.
        for(int i = 0; i < m; i++) {
            // Copy coefficients of original variables.
            for(int j = 0; j < n; j++) {
                D[i][j] = constraints[i][j];
            }

            // Add slack variable for this constraint.
            D[i][n + i] = 1;

            // RHS value.
            D[i][rhs_col] = rhs[i];

            // Initially the slack variable is basic.
            B[i] = n + i;
        }

        // Initialize non-basic variables.
        for(int j = 0; j < slack; j++) {
            N[j] = j;
        }

        // Objective row stores -objective for maximization.
        for(int j = 0; j < n; j++) {
            D[m][j] = -objective[j];
        }

        // Mark artificial variable column.
        N[slack] = -1;

        // Auxiliary objective initially copies the real objective.
        D[m + 1] = D[m];

        // Artificial variable coefficient.
        D[m + 1][slack] = 1;

        // Auxiliary basic marker.
        B[m] = m + 1;

        // x is the initial entering column for phase 1.
        int x = n;

        // If any RHS is negative, we need an artificial variable.
        for(int i = 0; i < m; i++) {
            if(D[i][rhs_col] < -eps()) {
                x = slack;
            }
        }

        // Phase 1: find a feasible starting basis.
        if(!run_phase(1, x, slack, rhs_col)) {
            return res; // Infeasible.
        }

        // Phase 2: optimize the real objective.
        if(!run_phase(2, n, slack, rhs_col)) {
            res.status = Status::UNBOUNDED;
            return res;
        }

        // If phase 2 succeeds, the optimum was found.
        res.status = Status::OPTIMAL;

        // Optimal value is stored in RHS of objective row.
        res.value = D[m][rhs_col];

        // Optionally recover original variable values.
        if(recover_x) {
            res.x.assign(n, 0);

            // A variable has nonzero value only if it is basic.
            for(int i = 0; i < m; i++) {
                if(B[i] < n) {
                    res.x[B[i]] = D[i][rhs_col];
                }
            }
        }

        return res;
    }

  private:
    int m, n;             // Number of constraints and variables.
    vector<int> N, B;     // Non-basic and basic variable indices.
    vector<vector<T>> D;  // Tableau.

    // Pivot on row r and column s.
    //
    // The variable in column s enters the basis,
    // and the variable currently basic in row r leaves.
    void pivot(int r, int s, int width) {
        // Pivot value.
        T pv = D[r][s];

        // Normalize pivot row so pivot becomes 1.
        for(int j = 0; j < width; j++) {
            D[r][j] /= pv;
        }

        // Eliminate column s from all other rows.
        for(int i = 0; i < m + 2; i++) {
            // Skip pivot row.
            if(i == r) {
                continue;
            }

            // If coefficient is already approximately zero, skip.
            if(fabs(D[i][s]) <= eps()) {
                continue;
            }

            // Factor to eliminate.
            T f = D[i][s];

            // Row operation: row_i -= f * row_r.
            for(int j = 0; j < width; j++) {
                D[i][j] -= f * D[r][j];
            }
        }

        // Update basis information.
        B[r] = N[s];

        // Mark column as no longer representing a normal non-basic variable.
        N[s] = -1;
    }

    // Run one simplex phase.
    //
    // phase = 1: find feasibility.
    // phase = 2: optimize real objective.
    bool run_phase(int phase, int x, int slack, int rhs_col) {
        // Total tableau width.
        int width = n + m + 2;

        // Select objective row.
        int obj = phase == 1 ? m + 1 : m;

        // Safety iteration limit.
        for(int iter = 0; iter < 10000; iter++) {
            int s = -1; // Entering column.

            if(phase == 1) {
                // Phase 1 chooses an artificial/helping variable column.
                for(int j = 0; j < slack; j++) {
                    if(N[j] == -1 && j != x && D[obj][j] > eps()) {
                        s = j;
                    }
                }
            } else {
                // Phase 2: choose a column with negative reduced cost.
                T best = -eps();

                for(int j = 0; j < slack; j++) {
                    if(D[obj][j] < best) {
                        best = D[obj][j];
                        s = j;
                    }
                }
            }

            // If no entering variable exists, this phase is finished.
            if(s == -1) {
                if(phase == 1) {
                    // If artificial variable remains basic, infeasible.
                    for(int i = 0; i < m; i++) {
                        if(B[i] == slack) {
                            return false;
                        }
                    }
                }

                return true;
            }

            int r = -1; // Leaving row.
            T best_ratio = inf();

            // Ratio test to select leaving variable.
            for(int i = 0; i < m; i++) {
                if(phase == 1) {
                    // Phase 1 uses a special ratio rule.
                    if(D[i][s] < -eps()) {
                        T df = -D[i][rhs_col] / D[i][s];

                        if(r == -1 || df < -D[r][rhs_col] / D[r][s] - eps()) {
                            r = i;
                        }
                    }
                } else if(D[i][s] > eps()) {
                    // Standard ratio test:
                    // keep RHS nonnegative after increasing entering variable.
                    T ratio = D[i][rhs_col] / D[i][s];

                    if(ratio < best_ratio - eps()) {
                        best_ratio = ratio;
                        r = i;
                    }
                }
            }

            // If there is no leaving row, objective is unbounded.
            if(r == -1) {
                return false;
            }

            // Perform pivot.
            pivot(r, s, width);
        }

        // Too many iterations, treat as failure.
        return false;
    }
};

// Payoff to Goryinyich if vot chooses i and Goryinyich chooses j.
//
// Indices are 0-based.
// Goryinyich gains +1 iff the numbers differ by exactly 1.
// Otherwise he loses 1.
int payoff(int i, int j) {
    return abs(i - j) == 1 ? 1 : -1;
}

// Solve the matrix game for given n using linear programming.
long double solve_game(int n) {
    // We use variables:
    //
    // q_0, q_1, ..., q_{n-2} = probabilities for first n-1 choices of Goryinyich.
    //
    // The last probability q_{n-1} is implicit:
    //
    // q_{n-1} = 1 - sum(q_0..q_{n-2})
    //
    // Additionally, the game value v is unrestricted,
    // so it is represented as:
    //
    // v = v_plus - v_minus
    //
    // where both v_plus and v_minus are nonnegative.
    int cols = max(n - 1, 0) + 2;

    // Column index for v_plus.
    int vp = n - 1;

    // Column index for v_minus.
    int vm = n;

    // LP constraint matrix, RHS vector, and objective vector.
    vector<vector<long double>> a;
    vector<long double> b, c(cols);

    // Objective is maximize v_plus - v_minus.
    c[vp] = 1;
    c[vm] = -1;

    // For every possible choice i by vot, require:
    //
    // expected_payoff_against_i >= v
    //
    // The simplex solver supports <= constraints, so this is rearranged into:
    //
    // v - sum_j q_j * (P[i][j] - P[i][last]) <= P[i][last]
    for(int i = 0; i < n; i++) {
        // New constraint row.
        vector<long double> row(cols);

        // Payoff if Goryinyich uses the implicit last column.
        int pin = payoff(i, n - 1);

        // Coefficients for explicit probabilities q_0..q_{n-2}.
        for(int j = 0; j < n - 1; j++) {
            row[j] = -(payoff(i, j) - pin);
        }

        // Coefficient of v_plus.
        row[vp] = 1;

        // Coefficient of v_minus, because v = v_plus - v_minus.
        row[vm] = -1;

        // Store the constraint.
        a.push_back(row);

        // RHS.
        b.push_back(pin);
    }

    // Constraint ensuring implicit probability is nonnegative:
    //
    // sum(q_0..q_{n-2}) <= 1
    if(n > 1) {
        vector<long double> box(n - 1, 1);

        // Remaining entries for v_plus and v_minus are implicitly 0.
        a.push_back(box);

        // RHS is 1.
        b.push_back(1);
    }

    // Solve the LP.
    auto res = Simplex<long double>().solve(a, b, c);

    // If something goes wrong, return 0.
    if(res.status != Simplex<long double>::Status::OPTIMAL) {
        return 0;
    }

    // Return optimal game value.
    return res.value;
}

// Convert a long double value to a small rational fraction.
//
// The true answer has small denominator for N <= 50,
// so trying denominators up to 200 is enough here.
pair<int64_t, int64_t> to_fraction(long double x) {
    // Try denominators from 1 to 200.
    for(int64_t den = 1; den <= 200; den++) {
        // Closest numerator for this denominator.
        int64_t num = llround(x * den);

        // Check whether num / den is close enough to x.
        if(fabsl(x - (long double)num / den) < 1e-8) {
            // Reduce by gcd.
            int64_t g = gcd(llabs(num), den);

            return {num / g, den / g};
        }
    }

    // Fallback: round to an integer.
    int64_t den = 1;
    int64_t num = llround(x);

    return {num, den};
}

// Current input N.
int n;

// Read one test case.
bool read() {
    return bool(cin >> n);
}

// Solve one test case.
void solve() {
    // The opening story is a red herring. The game we care about is the second
    // one: vot picks a in [1, N], Goryinyich picks b in [1, N] without seeing
    // a, and if |a-b| = 1 then vot pays Goryinyich a dollar, otherwise
    // Goryinyich pays vot. Both players maximize expected gain, so this is a
    // two-player zero-sum matrix game. Rows are vot's choices, columns are
    // Goryinyich's, and the payoff is P[a][b] = +1 when |a-b| = 1 and -1
    // otherwise.
    //
    // Rational play means a Nash equilibrium: neither player can improve
    // expected gain by unilaterally changing their mixed strategy. In zero-sum
    // games, every Nash equilibrium is a minimax pair (sigma, tau), and the
    // expected payoff E(sigma, tau) is the same at every equilibrium; that
    // common number is the game value v we output.
    //
    // With sigma on rows and tau on columns,
    //
    //     E(sigma, tau) = sum_{a,b} sigma(a) tau(b) P[a][b].
    //
    // Von Neumann's minimax theorem says v is unique and
    //
    //     v = max_tau min_sigma E = min_sigma max_tau E.
    //
    // How do we find the game value? Build the N x N matrix P and write two
    // linear programs. Goryinyich is the column player (maximizer). He chooses
    // a mixed strategy tau and a number v with the meaning: "no matter which a
    // vot plays, my expected payoff is at least v." Formally,
    //
    //     maximize v
    //     subject to   sum_j tau_j * P[i][j] >= v   for i = 1..N
    //                sum_j tau_j = 1
    //                tau_j >= 0
    //
    // So v is the best payoff Goryinyich can guarantee for himself by picking
    // tau; it is a lower bound on what he actually earns at equilibrium. vot is
    // the row player (minimizer). He chooses sigma and a number u with the
    // meaning: "no matter which b Goryinyich plays, his expected payoff is at
    // most u." Formally,
    //
    //     minimize u
    //     subject to   sum_i sigma_i * P[i][j] <= u   for j = 1..N
    //                sum_i sigma_i = 1
    //                sigma_i >= 0
    //
    // So u is the most Goryinyich can be forced to accept once vot plays sigma;
    // it is an upper bound on Goryinyich's payoff. Any real play sits between
    // these two stories: Goryinyich pushes v up, vot pushes u down.
    //
    // Strong duality applies because both programs are feasible and bounded
    // (payoffs lie in [-1, 1]). Then the optimal v and optimal u coincide, and
    // that common value is exactly the Nash/minimax game value we print.
    //
    // We solve the primal directly: substitute tau_N = 1 - sum_{j<N} tau_j,
    // split v = v_plus - v_minus with both nonnegative, and run two-phase
    // simplex on that standard-form LP. N <= 50 keeps the tableau small. The
    // optimum is rational and we print it in lowest terms.

    // Compute optimal expected payoff.
    long double val = solve_game(n);

    // Convert approximate floating-point answer to exact-looking fraction.
    auto [num, den] = to_fraction(val);

    // Print irreducible fraction.
    cout << num << "/" << den << "\n";
}

int main() {
    // Fast input/output.
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // Read until EOF.
    for(int test = 1; read(); test++) {
        // Required case prefix.
        cout << "Case #" << test << ": ";

        // Solve this test case.
        solve();
    }

    return 0;
}
```



## 4. Python solution with detailed comments

This Python version uses the closed-form result from the editorial.

```python
import sys
from math import gcd


def game_value_fraction(n: int) -> tuple[int, int]:
    """
    Return Goryinyich's optimal expected gain as an irreducible fraction.

    The expected gain is:
        2 * alpha - 1

    where alpha is the optimal probability that |a - b| = 1.

    Closed forms:
      n = 1:
          answer = -1

      n odd:
          answer = (3 - n) / (n + 1)

      n divisible by 4:
          answer = (4 - n) / n

      n == 2 mod 4:
          answer = (2 - n) / (n + 2)
    """

    # Special case: with only one number, |a-b| can never be 1.
    # Therefore Goryinyich always loses 1 dollar.
    if n == 1:
        return -1, 1

    # If n is odd, use (3 - n) / (n + 1).
    if n % 2 == 1:
        numerator = 3 - n
        denominator = n + 1

    # If n is divisible by 4, use (4 - n) / n.
    elif n % 4 == 0:
        numerator = 4 - n
        denominator = n

    # Otherwise n is even but not divisible by 4, so n == 2 mod 4.
    # Use (2 - n) / (n + 2).
    else:
        numerator = 2 - n
        denominator = n + 2

    # Reduce the fraction to lowest terms.
    g = gcd(abs(numerator), denominator)
    numerator //= g
    denominator //= g

    # Return the reduced fraction.
    return numerator, denominator


def main() -> None:
    # Read all integers from input.
    data = sys.stdin.read().strip().split()

    # Process every input line / integer.
    for case_id, token in enumerate(data, start=1):
        # Parse N.
        n = int(token)

        # Compute answer.
        numerator, denominator = game_value_fraction(n)

        # Print in required format.
        print(f"Case #{case_id}: {numerator}/{denominator}")


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



## 5. Compressed editorial

The real game is a zero-sum matrix game with payoff `+1` if `|a-b|=1`, otherwise `-1`.

Let `q_i` be Goryinyich’s probability of choosing `i`. For fixed vot choice `a`, Goryinyich wins with probability:

\[
q_{a-1}+q_{a+1}
\]

So if:

\[
\alpha = \max_q \min_a (q_{a-1}+q_{a+1})
\]

then the expected gain is:

\[
2\alpha - 1
\]

Scale by setting `x_i = q_i / α`. Then minimizing:

\[
\gamma = \sum x_i
\]

subject to:

\[
x_{a-1}+x_{a+1} \ge 1
\]

gives:

\[
\alpha = \frac{1}{\gamma}
\]

The constraints split by parity on the path graph.

The final formulas are:

- `N = 1`:

\[
-1/1
\]

- `N` odd:

\[
\frac{3-N}{N+1}
\]

- `N ≡ 0 mod 4`:

\[
\frac{4-N}{N}
\]

- `N ≡ 2 mod 4`:

\[
\frac{2-N}{N+2}
\]

Reduce the fraction and print it.