fork download
  1.  
  2.  
  3. public class CheeseRolling
  4. {
  5. int N;
  6. int[][] winner;
  7. long[][] cache;
  8. int[][] chooses;
  9. int[] nxt;
  10. long[] fact;
  11.  
  12. boolean powerOf2(int x)
  13. {
  14. return (x & (x - 1)) == 0;
  15. }
  16.  
  17. long[] f(int st)
  18. {
  19. if (cache[st] != null)
  20. return cache[st];
  21. if (powerOf2(st))
  22. {
  23. cache[st] = new long[N];
  24. for (int i = 0; i < N; i++) if (st == (1 << i))
  25. {
  26. cache[st][i] = 1;
  27. return cache[st];
  28. }
  29. }
  30. int cnt = Integer.bitCount(st) / 2;
  31. long[] ans = new long[N];
  32. for (int i = 0; i < nxt[cnt]; i++) if ((chooses[cnt][i] & st) == chooses[cnt][i])
  33. {
  34. long[] A = f(chooses[cnt][i]);
  35. long[] B = f(chooses[cnt][i] ^ st);
  36. for (int a = 0; a < N; a++)
  37. {
  38. for (int b = 0; b < N; b++)
  39. {
  40. ans[winner[a][b]] += A[a] * B[b];
  41. }
  42. }
  43. }
  44. return cache[st] = ans;
  45. }
  46.  
  47. int choose(int n, int k)
  48. {
  49. return (int) (fact[n] / fact[k] / fact[n-k]);
  50. }
  51.  
  52. public long[] waysToWin(String[] wins)
  53. {
  54. N = wins.length;
  55. fact = new long[N+1];
  56. fact[0] = 1;
  57. for (int i = 1; i <= N; i++)
  58. fact[i] = fact[i-1] * i;
  59. nxt = new int[N+1];
  60. chooses = new int[N+1][];
  61. for (int i = 0; i <= N; i++)
  62. chooses[i] = new int[choose(N, i)];
  63. winner = new int[N][N];
  64. for (int i = 0; i < N; i++)
  65. for (int j = 0; j < N; j++)
  66. winner[i][j] = wins[i].charAt(j) == 'Y' ? i : j;
  67. cache = new long[1 << N][];
  68. for (int i = 0; i < (1 << N); i++)
  69. {
  70. int cnt = Integer.bitCount(i);
  71. chooses[cnt][nxt[cnt]++] = i;
  72. }
  73. return f((1 << N) - 1);
  74. }
  75. }
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
Main.java:3: error: class CheeseRolling is public, should be declared in a file named CheeseRolling.java
public class CheeseRolling
       ^
1 error
stdout
Standard output is empty