Statistics

Problem Statement for "YetAnotherCardGame"

Problem Statement

Petr and Snuke are playing a cooperative card game. The game is played with special cards: each card is labeled with some positive integer. The integers on cards are not necessarily distinct.

At the beginning of the game Petr is holding some cards in his hand and Snuke is holding all the other cards in his hand. You are given int[]s petr and snuke that describe the state at the beginning of the game: the elements of petr are the numbers on Petr's cards and the elements of snuke are the numbers on Snuke's cards.

During the game the players will place some of their cards onto a pile. Initially, the pile is empty. The players take alternating turns, Petr goes first. In each turn, if the current player has no cards in his hand, the game ends. Otherwise, the player must make exactly one valid move. There are three types of valid moves:
  • If the pile is empty, the player may choose any card and place it onto the pile.
  • If the pile is not empty, the player may choose any card and place it on top of the pile. However, this move is only valid if the number on the new card is strictly greater than the number on the card that was previously on the top of the pile.
  • The player may always choose one of his cards and eat it.

Petr and Snuke have a common goal: they want to create a pile with as many cards as possible. Return the size of the pile at the end of the game, assuming that they cooperate and play the game optimally.

Definition

Class:
YetAnotherCardGame
Method:
maxCards
Parameters:
int[], int[]
Returns:
int
Method signature:
int maxCards(int[] petr, int[] snuke)
(be sure your method is public)

Constraints

  • petr and snuke will contain between 1 and 50 elements, inclusive.
  • petr and snuke will contain the same number of elements.
  • Each element in petr and snuke will be between 1 and 100, inclusive.

Examples

  1. {2, 5}

    {3, 1}

    Returns: 3

    One optimal way is as follows. Petr puts 2 onto the pile. Snuke puts 3 onto the pile. Petr puts 5 onto the pile. Snuke eats 1. The game ends because Petr has no cards in his hand.

  2. {1, 1, 1, 1, 1}

    {1, 1, 1, 1, 1}

    Returns: 1

    The integers on cards are not necessarily distinct.

  3. {1, 4, 6, 7, 3}

    {1, 7, 1, 5, 7}

    Returns: 6

  4. {19, 99, 86, 30, 98, 68, 73, 92, 37, 69, 93, 28, 58, 36, 86, 32, 46, 34, 71, 29}

    {28, 29, 22, 75, 78, 75, 39, 41, 5, 14, 100, 28, 51, 42, 9, 25, 12, 59, 98, 83}

    Returns: 28

  5. {95, 40, 1, 31, 27, 80, 10, 33, 31, 55, 41, 5, 51, 40, 5, 53, 52, 76, 15, 95, 8, 27, 57, 59, 24, 59, 89, 38, 24, 81, 55, 59, 82, 5, 72, 37, 39, 84, 28, 85, 35, 60, 72, 13, 6, 2, 92, 78, 75, 98}

    {41, 43, 23, 18, 36, 48, 85, 85, 35, 60, 46, 40, 89, 25, 39, 34, 32, 24, 23, 9, 84, 70, 50, 59, 95, 74, 70, 21, 21, 87, 87, 59, 29, 85, 89, 42, 41, 78, 57, 16, 89, 73, 39, 86, 89, 67, 37, 14, 10, 74}

    Returns: 61

  6. {57, 17, 98, 50, 1, 8, 43, 87, 2, 90, 42, 78, 97, 55, 47, 53, 43, 47, 10, 89, 76, 96, 91, 28, 99, 59, 11, 100, 13, 63, 86, 38, 2, 87, 95, 72, 48, 7, 40, 71, 96, 26, 10, 79, 38, 33, 61, 20, 94, 63}

    {44, 84, 17, 27, 71, 14, 92, 83, 84, 74, 15, 19, 10, 71, 25, 62, 42, 56, 9, 85, 82, 66, 35, 97, 84, 34, 63, 48, 53, 70, 36, 92, 34, 21, 47, 55, 56, 88, 95, 62, 11, 20, 80, 97, 63, 62, 79, 76, 64, 97}

    Returns: 66

  7. {1, 40, 73, 96, 64, 93, 21, 94, 96, 25, 38, 16, 15, 13, 60, 59, 42, 46, 26, 76, 44, 30, 25, 66, 89, 71, 100, 3, 68, 43, 22, 77, 87, 23, 67, 44, 75, 33, 65, 22, 54, 89, 84, 70, 33, 67, 54, 98, 8, 55}

    {54, 88, 54, 62, 96, 35, 79, 99, 39, 81, 82, 54, 62, 31, 38, 97, 10, 53, 22, 60, 99, 19, 33, 84, 17, 13, 15, 14, 43, 32, 47, 91, 46, 67, 19, 71, 24, 54, 51, 8, 40, 32, 2, 14, 37, 22, 37, 76, 3, 64}

    Returns: 64

  8. {82, 25, 58, 11, 53, 7, 29, 86, 34, 57, 33, 17, 28, 73, 54, 81, 47, 24, 21, 89, 44, 25, 31, 7, 62, 97, 7, 55, 98, 44, 19, 48, 87, 9, 35, 34, 56, 9, 62, 82, 42, 94, 28, 77, 63, 88, 92, 24, 63, 5}

    {56, 59, 96, 35, 60, 14, 89, 24, 3, 89, 44, 21, 26, 62, 31, 1, 16, 87, 6, 78, 69, 44, 56, 28, 55, 87, 7, 9, 39, 55, 100, 26, 21, 74, 5, 70, 78, 33, 34, 93, 13, 91, 97, 4, 67, 15, 11, 81, 17, 91}

    Returns: 60

  9. {94, 46, 49, 83, 18, 50, 33, 42, 99, 62, 20, 39, 4, 7, 14, 31, 58, 28, 54, 78, 33, 54, 89, 23, 3, 51, 44, 80, 49, 85, 67, 8, 43, 6, 75, 57, 1, 84, 32, 41, 8, 22, 14, 100, 24, 32, 100, 10, 50, 39}

    {15, 83, 90, 92, 34, 30, 8, 85, 85, 76, 68, 51, 66, 53, 91, 71, 98, 56, 37, 97, 2, 69, 4, 33, 41, 46, 77, 86, 61, 2, 76, 23, 39, 100, 34, 36, 43, 12, 79, 49, 33, 27, 48, 7, 5, 87, 86, 11, 23, 55}

    Returns: 70

  10. {79, 52, 32, 69, 42, 6, 91, 11, 47, 67, 92, 87, 93, 14, 31, 82, 17, 67, 29, 46, 63, 33, 38, 34, 60, 23, 29, 84, 59, 86, 22, 34, 1, 52, 39, 63, 7, 87, 40, 2, 66, 39, 89, 23, 28, 25, 49, 64, 89, 78}

    {41, 53, 31, 85, 67, 40, 64, 81, 66, 24, 72, 44, 53, 40, 25, 2, 29, 25, 99, 87, 69, 31, 50, 8, 21, 53, 62, 6, 8, 85, 56, 9, 36, 55, 95, 16, 41, 23, 30, 65, 4, 6, 24, 25, 14, 86, 62, 53, 17, 62}

    Returns: 62

  11. {96, 1, 46, 64, 41, 64, 2, 78, 98, 36, 70, 4, 79, 56, 20, 50, 44, 42, 68, 12, 95, 35, 17, 9, 19, 15, 54, 25, 88, 21, 67, 91, 49, 54, 7, 93, 98, 33, 79, 9, 63, 17, 4, 27, 52, 16, 92, 46, 55, 57}

    {76, 99, 57, 99, 48, 97, 54, 63, 90, 21, 42, 78, 7, 68, 5, 61, 39, 80, 31, 34, 34, 43, 32, 14, 53, 18, 36, 79, 12, 60, 85, 64, 74, 82, 75, 97, 29, 81, 5, 58, 15, 30, 6, 63, 76, 58, 67, 24, 45, 23}

    Returns: 69

  12. {33, 85, 34, 88, 57, 10, 81, 96, 88, 63, 3, 97, 29, 35, 54, 63, 95, 32, 51, 1, 19, 53, 91, 77, 18, 66, 98, 53, 90, 21, 95, 65, 43, 57, 18, 54, 33, 32, 31, 79, 85, 77, 90, 13, 24, 93, 13, 44, 29, 86}

    {44, 66, 21, 92, 75, 82, 20, 2, 44, 14, 54, 62, 1, 85, 96, 69, 80, 93, 7, 20, 70, 47, 58, 16, 53, 54, 69, 15, 10, 26, 35, 53, 27, 62, 3, 29, 14, 89, 52, 39, 79, 71, 14, 12, 88, 36, 36, 74, 85, 76}

    Returns: 61

  13. {3, 14, 54, 100, 56, 94, 6, 98, 48, 35, 43, 64, 71, 53, 97, 59, 63, 18, 37, 23, 25, 83, 75, 47, 65, 77, 43, 93, 44, 42, 85, 53, 5, 75, 36, 87, 18, 10, 53, 62, 88, 16, 22, 21, 28, 74, 74, 36, 11, 84}

    {31, 50, 87, 10, 85, 70, 44, 54, 45, 11, 51, 10, 16, 1, 54, 79, 17, 93, 12, 56, 59, 82, 5, 27, 34, 31, 64, 12, 27, 8, 84, 29, 78, 3, 82, 16, 44, 100, 34, 89, 94, 2, 63, 19, 95, 63, 9, 38, 6, 89}

    Returns: 64

  14. {77, 10, 19, 1, 90, 59, 37, 90, 69, 18, 39, 47, 69, 71, 21, 5, 29, 95, 69, 69, 15, 42, 73, 97, 56, 84, 12, 7, 40, 44, 22, 27, 64, 67, 95, 51, 49, 65, 2, 24, 42, 19, 78, 79, 15, 48, 21, 42, 96, 79}

    {57, 79, 24, 46, 27, 15, 50, 70, 63, 15, 17, 38, 23, 49, 6, 82, 17, 27, 73, 19, 86, 2, 78, 36, 84, 45, 27, 51, 55, 32, 55, 1, 33, 68, 48, 11, 88, 95, 92, 12, 37, 59, 98, 85, 7, 45, 24, 4, 64, 96}

    Returns: 62

  15. {9, 1, 14, 69, 2, 58, 30, 25, 55, 72, 81, 6, 15, 92, 31, 4, 49, 31, 48, 82, 41, 71, 71, 65, 20, 83, 32, 82, 96}

    {2, 13, 74, 80, 89, 37, 52, 55, 7, 79, 29, 96, 54, 55, 46, 69, 7, 88, 16, 72, 33, 97, 27, 73, 91, 99, 82, 3, 11}

    Returns: 42

  16. {50, 3, 1, 77, 47, 72, 71, 95, 29, 53, 88, 73, 96, 29, 94, 99, 20, 46, 82, 55, 14, 92, 28, 25, 36, 57, 59, 87, 47, 73, 20, 33, 94, 23, 42, 6, 73, 49, 19, 69, 64}

    {47, 66, 10, 25, 83, 85, 57, 51, 42, 54, 68, 13, 67, 28, 70, 22, 51, 62, 85, 68, 88, 81, 52, 70, 100, 72, 90, 62, 34, 51, 47, 85, 81, 88, 50, 97, 63, 53, 6, 97, 88}

    Returns: 54

  17. {29, 95, 47, 74, 15, 69, 33, 2, 65, 19, 89, 38, 64, 36, 2, 32, 20, 68, 84, 28, 86, 73, 18, 81, 70, 61, 64, 37, 96, 75, 80, 18, 5, 17}

    {62, 33, 62, 71, 9, 27, 81, 58, 94, 26, 52, 60, 91, 52, 39, 91, 50, 46, 83, 80, 83, 79, 40, 64, 69, 37, 76, 97, 73, 27, 23, 28, 38, 87}

    Returns: 48

  18. {2, 98, 13, 40, 36, 74, 32, 99, 55, 8, 86, 22, 44, 59, 64, 21, 78, 74, 84, 76, 82, 98, 89, 13, 8, 33}

    {4, 98, 36, 48, 32, 88, 69, 61, 52, 21, 66, 93, 16, 83, 63, 15, 46, 36, 57, 81, 63, 95, 24, 96, 10, 84}

    Returns: 39

  19. {48, 99, 37, 87, 41, 38, 78, 70, 18, 36, 68, 5, 51, 84, 98, 4, 57, 2, 91, 78, 63, 48, 84, 78, 98, 17}

    {72, 38, 36, 61, 79, 42, 94, 14, 52, 46, 44, 45, 33, 63, 82, 93, 31, 35, 18, 44, 27, 81, 99, 46, 63, 98}

    Returns: 36

  20. {83, 48, 55, 84, 71, 39, 79, 70, 89, 1, 98, 24, 35, 52, 63, 1, 89, 56, 100, 92, 17, 94, 26}

    {75, 16, 56, 91, 22, 54, 8, 87, 6, 42, 12, 44, 51, 84, 81, 79, 97, 97, 89, 56, 66, 43, 45}

    Returns: 35

  21. {24, 79, 34, 81, 54, 44, 85, 13, 71, 50, 81, 36, 100, 25, 68, 75, 27, 97, 64, 74, 32, 25, 61, 53, 33, 12, 88, 55, 87, 80, 64, 86, 38}

    {48, 11, 85, 45, 9, 4, 21, 58, 77, 73, 6, 53, 55, 48, 81, 89, 15, 87, 55, 14, 75, 82, 2, 47, 30, 67, 67, 5, 27, 46, 8, 91, 74}

    Returns: 44

  22. {26, 17, 41, 81, 3, 44, 7, 3, 99, 21, 24, 79, 54, 61, 74}

    {16, 93, 70, 33, 83, 4, 94, 91, 24, 66, 15, 37, 87, 58, 64}

    Returns: 22

  23. {30, 82, 59, 94, 79, 61, 90, 76, 57, 58, 83, 76, 70, 15, 27, 46, 10, 53, 67, 30, 67, 55, 10, 8, 22, 92, 67, 55}

    {56, 11, 79, 100, 88, 58, 64, 80, 65, 13, 65, 75, 8, 76, 90, 65, 56, 54, 88, 11, 45, 11, 10, 84, 25, 65, 43, 59}

    Returns: 36

  24. {31, 52, 36, 41, 100, 27, 54, 35, 10, 53, 20, 14, 97, 34, 4, 51, 12, 27, 57, 14, 38, 21, 17, 45, 3, 37, 53, 90, 79, 9, 59, 49, 59, 53, 37, 1, 98, 14, 30, 2}

    {18, 28, 46, 83, 59, 58, 72, 84, 82, 60, 93, 71, 78, 33, 1, 20, 14, 25, 80, 54, 86, 55, 96, 60, 12, 6, 10, 50, 85, 93, 31, 54, 29, 27, 58, 86, 82, 8, 92, 46}

    Returns: 54

  25. {43}

    {68}

    Returns: 2

  26. {44, 89}

    {44, 8}

    Returns: 2

  27. {72, 38, 95}

    {19, 48, 43}

    Returns: 4

  28. {22, 87, 44, 47}

    {79, 39, 62, 45}

    Returns: 7

  29. {19, 57, 69, 17, 76}

    {5, 7, 1, 89, 86}

    Returns: 6

  30. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 1

  31. {1}

    {1}

    Returns: 1

  32. {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99}

    {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100}

    Returns: 100

  33. {3, 4, 5}

    {1, 2, 6}

    Returns: 4

  34. {1, 3, 5, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 33, 36, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 52, 54, 56, 58, 60, 61, 62, 63 }

    {11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 64, 65, 66 }

    Returns: 43

  35. {2, 3, 4, 6 }

    {1, 3, 5, 6 }

    Returns: 6

  36. {19, 99, 86, 30, 98, 68, 73, 92, 37, 69, 93, 28, 58, 36, 86, 32, 46, 34, 71, 29 }

    {28, 29, 22, 75, 78, 75, 39, 41, 5, 14, 100, 28, 51, 42, 9, 25, 12, 59, 98, 83 }

    Returns: 28

  37. {3, 3 }

    {1, 4 }

    Returns: 3

  38. {9, 9, 9 }

    {6, 7, 8 }

    Returns: 3

  39. {10, 10, 10, 10, 10 }

    {1, 2, 3, 4, 5 }

    Returns: 5

  40. {1, 2, 3, 4 }

    {5, 6, 7, 8 }

    Returns: 5

  41. {1, 7, 5 }

    {1, 6, 8 }

    Returns: 5

  42. {30, 47, 100, 95, 56, 12, 64, 44, 12, 66, 87, 20, 16, 70, 89, 8, 53, 45, 24, 65, 97, 83, 41, 4, 61, 30, 60, 53, 97, 42, 68, 28, 13, 72, 41, 73, 83, 78, 71, 40, 30, 67, 72, 40, 50, 50, 32, 5, 90, 63 }

    {29, 51, 57, 20, 23, 57, 25, 60, 7, 14, 88, 11, 57, 69, 85, 76, 30, 23, 46, 9, 43, 92, 59, 78, 90, 85, 33, 19, 16, 65, 63, 56, 84, 92, 65, 56, 36, 82, 17, 57, 69, 68, 76, 51, 20, 2, 96, 87, 68, 27 }

    Returns: 66

  43. {2, 4 }

    {1, 3 }

    Returns: 3

  44. {10, 10, 10, 10 }

    {1, 2, 3, 4 }

    Returns: 4

  45. {2 }

    {1 }

    Returns: 1

  46. {4, 4, 4, 4 }

    {1, 2, 3, 4 }

    Returns: 4

  47. {100, 100 }

    {1, 1 }

    Returns: 2

  48. {1, 4, 6, 7, 3 }

    {1, 7, 1, 5, 7 }

    Returns: 6

  49. {10, 3, 3, 9, 10, 10, 9 }

    {5, 1, 10, 6, 6, 2, 4 }

    Returns: 8

  50. {77, 19, 45, 77, 41, 69, 55, 62, 67, 65, 23, 21, 58, 2, 4, 32, 50, 21, 4, 78, 34, 35, 32, 20, 53, 63, 3, 26, 22, 34, 45, 77, 54, 64, 67, 31, 20, 45, 75 }

    {55, 70, 32, 60, 42, 50, 16, 44, 54, 45, 45, 34, 19, 62, 50, 4, 32, 9, 12, 31, 28, 50, 23, 28, 55, 20, 41, 27, 51, 53, 24, 52, 32, 28, 62, 54, 63, 44, 76 }

    Returns: 42

  51. {1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 23, 24, 25, 26, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40 }

    {11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60 }

    Returns: 58

  52. {8, 20, 24, 9, 11, 3, 25, 9, 24, 20, 1, 6, 13, 3, 28, 24, 8, 20, 11, 23, 4, 20, 10, 18, 11, 4, 10, 19, 27, 26, 8, 27, 3, 8, 21, 4, 20, 20, 10, 22, 8, 3, 14, 7, 6, 6, 9, 2, 25, 8 }

    {12, 24, 29, 5, 29, 21, 25, 27, 1, 14, 23, 17, 10, 15, 12, 14, 28, 19, 19, 14, 29, 2, 26, 14, 16, 5, 24, 7, 6, 30, 16, 5, 10, 2, 18, 6, 16, 15, 22, 19, 19, 24, 6, 23, 13, 27, 17, 28, 9, 25 }

    Returns: 30

  53. {1, 4, 5, 5 }

    {2, 2, 3, 6 }

    Returns: 6

  54. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

    {91, 92, 93, 94, 95, 96, 97, 98, 99, 100 }

    Returns: 11

  55. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    Returns: 50

  56. {1, 3 }

    {2, 4 }

    Returns: 4

  57. {97, 98, 99, 100 }

    {1, 2, 3, 100 }

    Returns: 5

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: