aa

// div2 easy
public class FarmvilleDiv2 {
    public int minTime(int[] time, int[] cost, int budget) {
        int n = time.length;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (cost[i] > cost[j]) {
                    int t;
                    t = cost[i]; cost[i] = cost[j]; cost[j] = t;
                    t = time[i]; time[i] = time[j]; time[j] = t;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += time[i];
            int take = Math.min(time[i], budget / cost[i]);
            budget -= cost[i] * take;
            sum -= take;
        }
        return sum;
    }
}

// div2 med
public class BoardEscapeDiv2 {
    public int[] dx = {-1,0,1,0}, dy = {0,-1,0,1};
    public String findWinner(String[] s, int k) {
        int n = s.length, m = s[0].length();
        char[][] board = new char[n][m];
        for (int i = 0; i < n; i++)
            board[i] = s[i].toCharArray();

        boolean[][] win = new boolean[n][m];
        for (int r = 0; r < k; r++) {
            boolean[][] nwin = new boolean[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (board[i][j] == 'E') continue;
                    for (int w = 0; w < 4; w++) {
                        int ni = i+dx[w], nj = j+dy[w];
                        if (ni >= 0 && ni < n && nj >= 0 && nj < m && board[ni][nj] != '#') {
                            nwin[i][j] |= !win[ni][nj];
                        }
                    }
                }
            }
            win = nwin;
        }

        int tx = 0, ty = 0;
        outer : for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'T') {
                    tx = i;
                    ty = j;
                    break outer;
                }
            }
        }

        return win[tx][ty] ? "Alice" : "Bob";

    }
}


// div2 hard
import java.util.ArrayList;
public class RailroadSwitchOperator {
  public int minEnergy(int N, int[] x, int[] t) {
    int m = t.length;
    its = new ArrayList<>();
    curstate = new int[4*(N+1)];
    lasttime = new int[4*(N+1)];
    for (int i = 0; i < m; i++) {
      simulate(t[i], 1, 1, N, x[i]);
    }

    int ans = 0;
    while (its.size() > 0) {
      ++ans;
      int min = Integer.MAX_VALUE;
      for (Interval w : its) {
        if (w.b < min) {
          min = w.b;
        }
      }

      ArrayList<Interval> next = new ArrayList<>();
      for (Interval w : its) {
        if (min < w.a)
          next.add(w);
      }

      its = next;
    }
    return ans;
  }

  static class Interval {
    public int a,b;
    public Interval(int a, int b) {
      this.a = a;
      this.b = b;
    }
  }
  public ArrayList<Interval> its;
  public int[] curstate;
  public int[] lasttime;
  public void simulate(int curtime, int curindex, int start, int end, int pos) {
    if (start == pos && end == pos) return;
    int mid = (start+end) / 2;
    int need = mid >= pos ? 0 : 1;
    if (curstate[curindex] != need) {
      its.add(new Interval(lasttime[curindex]+1, curtime));
      curstate[curindex] = need;
    }
    lasttime[curindex] = curtime;
    if (mid >= pos) simulate(curtime+1, 2*curindex, start, mid, pos);
    else simulate(curtime+1, 2*curindex+1, mid+1, end, pos);
  }
}