Advertisement
ogv

Untitled

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