ogv

Untitled

ogv
Jan 10th, 2020
208
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.10 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class Main {
  4. private static double solve(int N, int[] a) {
  5. long state = 0;
  6. long[] p = new long[] {1, 300, 300*300, 300*300*300, 300*300*300*300 };
  7. for (int i = 0; i < N; i++) state += p[a[i]];
  8. return solve(N, state, new HashMap<Long, Double>());
  9. }
  10.  
  11. private static double solve(int N, long state, Map<Long, Double> memo) {
  12. if (state == 0) return 1;
  13. if (memo.containsKey(state)) return memo.get(state);
  14.  
  15. long[] count = new long[4];
  16. long temp = state;
  17. for (int i = 0; i < 3; i++) {
  18. count[i] = temp % 300;
  19. temp /= 300;
  20. }
  21.  
  22. double e = 0;
  23. long p = 1;
  24. for (int i = 0; i < 3; i++, p *= 300) {
  25. if (count[i] == 0) continue;
  26.  
  27. e += ((double)N/count[i])*solve(N, state - p, memo);
  28. }
  29. memo.put(state, e);
  30. return e;
  31. }
  32.  
  33. public static double run(Scanner scanner) {
  34. int N = scanner.nextInt();
  35. int[] a = new int[N];
  36. for (int i=0; i < N; i++) a[i] = scanner.nextInt();
  37.  
  38. return solve(N, a);
  39. }
  40.  
  41. public static void main(String[] args) {
  42. try (Scanner scanner = new Scanner(System.in)) {
  43. System.out.println(run(scanner));
  44. }
  45. Tests.run();
  46. }
  47. }
  48.  
  49. class Tests {
  50. public static void run() {
  51. testCase("3\n" +
  52. "1 1 1", 5.5);
  53. testCase("1\n" +
  54. "3", 3);
  55. testCase("2\n" +
  56. "1 2", 4.5);
  57. testCase("10\n" +
  58. "1 3 2 3 3 2 3 2 1 3", 54.48064457488221);
  59.  
  60. System.out.println("DONE");
  61. }
  62.  
  63. private static void testCase(String input, double expected) {
  64. try (Scanner scanner = new Scanner(input)) {
  65. double result = Main.run(scanner);
  66. if (Math.abs(result-expected) > 1e-9) System.out.println("TEST FAILED: was " + result + " expected " + expected + " on input\n" + input);
  67. }
  68. }
  69. }
Advertisement
Add Comment
Please, Sign In to add comment