fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/QvHpbb
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!