fork(1) download
copy 
  1. import java.awt.Point;
  2. import java.io.BufferedReader;
  3. import java.io.InputStreamReader;
  4. import java.util.HashMap;
  5. import java.util.HashSet;
  6. import java.util.Map;
  7. import java.util.Set;
  8. import java.util.StringTokenizer;
  9.  
  10. /** Google Code Jam 2013, wrong code for round 1B, problem B */
  11. class B {
  12.  
  13.     public static void main(String[] args) throws Exception {
  14.     	init();
  15.  
  16. 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  17. 		int T = Integer.parseInt(br.readLine());
  18. 		String line;
  19. 		StringTokenizer tok;
  20. 		for (int ii = 0; ii < T; ii++) {
  21. 			line = br.readLine();
  22. 			tok = new StringTokenizer(line);
  23. 			int N, X, Y;
  24. 			N = Integer.parseInt(tok.nextToken());
  25. 			X = Integer.parseInt(tok.nextToken());
  26. 			Y = Integer.parseInt(tok.nextToken());
  27. 			System.out.printf("Case #%d: %.9f\n", ii+1, solve(N, X, Y));
  28. 		}
  29. 	}
  30.  
  31. 	static HashMap<Integer, HashMap<Point, Double>> data = new HashMap<>();
  32.  
  33. 	public static void init() {
  34. 		HashMap<Point, Double> n1map = new HashMap<>();
  35. 		n1map.put(new Point(0, 0),  1D);
  36. 		data.put(1, n1map);
  37.  
  38. 		data.put(6, getN6());
  39.  
  40. 		data.put(15, getN15());
  41. 	}
  42.  
  43. 	private static HashMap<Point, Double> getN6() {
  44. 		HashMap<Point, Double> res = new HashMap<>();
  45. 		res.putAll(data.get(1));
  46. 		int x = -2;
  47. 		int y = 0;
  48. 		res.put(new Point(x, y), 1D);
  49. 		for (int i = 0; i < 2; i++) {
  50. 			++x;
  51. 			++y;
  52. 			res.put(new Point(x, y), 1D);
  53. 		}
  54. 		for (int i = 0; i < 2; i++) {
  55. 			++x;
  56. 			--y;
  57. 			res.put(new Point(x, y), 1D);
  58. 		}
  59. 		return res;
  60. 	}
  61.  
  62. 	private static HashMap<Point, Double> getN15() {
  63. 		HashMap<Point, Double> res = new HashMap<>();
  64. 		res.putAll(data.get(6));
  65. 		int x = -4;
  66. 		int y = 0;
  67. 		res.put(new Point(x, y), 1D);
  68. 		for (int i = 0; i < 3; i++) {
  69. 			++x;
  70. 			++y;
  71. 			res.put(new Point(x, y), 1D);
  72. 		}
  73. 		for (int i = 0; i < 3; i++) {
  74. 			++x;
  75. 			--y;
  76. 			res.put(new Point(x, y), 1D);
  77. 		}
  78. 		return res;
  79. 	}
  80.  
  81. 	public static double solve(int N, int X, int Y) {
  82. 		Set<Integer> special = new HashSet<Integer>(); special.add(1); special.add(6); special.add(15);
  83. 		HashMap<Point, Double> map;
  84. 		if (special.contains(N)) {
  85. 			map = data.get(N);
  86. 		} else {
  87. 			if (data.containsKey(N)) {
  88. 				map = data.get(N);
  89. 			} else {
  90. 				if (N > 15) {
  91. 					map = get(15, N - 15, 6);
  92. 				} else if (N > 6 ) {
  93. 					map = get(6, N - 6, 4);
  94. 				} else {
  95. 					map = get(1, N - 1, 2);
  96. 				}
  97. 				data.put(N, map);
  98. 			}
  99. 		}
  100. 		Double res = map.get(new Point(X, Y));
  101. 		return res == null ? 0 : res;
  102. 	}
  103.  
  104. 	private static HashMap<Point, Double> get(int SN, int cnt, int max) {
  105. 		// SN = special N
  106. 		HashMap<Point, Double> res = new HashMap<>();
  107. 		int pos = 0;
  108. 		for (int mask = 0; mask < (1 << cnt); mask++) {
  109. 			int rc = Integer.bitCount(mask);
  110. 			int lc = cnt - rc;
  111. 			if (rc > max || lc > max ) {
  112. 				continue;
  113. 			}
  114. 			++pos;
  115. 			for (int i = 0; i < lc; i++) {
  116. 				Point p = getLeft(SN, i);
  117. 				inc(p, res);
  118. 			}
  119. 			for (int i = 0; i < rc; i++) {
  120. 				Point p = getRight(SN, i);
  121. 				inc(p, res);
  122. 			}
  123. 		}
  124. 		// divide by pos
  125. 		//System.out.printf( "DEBUG: pos=%d\n", pos );
  126. 		for (Point p : res.keySet()) {
  127. 			double prob = res.get(p);
  128. 			res.put(p, prob / pos);
  129. 		}
  130. 		// add special points
  131. 		res.putAll(data.get(SN));
  132. 		return res;
  133. 	}
  134.  
  135. 	private static Point getLeft(int SN, int idx) {
  136. 		int y = 0;
  137. 		int x;
  138. 		switch(SN) {
  139. 		case 1: x = -2; break;
  140. 		case 6: x = -4; break;
  141. 		case 15: x = -6; break;
  142. 		default: throw new IllegalArgumentException("SN=" + SN);
  143. 		}
  144. 		for (int i = 0; i < idx; i++) {
  145. 			++y;
  146. 			++x;
  147. 		}
  148. 		return new Point(x, y);
  149. 	}
  150.  
  151. 	private static Point getRight(int SN, int idx) {
  152. 		int y = 0;
  153. 		int x;
  154. 		switch(SN) {
  155. 		case 1: x = 2; break;
  156. 		case 6: x = 4; break;
  157. 		case 15: x = 6; break;
  158. 		default: throw new IllegalArgumentException("SN=" + SN);
  159. 		}
  160. 		for (int i = 0; i < idx; i++) {
  161. 			++y;
  162. 			--x;
  163. 		}
  164. 		return new Point(x, y);
  165. 	}
  166.  
  167. 	private static void inc(Point p, Map<Point, Double> map) {
  168. 		Double val = map.get(p);
  169. 		if (val == null) val = 0D;
  170. 		map.put(p, val + 1);
  171. 	}
  172.  
  173. }
  174.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
7
1 0 0
1 0 2
3 0 0
3 2 0
3 1 1
4 1 1
4 0 2
stdout
copy 
Case #1: 1.000000000
Case #2: 0.000000000
Case #3: 1.000000000
Case #4: 0.750000000
Case #5: 0.250000000
Case #6: 0.500000000
Case #7: 0.000000000
https://ideone.com/oFM0iU
language:
Java (HotSpot 12)
created:
10 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!