Statistics

Problem Statement for "BearFair"

Problem Statement

Limak is a grizzly bear. He is big and dreadful. You were chilling in the forest when you suddenly met him. It's very unfortunate for you. He will eat all your cookies unless you can demonstrate your mathematical skills. To test you, Limak is going to give you a puzzle to solve.


It's a well-known fact that Limak, as every bear, owns a set of numbers. You know some information about the set:

  • The elements of the set are distinct positive integers.
  • The number of elements in the set is n. The number n is even.
  • All elements are between 1 and b, inclusive: bears don't know numbers greater than b.
  • The set contains exactly n/2 even elements and exactly n/2 odd elements, because grizzly bears only like sets with this property.


Limak smiles mysteriously and gives you q hints about his set. The hints are numbered 0 through q-1. For each valid i, the hint number i is the following sentence: "If you only look at elements that are between 1 and upTo[i], inclusive, you will find exactly quantity[i] such elements in my set."


In a moment Limak will tell you the actual puzzle, but something doesn't seem right... That smile was very strange. You start to think about a possible reason. Maybe Limak cheated you? Or is he a fair grizzly bear?


You are given the ints n and b. You are also given the int[]s upTo and quantity. Return "fair" (quotes for clarity) if there exists at least one set that has all the required properties and matches all the given hints. Otherwise, return "unfair".

Definition

Class:
BearFair
Method:
isFair
Parameters:
int, int, int[], int[]
Returns:
String
Method signature:
String isFair(int n, int b, int[] upTo, int[] quantity)
(be sure your method is public)

Constraints

  • n will be between 2 and 50, inclusive.
  • n will be even.
  • b will be between n and 1000, inclusive.
  • q will be between 1 and 50, inclusive.
  • upTo will have exactly q elements.
  • quantity will have exactly q elements.
  • Each element in upTo will be between 1 and b, inclusive.
  • Each element in quantity will be between 0 and n, inclusive.

Examples

  1. 4

    6

    {3,6}

    {2,4}

    Returns: "fair"

    Limak is a fair bear. Some sets that match his hints are {1,3,4,6} and {1,2,4,5}.

  2. 4

    6

    {3,6}

    {2,3}

    Returns: "unfair"

    The second hint is that exactly 3 elements are between 1 and 6 (inclusive). But there should be 4 elements in total, all between 1 and 6 (inclusive). In this situation Limak is clearly being unfair, there is no set that matches these hints.

  3. 2

    6

    {1,2,3}

    {1,1,2}

    Returns: "unfair"

    The only set that matches the hints is the set {1,3}. However, this set violates the constraint that the number of odd elements must be n/2.

  4. 50

    1000

    {736,205,264,235,273,40,901,37,900,424,122,517,820,402,669,279,455,921,774,923,107,936,484,171,248, 186,970,231,321,902,606,24,451,585,823,270,361,292,128,521,689,683,270,726,980,652,996,909,196,357}

    {35,9,9,9,9,3,46,3,46,18,7,25,39,18,32,9,20,49,37,49,7,49,24,8,9,8,49,9,12,46,29,2,20,29,39,9,16,11,7,27,33,32,9,34,49,32,50,47,8,16}

    Returns: "fair"

  5. 4

    1000

    {400,600}

    {4,0}

    Returns: "unfair"

  6. 20

    589

    {25,48,18,75,14,20,49,41,54,44,1,62,35,52,8,34,28,80,42,51,77,56,43,60,32,6,26,16,22,66,79,70,12,24,72,73,30,4,58,37,2,59,23,10,64,39,50,74,68,46}

    {2,4,1,7,1,1,5,4,5,4,0,6,2,5,1,2,2,7,4,5,7,5,4,6,2,1,2,1,1,6,7,6,1,2,6,6,2,0,5,2,0,6,2,1,6,4,5,7,6,4}

    Returns: "fair"

  7. 12

    663

    {67,41,6,37,54,68,56,27,25,43,32,31,65,2,19,76,73,74,29,35,58,71,50,48,80,69,17,61,15,45,23,38,78,3,60,39,63,77,5,34,21,12,52,10,8,28,13,46,70,64}

    {6,3,0,3,4,6,6,0,0,3,1,1,6,0,0,8,7,8,1,3,6,7,4,4,8,6,0,6,0,4,0,3,8,0,6,3,6,8,0,3,0,0,4,0,0,1,0,4,7,6}

    Returns: "fair"

  8. 8

    944

    {22,60,16,19,40,10,8,25,17,24,48,35,52,44,49,56,27,46,13,37,55,21,39,42,33,15,38,61,31,11,28,58,34,20,51,30,53}

    {2,6,1,1,5,0,0,3,1,2,5,4,5,5,5,5,3,5,1,4,5,2,5,5,3,1,4,7,3,1,3,5,3,1,5,3,5}

    Returns: "unfair"

  9. 2

    400

    {11,9,15,13}

    {0,0,2,0}

    Returns: "fair"

  10. 4

    321

    {6,12,2,3,9,8,10,5}

    {0,3,0,0,1,0,2,0}

    Returns: "fair"

  11. 12

    979

    {54,49,8,62,20,76,29,68,69,33,57,26,40,75,79,16,11,30,71,70,27,45,35,44,32,42,22,47,73,56,51,78,66,24,14,13,15,34,10,64,58,60,18,4,38,6,53,5,36,65}

    {5,2,0,5,1,9,1,8,8,2,5,1,2,9,9,1,0,1,9,8,1,2,2,2,1,2,1,2,9,5,4,9,8,1,0,0,1,2,0,7,5,5,1,0,2,0,5,0,2,8}

    Returns: "fair"

  12. 6

    954

    {9,54,44,18,12,14,30,50,37,48,16,26,27,40,33,52,7,24,46,29,31,20,35,22,11,39,49,42}

    {0,5,4,1,1,1,3,4,3,4,1,3,3,4,3,4,0,3,4,3,3,1,3,2,0,3,4,4}

    Returns: "fair"

  13. 18

    800

    {11,26,76,33,12,35,74,54,38,77,60,61,79,59,6,46,53,65,9,80,40,29,41,78,10,43,70,50,81,18,31,57,72,64,7,66,16,24,37,27,20,22,19,44,63,68,56,14,48,51}

    {0,2,10,4,0,4,10,7,4,11,8,9,11,8,0,5,6,10,0,11,4,3,5,11,0,5,10,5,11,1,3,8,10,9,0,10,1,2,4,3,2,2,2,5,9,10,7,0,5,6}

    Returns: "fair"

  14. 18

    374

    {73,14,26,16,41,61,6,70,13,36,38,59,2,43,21,37,45,32,15,49,19,47,72,4,66,57,55,64,68,67,63,34,29,22,25,60,9,7,46,51,24,40,58,27,18,35,31,53,3,11}

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

    Returns: "fair"

  15. 16

    417

    {57,78,13,64,49,72,66,26,59,69,41,54,31,52,16,32,17,29,38,22,47,58,24,48,9,61,44,34,43,11,74,18,80,76,68,45,28,51,71,40,37,83,56,7,35,82,14,20,63,81}

    {6,7,0,6,5,7,6,3,6,6,3,6,3,6,0,3,0,3,3,3,4,6,3,5,0,6,4,3,3,0,7,1,9,7,6,4,3,5,6,3,3,9,6,0,3,9,0,1,6,9}

    Returns: "fair"

  16. 14

    434

    {25,14,18,75,77,12,44,50,63,66,69,22,11,28,26,42,46,21,49,47,81,56,16,35,71,33,30,37,23,65,15,36,52,43,58,78,32,64,55,54,61,60,13,19,73,40,10,67,39,80}

    {3,2,2,9,9,1,7,7,7,7,7,3,1,3,3,6,7,3,7,7,9,7,2,3,9,3,3,4,3,7,2,3,7,7,7,9,3,7,7,7,7,7,2,3,9,6,0,7,6,9}

    Returns: "fair"

  17. 8

    954

    {21,23,9,7,3,10,6,24,28,4,18,30,13,16,1,11,17,26,15,2,20,14}

    {6,6,2,2,1,3,2,6,6,2,6,7,3,5,0,3,5,6,4,1,6,4}

    Returns: "unfair"

  18. 14

    842

    {45,40,48,32,39,22,17,29,16,20,7,11,41,46,54,9,36,52,49,19,33,26,44,30,24,28,5,34,6,43,23,18,12,51,56,14,10,37}

    {8,7,8,7,7,5,3,6,3,5,0,0,7,8,11,0,7,9,8,4,7,6,8,7,6,6,0,7,0,7,5,3,1,8,13,1,0,7}

    Returns: "unfair"

  19. 2

    917

    {12,11,9,7}

    {1,0,0,0}

    Returns: "fair"

  20. 16

    586

    {62,73,48,51,20,70,74,78,34,49,13,43,58,79,8,60,76,15,50,17,29,25,44,63,37,55,64,12,30,56,68,53,11,66,23,10,9,18,19,40,21,71,42,46,77,38,32,36,80,27}

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

    Returns: "fair"

  21. 6

    912

    {30,21,26,12,24,20,28,17,19,33,15,31,29,10,27,32,13,16,36,35,22}

    {3,2,2,0,2,2,2,0,2,4,0,4,2,0,2,4,0,0,5,4,2}

    Returns: "fair"

  22. 16

    690

    {6,49,63,29,39,43,4,68,23,56,65,17,52,59,24,22,66,2,11,73,72,15,62,45,20,51,13,32,36,55,18,8,30,37,5,47,40,71,50,10,27,34,26,69,53,58,60,42,64,7}

    {1,5,7,4,5,5,0,8,4,6,8,4,6,6,4,4,8,0,2,9,9,3,6,5,4,6,3,5,5,6,4,1,4,5,1,5,5,9,5,1,4,5,4,9,6,6,6,5,7,1}

    Returns: "fair"

  23. 14

    928

    {56,10,62,9,28,30,70,23,80,46,69,89,72,44,52,43,78,82,84,35,88,68,12,42,74,60,8,18,86,50,54,31,39,21,64,17,36,48,27,66,91,33,15,14,40,20,76,25,58,37}

    {4,0,4,0,1,1,4,1,4,2,4,7,4,2,2,2,4,4,6,2,6,4,0,2,4,4,0,0,6,2,4,1,2,1,4,0,2,2,1,4,7,1,0,0,2,0,4,1,4,2}

    Returns: "fair"

  24. 14

    473

    {10,46,21,66,47,31,48,40,33,38,60,5,29,41,27,59,45,51,35,44,68,17,30,53,9,25,22,23,55,50,14,32,24,26,16,64,11,20,36,12,62,42,18,7,58,56}

    {1,8,1,12,8,4,8,7,4,7,11,0,3,7,3,10,8,9,4,8,14,1,4,9,0,3,2,2,9,9,1,4,3,3,1,11,1,1,5,1,11,8,1,0,10,10}

    Returns: "unfair"

  25. 6

    686

    {21,33,66,11,59,35,67,43,22,5,42,38,75,19,70,47,52,40,69,56,57,55,63,49,31,27,61,30,45,26,15,6,8,73,13,65,3,23,71,76,29,17,24,10,14,53,37,41,50,60}

    {1,1,3,1,3,1,3,2,1,0,2,2,3,1,3,2,3,2,3,3,3,3,3,2,1,1,3,1,2,1,1,1,1,3,1,3,0,1,3,4,1,1,1,1,1,3,1,2,2,3}

    Returns: "fair"

  26. 8

    14

    {1, 4, 5, 8, 9, 11, 12, 13 }

    {0, 2, 2, 4, 4, 6, 7, 7 }

    Returns: "unfair"

  27. 4

    6

    {4, 4 }

    {2, 4 }

    Returns: "unfair"

  28. 4

    8

    {2, 3, 4, 5 }

    {0, 1, 1, 2 }

    Returns: "fair"

  29. 10

    100

    {3, 3 }

    {1, 2 }

    Returns: "unfair"

  30. 6

    10

    {9 }

    {3 }

    Returns: "unfair"

  31. 4

    6

    {3, 6 }

    {2, 3 }

    Returns: "unfair"

  32. 50

    1000

    {645, 663, 758, 38, 860, 724, 742, 530, 779, 317, 36, 191, 843, 289, 107, 41, 943, 265, 649, 447, 806, 891, 730, 371, 351, 7, 102, 394, 549, 630, 624, 85, 955, 757, 841, 967, 377, 932, 309, 945, 440, 627, 324, 538, 539, 119, 83, 930, 542, 834 }

    {27, 27, 37, 1, 40, 35, 37, 24, 38, 10, 1, 6, 40, 8, 2, 1, 47, 7, 27, 18, 38, 42, 37, 14, 13, 0, 2, 16, 26, 27, 27, 2, 47, 37, 40, 49, 14, 46, 10, 47, 18, 27, 11, 24, 25, 2, 2, 46, 25, 40 }

    Returns: "fair"

  33. 4

    6

    {3, 3, 6 }

    {3, 2, 4 }

    Returns: "unfair"

  34. 4

    200

    {1, 1 }

    {0, 1 }

    Returns: "unfair"

  35. 8

    17

    {6, 7, 8, 9, 12, 13, 14, 17 }

    {2, 3, 3, 4, 4, 5, 5, 8 }

    Returns: "unfair"

  36. 2

    2

    {2 }

    {2 }

    Returns: "fair"

  37. 6

    13

    {6, 8, 9, 10, 11, 12, 13 }

    {3, 3, 4, 4, 5, 5, 6 }

    Returns: "fair"

  38. 28

    36

    {24, 33 }

    {8, 16 }

    Returns: "unfair"

  39. 4

    10

    {9 }

    {2 }

    Returns: "unfair"

  40. 2

    10

    {2, 2 }

    {2, 1 }

    Returns: "unfair"

  41. 8

    100

    {3, 4 }

    {0, 2 }

    Returns: "unfair"

  42. 4

    6

    {3, 3, 6 }

    {1, 2, 4 }

    Returns: "unfair"

  43. 28

    93

    {1, 4, 6, 10, 15, 20, 23, 30, 36, 39, 40, 45, 48, 51, 54, 56, 68, 68, 69, 72, 73, 74, 78, 80, 85, 86, 87, 88 }

    {1, 1, 1, 1, 2, 3, 3, 5, 6, 6, 7, 7, 7, 10, 10, 11, 12, 12, 13, 13, 14, 14, 15, 17, 18, 19, 20, 21 }

    Returns: "unfair"

  44. 2

    4

    {1, 2, 3 }

    {1, 1, 1 }

    Returns: "fair"

  45. 8

    10

    {9, 8, 5, 9, 2 }

    {8, 8, 5, 8, 2 }

    Returns: "fair"

  46. 4

    8

    {2 }

    {4 }

    Returns: "unfair"

  47. 2

    10

    {5, 5 }

    {1, 2 }

    Returns: "unfair"

  48. 6

    10

    {4, 5, 6, 7, 8, 9, 10 }

    {3, 3, 4, 4, 5, 5, 6 }

    Returns: "unfair"

  49. 4

    4

    {1 }

    {1 }

    Returns: "fair"

  50. 6

    10

    {3, 4, 7 }

    {3, 3, 6 }

    Returns: "unfair"

  51. 6

    10

    {4, 8, 10 }

    {2, 2, 6 }

    Returns: "unfair"

  52. 4

    10

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

    {1, 1, 2, 2, 3, 4 }

    Returns: "unfair"

  53. 4

    4

    {4 }

    {4 }

    Returns: "fair"

  54. 50

    100

    {2 }

    {2 }

    Returns: "fair"

  55. 10

    20

    {20 }

    {10 }

    Returns: "fair"

  56. 2

    2

    {1 }

    {1 }

    Returns: "fair"

  57. 4

    10

    {1 }

    {1 }

    Returns: "fair"

  58. 10

    1000

    {5, 5 }

    {1, 2 }

    Returns: "unfair"

  59. 4

    4

    {1, 2, 3, 4 }

    {1, 2, 3, 4 }

    Returns: "fair"

  60. 4

    6

    {2, 3 }

    {1, 3 }

    Returns: "unfair"

  61. 4

    20

    {2, 5, 7, 10 }

    {3, 4, 4, 4 }

    Returns: "unfair"

  62. 4

    6

    {5 }

    {3 }

    Returns: "fair"

  63. 4

    10

    {3, 4, 5, 6 }

    {2, 3, 3, 4 }

    Returns: "fair"

  64. 30

    50

    {1, 3 }

    {0, 8 }

    Returns: "unfair"

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: