// Liam Keliher, 2024 // // RTE submission for problem "Brownian Bears" (brownianbears) // // Same as BrownianBearsKeliher.java, but uses int everywhere, never long. // This was originally intended to be a WA submission. The reason it produces // a run-time error is that as soon as the denominator, which is always a power // of 2, is >= 2^32, it wraps around to 0, and if the numerator is also 0, this // results in the call gcd(0,0), which returns 0, since the gcd() method is not // written to handle this edge case. This in turn leads to division by zero. import java.io.*; public class RTE_Overflow { //--------------------------------------------------------------- public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] tokens = br.readLine().split(" "); int n = Integer.parseInt(tokens[0]); int x = Integer.parseInt(tokens[1]); int y = Integer.parseInt(tokens[2]); int numDays = Integer.parseInt(tokens[3]); int[][] prev = new int[n + 1][n + 1]; // 1-based indexing int leftPos = Math.min(x, y); int rightPos = Math.max(x, y); prev[leftPos][rightPos] = 1; int diagonalTotal = 0; for (int d = 1; d <= numDays; d++) { int[][] curr = new int[n + 1][n + 1]; // 1-based indexing for (int i = 1; i < n; i++) { for (int j = i + 1; j <= n; j++) { int prevEntry = prev[i][j]; if (prevEntry > 0) { // both move left int iNew = Math.max(i - 1, 1); int jNew = j - 1; curr[iNew][jNew] += prevEntry; // both move right iNew = i + 1; jNew = Math.min(j + 1, n); curr[iNew][jNew] += prevEntry; // both move outward iNew = Math.max(i - 1, 1); jNew = Math.min(j + 1, n); curr[iNew][jNew] += prevEntry; // both move inward (might swap positions) iNew = i + 1; jNew = j - 1; if (iNew < jNew) { curr[iNew][jNew] += prevEntry; } // if else { curr[jNew][iNew] += prevEntry; } // else } // if } // for j } // for i prev = curr; // Add up the values on the diagonal int numOnDiagonal = 0; for (int i = 1; i <= n; i++) { numOnDiagonal += curr[i][i]; } // for i diagonalTotal = 4*diagonalTotal + numOnDiagonal; } // for d int denom = (1 << numDays)*(1 << numDays); int g = gcd(diagonalTotal, denom); System.out.println(diagonalTotal/g + "/" + denom/g); } // main(String[]) //--------------------------------------------------------------- static int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } // while return a; } // gcd(int,int) //--------------------------------------------------------------- } // class RTE_Overflow