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 divisible by 3.
- All elements are between 1 and b, inclusive: bears don't know numbers greater than b.
- For each r in {0,1,2}, the set contains exactly n/3 elements that give remainder r when divided by 3. (That is, there are n/3 elements divisible by 3, n/3 elements of the form 3k+1, and n/3 elements of the form 3k+2.)
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
Definition
- Class:
- BearFair2
- 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 3 and 48, inclusive.
- n will be divisible by 3.
- 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
3
5
{2,3}
{1,2}
Returns: "fair"
Limak is a fair bear. Some sets that match his hints are {1,3,5} and {2,3,4}.
6
1000
{500,100,950}
{4,3,6}
Returns: "fair"
6
20
{5,19,10}
{0,3,2}
Returns: "unfair"
The second hint is that exactly 3 elements are between 1 and 19 (inclusive). But there should be 6 elements in total, all between 1 and 20 (inclusive). In this situation Limak is clearly being unfair, there is no set that matches these hints.
3
6
{1,2,3,4}
{1,1,1,2}
Returns: "unfair"
The only sets that match the hints are {1,4,5} and {1,4,6}. However, none of them satisfies the constraints about numbers of elements with each reminder.
48
1000
{38,450,202,685,971,661,946,226,901,353,12,937,655,108,31,908,845,908,981,896,296,987,77,790,679, 152,412,492,286,54,214,651,59,189,107,445,728,327,438,523,527,663,825,67,523,400,65,892,587,995}
{1,19,8,32,48,31,48,8,43,13,0,46,30,8,1,45,42,45,48,43,13,48,6,40,32,8,17,20,13,3,8,30,3,8,8,19, 37,13,19,21,21,31,41,4,21,16,4,43,23,48}
Returns: "fair"
3
100
{40,60}
{2,1}
Returns: "unfair"
6
941
{605}
{6}
Returns: "fair"
6
971
{212,830,677,729,481,534}
{6,5,5,5,2,5}
Returns: "unfair"
18
625
{34,26,9,35,30,31,20,43,12,23,39,14,38,28,24,17,40}
{14,13,9,15,13,14,12,17,9,12,16,9,15,13,13,12,16}
Returns: "fair"
9
437
{20,8,100,33,68,73,92,55,31,69,49,57,102,21,52,47,13,86,19,54,38,97,36,95,65,43,44,78,84,63,17,18,35,71,26,11,14,61,56,2,28,58,5,81,40,24,41,89,99,76}
{1,1,2,1,2,2,2,2,1,2,2,2,2,1,2,2,1,2,1,2,2,2,2,2,2,2,2,2,2,2,1,1,1,2,1,1,1,2,2,1,1,2,1,2,2,1,2,2,2,2}
Returns: "fair"
12
914
{61,59,2,9,44,37,1,58,46,15,27,48,40,64,34,42,11,54,4,5,24,57,14,67,51,31,17,21,19,28,26,8}
{10,8,1,3,7,7,1,7,7,4,5,7,7,10,6,7,3,7,1,2,4,7,3,12,7,6,4,4,4,5,4,2}
Returns: "fair"
27
546
{83,77,74,24,71,82,12,36,45,76,91,10,87,49,63,57,15,51,43,37,84,22,68,66,81,33,94,25,21,60,96,27,88,48,16,53,31,54,18,99,41,58,101,23,38,47,80,30,11,90}
{22,21,21,12,21,22,10,15,16,21,24,10,23,16,18,16,10,16,16,15,23,12,21,21,21,14,25,12,11,18,25,12,24,16,11,16,14,16,11,25,16,17,25,12,16,16,21,14,10,24}
Returns: "unfair"
21
581
{55,96,17,16,4,76,56,37,89,12,22,60,64,47,31,27,7,52,63,91,73,88,42,24,102,71,39,29,78,21,1,5,67,50,79,30,83,57,34,13,70,99,3,86,80,44,10,20,93,14}
{11,18,5,4,3,14,11,9,16,4,6,13,13,10,6,6,4,10,13,16,14,15,9,6,18,14,9,6,14,6,1,4,13,10,14,6,15,12,6,4,13,18,3,15,14,9,4,5,18,4}
Returns: "fair"
30
439
{84,85,96,82,90,78,98,25,101,74,17,51,41,52,19,32,60,33,57,44,71,68,29,88,54,21,62,46,42,10,66,14,50,55,79,63,87,93,77,39,47,92,12,35,24,28,38,26}
{23,23,26,23,25,22,26,12,29,19,12,17,15,17,12,13,17,14,17,15,19,18,13,25,17,12,17,15,15,10,18,10,16,17,23,18,25,26,22,15,16,25,10,14,12,12,14,12}
Returns: "unfair"
18
408
{34,20,85,66,71,9,63,48,69,58,82,18,37,26,16,60,25,72,11,52,39,55,44,31,27,46,61,88,49,76,30,81,22,24,74,14,68,41,79,21}
{6,4,16,12,13,3,12,8,13,11,14,4,8,5,4,11,5,13,3,9,8,11,8,6,6,8,12,17,9,13,6,14,5,5,13,4,12,8,14,5}
Returns: "fair"
30
386
{57,51,31,18,70,98,84,55,26,66,59,46,65,38,76,9,34,64,37,14,80,93,12,85,62,41,68,82,7,95,71,29,15,102,30,69,19,99,81,88,23,44,53,56,91,22,49,78,73,21}
{8,7,5,3,9,15,14,7,4,8,8,7,8,7,10,3,6,8,6,3,11,15,3,14,8,7,8,12,3,15,9,4,3,16,5,8,3,15,11,15,4,7,7,8,15,4,7,10,9,3}
Returns: "fair"
48
1000
{1, 21, 41, 61, 81, 101, 121, 141, 161, 181, 201, 221, 241, 261, 281, 301, 321, 341, 361, 381, 401, 421, 441, 461, 481, 501, 521, 541, 561, 581, 601, 621, 641, 661, 681, 701, 721, 741, 761, 781, 801, 821, 841, 861, 881, 901, 921, 941}
{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}
Returns: "fair"
48
1000
{2, 3, 5, 6, 8, 9, 11, 12, 14, 15, 17, 18, 20, 21, 23, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 41, 42, 44, 45, 47, 48, 50, 51, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000}
{0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48}
Returns: "unfair"
48
1000
{2, 3, 5, 6, 8, 9, 11, 12, 14, 15, 17, 18, 20, 21, 23, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 41, 42, 44, 45, 47, 48, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000}
{0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48}
Returns: "fair"
48
1000
{413, 103, 563, 398, 991, 976, 343, 101, 634, 950, 769, 260, 342, 471, 616, 579, 242, 561, 745, 683, 545, 407, 927, 192, 847, 960, 447, 288, 443, 947, 820, 233, 529, 219, 381, 916, 59, 666, 519, 498, 127, 169, 352, 965, 745, 755, 71, 196}
{16, 16, 35, 38, 18, 8, 33, 37, 47, 47, 15, 47, 33, 13, 40, 42, 10, 22, 22, 7, 21, 15, 45, 26, 30, 16, 1, 41, 34, 27, 11, 42, 40, 18, 23, 34, 24, 17, 25, 7, 13, 1, 21, 25, 4, 20, 47, 42}
Returns: "unfair"
48
1000
{70, 70, 86, 103, 134, 150, 164, 182, 208, 214, 215, 217, 274, 334, 338, 371, 407, 418, 419, 446, 557, 587, 590, 617, 656, 672, 699, 711, 716, 722, 751, 770, 778, 782, 787, 806, 815, 831, 856, 865, 901, 911, 922, 937, 939, 947, 948, 975}
{1, 2, 2, 3, 4, 4, 5, 5, 5, 7, 7, 9, 10, 10, 10, 11, 11, 13, 13, 13, 13, 18, 21, 21, 22, 22, 22, 23, 24, 26, 26, 27, 28, 29, 29, 30, 31, 32, 33, 41, 43, 43, 46, 47, 47, 47, 47, 48}
Returns: "unfair"
48
1000
{73, 120, 120, 152, 237, 317, 380, 389, 401, 451, 532, 583, 626, 761, 764, 798, 831, 861, 887, 936}
{2, 4, 5, 6, 8, 11, 12, 16, 18, 23, 30, 34, 35, 35, 36, 37, 40, 41, 42, 48}
Returns: "unfair"
48
1000
{26, 94, 222, 295, 525, 549, 582, 672, 739, 955}
{3, 6, 7, 14, 25, 31, 33, 34, 38, 45}
Returns: "fair"
48
1000
{906,127,664,942,986,215,204,274,200,898,256,358,814,664,247,731,423,4,485,27,153,44,267,586,131,666,238,353,117,112,64,987,55,632,317,563,438,934,778,165,780,520,806,459,82,821,781,280,148,970}
{41,8,33,44,46,10,10,13,10,41,11,16,38,33,10,35,22,0,25,2,9,2,13,28,8,33,10,16,8,8,3,46,2,31,14,28,22,42,36,9,36,26,37,23,5,38,36,13,9,45}
Returns: "fair"
48
150
{30,108,71,29,40,134,80,18,94,25,66,40,18,43,10,22,22,58,130,45,136,74,20,84,96,103,133,76,122,1,95,10,113,135,116,85,150,150,43,13,39,135,110,141,140,97,60,61,33,43}
{6,34,22,6,11,42,24,4,29,5,21,11,4,13,2,5,5,19,41,13,42,22,4,25,31,33,42,22,40,1,30,2,38,42,39,25,48,48,13,4,11,42,36,46,45,31,19,20,7,13}
Returns: "fair"
21
523
{79,55,100,53,18,71,31,14,61,9,38,102,70,64,69,12,73,95,75,108,36,27,113,47,67,110,41,34,77,22,114,105,94,112,58,88,97,25,81,91,84,56,85,21,28,44,50,15,107,116}
{13,11,16,11,7,13,7,6,11,6,7,16,13,12,12,6,13,16,13,16,7,7,16,8,12,16,7,7,13,7,16,16,16,16,11,16,16,7,13,16,13,11,13,7,7,8,8,6,16,16}
Returns: "fair"
39
586
{96,92,58,25,35,105,67,78,56,49,32,52,86,30,27,71,20,91,9,109,37,93,73,89,44,16,14,84,41,60,102,108,110,62,22,114,39,47,64,19,115,55,69,81,76,95,31,99,11,113}
{30,30,19,9,11,31,23,26,19,15,11,18,29,10,9,23,9,29,8,33,11,30,23,29,14,8,8,29,11,19,31,33,34,21,9,34,11,15,23,8,34,18,23,26,26,30,10,30,8,34}
Returns: "fair"
42
856
{44,41,7,12,50,21,39,82,28,66,87,103,16,74,95,91,68,70,34,58,97,48,27,31,26,88,84,63,99,46,78,49,101,36,75,104,56,60,72,90,9,80,24,19,54,59,52,94,98,15}
{9,9,3,4,10,5,9,16,6,13,16,19,5,14,18,17,14,14,9,10,18,9,5,6,5,17,16,10,19,9,16,9,19,9,14,20,10,10,14,17,3,16,5,5,10,10,10,18,19,4}
Returns: "fair"
18
742
{45,49,69,72,38,80,62,20,60,6,68,77,54,83,85,27,12,57,75,24,26,9,33,17,30,84,36,14,78,7,48,23,29,2,19,51,41,5,65,88,82,42}
{9,11,13,14,8,16,12,3,11,1,12,14,11,16,16,5,2,11,14,3,5,1,6,2,6,16,8,2,14,1,11,3,5,1,2,11,8,1,12,18,16,8}
Returns: "fair"
39
431
{40,23,92,30,104,27,53,58,78,66,50,33,12,39,93,55,74,72,51,89,87,19,42,98,44,75,81,63,71,54,24,17,68,22,84,14,9,47,60,36,101,35,26,29,57,86,102,96,64,106}
{8,7,9,8,9,8,9,9,9,9,9,8,6,8,9,9,9,9,9,9,9,7,8,9,8,9,9,9,9,9,8,7,9,7,9,6,6,8,9,8,9,8,8,8,9,9,9,9,9,9}
Returns: "fair"
42
999
{104,76,82,66,40,35,98,107,103,17,53,73,26,88,112,14,58,47,30,72,19,28,89,85,97,91,109,50,44,37,69,94,61,80,36,24,9,63,68,56,22,48,11,32,87,78,42,100,64,108}
{22,17,19,12,6,6,21,22,21,3,7,14,4,20,22,3,10,7,4,14,3,4,20,19,20,20,22,7,7,6,12,20,10,17,6,3,3,10,12,10,3,7,3,6,19,17,7,21,11,22}
Returns: "fair"
33
458
{83,79,69,30,67,22,20,96,61,15,19,78,50,44,82,93,46,75,92,10,11,99,94,87,35,16,54,9,81,52,48,41,58,40,100,88,64,57,25,72,36,55,86,28,32,56,14,38,95,89}
{5,5,5,5,5,5,5,7,5,5,5,5,5,5,5,7,5,5,7,5,5,7,7,6,5,5,5,5,5,5,5,5,5,5,7,7,5,5,5,5,5,5,6,5,5,5,5,5,7,7}
Returns: "fair"
9
945
{60,34,69,25,11,48,82,59,107,28,76,66,23,77,9,43,30,49,94,88,68,24,95,52,100,103,42,73,32,81,21,36,18,39,38,85,45,56,63,54,14,104,31,15,50,57,98,78,71,91}
{2,2,2,2,1,2,3,2,3,2,2,2,1,2,1,2,2,2,3,3,2,1,3,2,3,3,2,2,2,2,1,2,1,2,2,3,2,2,2,2,1,3,2,1,2,2,3,2,2,3}
Returns: "fair"
39
586
{91,65,63,19,97,96,45,86,101,89,42,79,8,16,10,102,73,24,62,13,38,30,83,106,82,50,95,76,84,57,56,47,40,51,59,22,104,92,78,100,34,54,37,70,68,32,27,71,67,85}
{19,16,16,10,19,19,12,19,20,19,12,17,8,10,8,20,17,11,15,10,12,11,18,20,17,12,19,17,18,15,14,12,12,13,15,11,20,19,17,19,11,14,12,16,16,11,11,17,16,19}
Returns: "fair"
24
496
{33,39,61,49,70,24,79,15,86,72,30,8,54,66,42,58,74,73,10,40,56,21,7,60,12,37,51,59,95,28,46,27,91,88,14,93,98,17,25,19,81,84,16,34,64,57,43,75,67,78}
{5,5,7,5,10,5,10,5,10,10,5,5,5,7,5,6,10,10,5,5,5,5,5,7,5,5,5,6,10,5,5,5,10,10,5,10,10,5,5,5,10,10,5,5,7,6,5,10,7,10}
Returns: "fair"
30
475
{93,100,70,111,76,62,44,35,38,6,20,64,60,72,41,89,12,67,2,106,31,109,82,53,23,8,48,28,86,92,5,96,18,66,26,55,15,75,59,33,51,90,103,97,85,78,79,46,57,11}
{19,19,13,19,13,10,10,7,10,2,6,10,10,13,10,18,4,10,2,19,7,19,14,10,6,2,10,6,15,18,2,19,6,10,6,10,6,13,10,7,10,18,19,19,14,13,14,10,10,4}
Returns: "fair"
45
599
{80,106,48,23,26,30,16,71,74,68,70,87,45,13,89,9,37,101,93,83,88,10,61,66,32,98,27,67,92,75,34,17,65,42,62,57,104,15,54,94,77,86,96,25,40,95,51,99,60,20}
{5,7,4,2,2,2,2,5,5,5,5,5,4,2,5,2,4,5,5,5,5,2,4,5,2,5,2,5,5,5,2,2,5,4,4,4,7,2,4,5,5,5,5,2,4,5,4,5,4,2}
Returns: "fair"
12
483
{26,10,23,47,48,43,44,17,38,40,50,24,27,49,20,28,11,25,19,8,35,14,32,29,13}
{5,4,5,10,10,7,7,5,7,7,11,5,5,10,5,5,4,5,5,4,6,5,6,6,4}
Returns: "fair"
30
345
{80,90,15,59,52,95,45,77,48,24,54,18,87,39,32,42,68,8,6,49,65,20,88,10,28,66,34,75,36,74,83,16,97,17,57,31,85,100,23,12,62,13,41,64,71,86,27,63,93,99}
{12,12,6,8,7,14,7,12,7,7,8,7,12,7,7,7,9,6,6,7,9,7,12,6,7,9,7,12,7,12,12,6,14,6,8,7,12,14,7,6,8,6,7,8,12,12,7,8,14,14}
Returns: "fair"
33
863
{21,68,18,15,48,66,43,61,12,51,57,27,19,24,22,56,58,63,10,30,71,40,37,45,49,34,53,7,32,74}
{11,31,11,8,22,30,21,27,8,22,26,13,11,13,12,25,27,27,8,15,31,18,16,21,22,16,22,6,15,33}
Returns: "fair"
24
449
{22,44,18,49,10,55,43,41,36,52,30,34,15,16,7,19,4,5,25,47,13,31,29,14,3,6,28,38}
{8,19,7,21,3,24,18,17,16,21,12,16,7,7,3,8,1,2,11,21,6,13,12,6,1,2,11,16}
Returns: "fair"
45
697
{107,37,57,66,94,10,28,91,112,110,31,115,69,16,58,78,63,19,21,97,84,44,48,72,81,90,26,13,60,38,105,27,23,101,98,70,83,41,46,82,14,87,50,52,104,7,54,34,75,59}
{32,13,17,18,30,3,9,27,33,33,9,33,18,3,17,24,18,3,5,30,25,15,15,21,24,27,8,3,18,13,32,8,5,30,30,19,24,13,15,24,3,25,15,17,32,1,17,10,21,17}
Returns: "fair"
21
412
{68,4,71,83,14,77,81,34,101,65,61,7,22,26,94,54,16,27,64,74,39,78,23,45,15,33,38,57,11,58,30,37,50,42,48,86,70,91,9,73,88,29,80,19,96,72,103,13,98,51}
{5,4,5,5,4,5,5,5,7,5,5,4,4,4,7,5,4,5,5,5,5,5,4,5,4,5,5,5,4,5,5,5,5,5,5,5,5,5,4,5,5,5,5,4,7,5,7,4,7,5}
Returns: "fair"
36
502
{27,106,102,49,16,82,53,42,90,6,75,98,101,92,69,56,79,22,19,84,46,52,38,64,4,30,71,36,21,65,104,54,87,61,59,96,93,24,13,68,33,8,73,41,29,78,11,67,45,10}
{4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4}
Returns: "fair"
36
922
{19,16,94,41,24,86,56,33,81,93,100,79,28,59,44,21,69,31,47,10,55,89,37,99,75,102,70,54,83,72,103,67,35,49,92,104,11,61,77,51,14,97,63,26,34,8,36,88,65,39}
{4,4,26,11,7,24,19,9,23,25,27,23,9,19,14,4,20,9,14,1,18,24,11,26,23,27,21,17,23,23,27,19,10,14,25,28,1,19,23,14,2,26,19,9,10,1,11,24,19,11}
Returns: "fair"
6
20
{5, 19, 10 }
{0, 3, 2 }
Returns: "unfair"
48
1000
{38, 450, 202, 685, 971, 661, 946, 226, 901, 353, 12, 937, 655, 108, 31, 908, 845, 908, 981, 896, 296, 987, 77, 790, 679, 152, 412, 492, 286, 54, 214, 651, 59, 189, 107, 445, 728, 327, 438, 523, 527, 663, 825, 67, 523, 400, 65, 892, 587, 995 }
{1, 19, 8, 32, 48, 31, 48, 8, 43, 13, 0, 46, 30, 8, 1, 45, 42, 45, 48, 43, 13, 48, 6, 40, 32, 8, 17, 20, 13, 3, 8, 30, 3, 8, 8, 19, 37, 13, 19, 21, 21, 31, 41, 4, 21, 16, 4, 43, 23, 48 }
Returns: "fair"
3
100
{40, 60 }
{2, 1 }
Returns: "unfair"
3
1000
{9, 100, 300 }
{1, 3, 2 }
Returns: "unfair"