Untitled

//Klaara's Forest
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Point {
    int x;
    int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Fortress {
    Point[] array;
    int front;
    int rear;

    Fortress(int size) {
        array = new Point[size];
        front = -1;
        rear = -1;
    }
}

public class MaxThiefTime {

    private static void initQueue(Fortress q) {
        q.front = -1;
        q.rear = -1;
    }

    private static boolean isEmpty(Fortress q) {
        return q.front == -1;
    }

    private static void enqueue(Fortress q, Point p) {
        if (isEmpty(q)) {
            q.front = 0;
            q.rear = 0;
        } else {
            q.rear++;
        }
        q.array[q.rear] = p;
    }

    private static Point dequeue(Fortress q) {
        Point p = q.array[q.front];
        if (q.front == q.rear) {
            q.front = -1;
            q.rear = -1;
        } else {
            q.front++;
        }
        return p;
    }

    private static int max(int a, int b) {
        return (a > b) ? a : b;
    }

    private static int min(int a, int b) {
        return (a < b) ? a : b;
    }

    private static int maxThiefTime(int m, int n, int[][] fortress) {
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int placementlelo = 0;

        int bfs(int start_x, int start_y) {
            boolean[][] visited = new boolean[MAX_M][MAX_N];
            int[][] distance = new int[MAX_M][MAX_N];
            Fortress q = new Fortress(MAX_M * MAX_N);
            initQueue(q);
            Point start = new Point(start_x, start_y);
            enqueue(q, start);
            visited[start_x][start_y] = true;

            while (!isEmpty(q)) {
                Point p = dequeue(q);
                for (int i = 0; i < 4; i++) {
                    int nx = p.x + directions[i][0];
                    int ny = p.y + directions[i][1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && fortress[nx][ny] == 0) {
                        distance[nx][ny] = distance[p.x][p.y] + 1;
                        visited[nx][ny] = true;

                        Point newPoint = new Point(nx, ny);
                        enqueue(q, newPoint);
                    }
                }
            }
            return distance[m - 1][n - 1];
        }

        int distance = bfs(0, 0);
        placementlelo = distance;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (fortress[i][j] == 0) {
                    fortress[i][j] = 1;
                    distance = bfs(0, 0);
                    placementlelo = max(placementlelo, distance);
                    fortress[i][j] = 0;
                }
            }
        }

        return placementlelo + 1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] fortress = new int[MAX_M][MAX_N];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                fortress[i][j] = scanner.nextInt();
            }
        }

        int result = maxThiefTime(m, n, fortress);
        System.out.println(result);
    }
}

//ROI
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Tuple;

public class StockAnalysis {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        List<Tuple<Integer, Integer, Integer>> stocks = new ArrayList<>();

        for (int i = 0; i < n; ++i) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            stocks.add(new Tuple<>(a, b, c));
        }

        int m = scanner.nextInt();
        int real = 0, unreal = 0;
        List<List<Integer>> placementlelo = new ArrayList<>();

        for (int i = 0; i < n; ++i) {
            List<Integer> arr = new ArrayList<>();
            for (int j = 0; j < m; ++j) {
                arr.add(scanner.nextInt());
            }
            placementlelo.add(arr);
        }

        int day = scanner.nextInt();

        for (int i = 0; i < n; ++i) {
            int a, b, c;
            Tuple<Integer, Integer, Integer> stock = stocks.get(i);
            a = stock.getFirst();
            b = stock.getSecond();
            c = stock.getThird();

            if (b > day) {
                continue;
            } else if (c > day || c == 0) {
                unreal += a * (placementlelo.get(i).get(day - 1) - placementlelo.get(i).get(b - 1));
            } else {
                real += a * (placementlelo.get(i).get(c - 1) - placementlelo.get(i).get(b - 1));
            }
        }

        System.out.println(real);
        System.out.println(unreal);
    }
}

//X from Y
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int[][] dp;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String x = scanner.next();
        String y = scanner.next();
        int s = scanner.nextInt();
        int r = scanner.nextInt();

        dp = new int[10001][10001];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], -1);
        }

        int ans = solve(s, r, x, y);
        if (ans == 1e9) {
            System.out.println("Impossible");
            return;
        }

        System.out.println(ans);
    }

    static int f(int i, int j, int s, int r, String x, String y, String y1) {
        if (i > j) return 0;
        if (dp[i][j] != -1) return dp[i][j];

        int mini = 1e9;
        for (int k = i; k <= j; k++) {
            if (y1.contains(x.substring(i, k + 1))) mini = Math.min(mini, r + f(k + 1, j, s, r, x, y, y1));
            if (y.contains(x.substring(i, k + 1))) mini = Math.min(mini, s + f(k + 1, j, s, r, x, y, y1));
        }

        return dp[i][j] = mini;
    }

    static int solve(int s, int r, String x, String y) {
        String y1 = new StringBuilder(y).reverse().toString();
        return f(0, x.length() - 1, s, r, x, y, y1);
    }
}

//Lucky
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static String toggle(String num) {
        StringBuilder result = new StringBuilder();
        for (char bit : num.toCharArray()) {
            if (bit == '0') {
                result.append('1');
            } else {
                result.append('0');
            }
        }
        return result.toString();
    }

    private static Pair<Integer, List<Integer>> getMaxSum(List<Integer> arr, int k) {
        int maxIndex = arr.indexOf(arr.stream().max(Integer::compare).orElseThrow());
        int left = Math.max(0, maxIndex - k);
        int right = Math.min(arr.size() - 1, maxIndex + k);

        List<Integer> selected = new ArrayList<>(arr.subList(left, maxIndex + 1));
        selected.addAll(arr.subList(maxIndex, right + 1));

        arr.removeIf(x -> selected.contains(x));

        int sum = selected.stream().mapToInt(Integer::intValue).sum();

        return new Pair<>(sum, arr);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> arr = new ArrayList<>();

        while (scanner.hasNextInt()) {
            arr.add(scanner.nextInt());
        }

        String a1 = scanner.next();
        String b1 = scanner.next();
        String a2 = scanner.next();
        String b2 = scanner.next();

        int k = scanner.nextInt();
        int sum1 = 0, sum2 = 0;

        while (!arr.isEmpty()) {
            Pair<Integer, List<Integer>> result1 = getMaxSum(new ArrayList<>(arr), k);
            sum1 += result1.getFirst();

            if (arr.isEmpty()) {
                break;
            }

            Pair<Integer, List<Integer>> result2 = getMaxSum(new ArrayList<>(arr), k);
            sum2 += result2.getFirst();
        }

        if (sum1 > sum2) {
            a1 = toggle(a1);
            b2 = toggle(b2);
        } else {
            a2 = toggle(a2);
            b1 = toggle(b1);
        }

        int xor1 = Integer.parseInt(a1, 2) ^ Integer.parseInt(b1, 2);
        int xor2 = Integer.parseInt(a2, 2) ^ Integer.parseInt(b2, 2);

        if (xor1 > xor2) {
            System.out.println("Rahul");
        } else if (xor2 > xor1) {
            System.out.println("Rupesh");
        } else {
            System.out.println("both");
        }
    }

    static class Pair<T, U> {
        private final T first;
        private final U second;

        Pair(T first, U second) {
            this.first = first;
            this.second = second;
        }

        T getFirst() {
            return first;
        }

        U getSecond() {
            return second;
        }
    }
}