a

// div2 easy
public class CoinFlipsDiv2 {
  public int countCoins(String state) {
    int n = state.length();
    int res = 0;
    for (int i = 0; i < n; i++) {
      boolean add = false;
      if (i > 0 && state.charAt(i-1) != state.charAt(i)) add=true;
      if (i+1 < n && state.charAt(i+1) != state.charAt(i)) add=true;
      if (add) res++;
    }
    return res;
  }
}

// div2 med
public class ExplodingRobots {
  public String canExplode(int x1, int y1, int x2, int y2, String instructions) {
    int x = Math.abs(x1-x2);
    int y = Math.abs(y1-y2);
    for (char c : instructions.toCharArray()) {
      if (c == 'R' || c == 'L') x -= 1;
      if (c == 'U' || c == 'D') y -= 1;
    }
    return x <= 0 && y <= 0 ? "Explosion" : "Safe";
  }
}

// div2 hard
import java.util.Arrays;
public class XorLists {
  public int n, m;
  public int[][] b;
  public int countLists(int[] s, int max) {
    n = 0;
    m = max;
    while(n*n < s.length) n++;

    b = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        b[i][j] = s[i*n+j];
      }
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          if ((b[i][j] ^ b[j][k]) != b[i][k]) {
            return 0;
          }
        }
      }
    }

    dp = new int[32][(1<<n)];
    for(int[] x : dp) Arrays.fill(x, -1);
    return count(31, 0);
  }
  public int[][] dp;
  public int count(int bit, int mask) {
    if (bit < 0) return 1;
    if (dp[bit][mask] != -1) return dp[bit][mask];

    int[] a = new int[n];
    for (int i = 1; i < n; i++) {
      a[i] = (b[0][i] >> bit) & 1;
    }
    int count = 0;
    int cb = (m >> bit) & 1;
    for (int tt = 0; tt < 2; tt++) {
      int nmask = mask;
      boolean ok = true;
      for (int i = 0; i < n; i++) {
        if (a[i] > cb && (mask&(1<<i)) == 0) {
          ok = false;
        }
        if (a[i] < cb) nmask |= 1 << i;
      }
      if (ok) {
        count += count(bit-1, nmask);
      }
      for (int i = 0; i < n; i++) a[i] ^= 1;
    }
    return dp[bit][mask] = count;
  }
}