Statistics

Problem Statement for "Excavations"

Problem Statement

Once upon a time, there was a civilization called Ruritania. It had n building sites numbered from 0 to n-1. There were various types of buildings such as libraries, markets, and palaces. Each building type was assigned an integer from 1 to 50. The building at site i (0-based index) was of type kind[i].

With the passing of millennia, Ruritania declined and its building sites were covered in sand, concealing all the buildings. Due to wind and terrain, the depth of the sand varied. The building at site i (0-based index) was buried depth[i] meters below the surface.

Recently, an intrepid archeologist excavated K building sites using a machine that could dig to a maximum depth of D meters. Thus, he only discovered buildings that had been buried at most D meters below the surface.

You are given int[]s kind, depth, and found as well as the int K. The types of buildings discovered by the excavation are given by the int[] found, which contains at most one value for each building type even if several buildings of a type were excavated.

Return the number of K-tuples of sites that could have been excavated to arrive at the given values. If the given information is not consistent with any configuration of building sites, return 0.

Definition

Class:
Excavations
Method:
count
Parameters:
int[], int[], int[], int
Returns:
long
Method signature:
long count(int[] kind, int[] depth, int[] found, int K)
(be sure your method is public)

Constraints

  • kind will contain N elements, where N is between 1 and 50, inclusive.
  • Each element of kind will be between 1 and 50, inclusive.
  • depth will contain N elements.
  • Each element of depth will be between 1 and 100,000, inclusive.
  • found will contain between 1 and 50 elements, inclusive.
  • Each element of found will occur in kind at least once.
  • The elements of found will be distinct.
  • K will be between the number of elements in found and N, inclusive.

Examples

  1. {1, 1, 2, 2}

    {10, 15, 10, 20}

    {1}

    2

    Returns: 3

    There are four building sites. Two have buildings of type 1 and two have buildings of type 2. The type 1 buildings are at depths 10 and 15. The type 2 buildings are at depths 10 and 20. The archeologist has excavated two sites and discovered only type 1 buildings. He must have excavated one of three possible pairs of sites: Sites 0 and 1. The archeologist's machine excavates to a maximum depth D of at least 10. Sites 0 and 3. The machine excavates to a maximum depth D that falls in the interval [10, 20). Sites 1 and 3. The machine excavates to a maximum depth that falls in the interval [15, 20). The other pairs of sites could not have been excavated. For example, the archeologist could not have excavated sites 0 and 2, because he would have found either none or both of the buildings.

  2. {1, 1, 2, 2}

    {10, 15, 10, 20}

    {1, 2}

    2

    Returns: 4

    The archeologist could have chosen any pair of sites containing a type 1 and a type 2 building. With a large enough value of D, he could have excavated both.

  3. {1, 2, 3, 4}

    {10, 10, 10, 10}

    {1, 2}

    3

    Returns: 0

    The archeologist cannot have excavated three sites, or else he would have found three types of buildings.

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

    {12512, 12859, 125, 1000, 99, 114, 125, 125, 114}

    {1, 2, 3}

    7

    Returns: 35

  5. {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50}

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

    {50}

    18

    Returns: 9075135300

  6. {12}

    {98238}

    {12}

    1

    Returns: 1

  7. {23,7}

    {33148,33148}

    {23}

    1

    Returns: 1

  8. {22,10,22}

    {69298,69298,69298}

    {22}

    2

    Returns: 1

  9. {45,45,45}

    {79398,42833,42833}

    {45}

    2

    Returns: 3

  10. {43,43,43}

    {74548,7971,7971}

    {43}

    2

    Returns: 3

  11. {30,30,12,37,30,24,26}

    {68528,89247,36223,88871,36833,45953,39033}

    {24,30}

    2

    Returns: 3

  12. {25,15,12,49,26}

    {78984,58041,48528,62838,48528}

    {25,15}

    2

    Returns: 1

  13. {41,40,5,46,40,47,40,45,16,6,40}

    {41121,80964,44016,90126,80964,91164,60285,91164,60285,86209,30801}

    {46,47}

    6

    Returns: 0

  14. {6,37,4,1,39,27,44,1,1,12,34,34}

    {98223,43897,85662,94999,60,14004,85662,35057,94999,83297,43897,43897}

    {4,37,1,44,39,27,6,12,34}

    12

    Returns: 1

  15. {43,45,44,43,43,10,2,9,43,45,24,32,22,11,2}

    {11694,13945,22571,13945,96402,46728,46728,30230,18506,25194,96402,61113,46728,13945,32825}

    {11,43}

    13

    Returns: 13

  16. {43,39,21,9,9,45,21,9,5,17,40,6,45,6,41,41,30,40}

    {87263,79380,79380,9451,54796,9451,87263,29935,39221,54796,29935,9451,54796,95916,13510,65823,65823,13510}

    {9,21,6,41,45,5,43,40,39}

    12

    Returns: 440

  17. {26,18,18,18,49,10,26,49,18,27,26,10,31,26,10,28,10,18,18,18,19}

    {62714,92615,26348,422,92615,26348,81820,62780,95399,4666,95399,62686,92615,82157,422,95399,95399,82157,82157,12525,81820}

    {26,10}

    18

    Returns: 0

  18. {31,38,37,29,40,38,40,31,17,17,4,38,40,29,5,5,30,37,22,46,46,2,37,46}

    {87596,50842,94053,40221,40221,50070,92367,19883,18685,40221,5084,87596,92367,35628,89435,19883,12427,12427,40221,18685,50842,92367,12427,12491}

    {40,2,31,38,37}

    6

    Returns: 189

  19. {21,31,32,41,28,25,6,6,32,21,3,6,35,25,21,35,49,49,6,6,49,6,32,6,46,41,6,35,25}

    {73547,65249,11502,11919,28061,5700,8979,75087,74217,73547,86653,53735,69214,53735,5700,28061,5700,53735,5700,75087,53735,86653,11502,8979,65249,28061,86653,65249,70601}

    {32,35}

    15

    Returns: 10948

  20. {50,47,13,45,50,32,22,8,28,32,23,21,36,38,36,13,45,21,47,47,50,36,13,32,23,45,21}

    {32334,95485,14709,89094,289,32334,95485,14709,35353,92674,6036,32334,26909,10292,14709,35353,92674,92674,26909,95485,10292,67197,67197,6036,18579,67197,54163}

    {45,36,23,47,22,13,32,50,38,8,21}

    24

    Returns: 252

  21. {33,33,33,50,50,33,48,9,50,50,9,22,50,21,28,21,24,9,48,29,33,9,15,48,9,48,48,50,24,48}

    {88079,99527,59007,16688,58126,71597,58126,66796,59007,66796,59007,16688,67398,99527,71597,78014,16688,2014,67398,71597,58126,71597,88079,66796,58126,58126,99527,42931,16688,62795}

    {24,33,50,9}

    24

    Returns: 2874

  22. {39,48,27,28,12,39,48,12,17,21,21,21,27,13,35,35,8,13,28,12,12,28,48,12,13,28,35,12,11,12,12,8,39}

    {89834,47366,91982,47366,89834,17988,84721,17988,89834,51076,91982,51076,62376,75116,91982,47366,91982,62376,62376,44953,65085,65887,65887,62376,62376,44953,60333,99791,51076,62376,65085,84721,99791}

    {17,13,27,35,48,12,28,39,8,21,11}

    30

    Returns: 4432

  23. {40,33,16,19,7,20,19,24,19,20,40,35,31,43,7,31,35,31,19,40,1,31,20,40,31,35,19,13,7,1,24,7,1,24,2}

    {78943,51137,83152,5381,2270,2270,78943,83152,95437,57465,40469,61797,76043,51137,40469,95437,83152,57785,85436,78943,5381,57785,78978,51137,85436,57785,61797,85436,57465,76043,5381,2270,78943,78943,95437}

    {43,31,7,16,20,40}

    7

    Returns: 2112

  24. {18,3,47,40,47,20,3,33,43,10,43,47,3,47,33,18,3,40,33,47,33,35,10,10,43,40,47,40,47,40,18,15,15,35,3}

    {64194,77986,21359,67619,21359,22878,78267,21359,34650,34650,45007,82232,34650,64194,78267,34650,78267,76559,45007,77986,82232,22878,46150,22878,76559,82232,77986,26782,79777,76559,78267,77986,26782,2645,82232}

    {18,15,33,3,47}

    7

    Returns: 31969

  25. {19,14,4,42,26,17,45,4,3,14,14,32,14,14,42,17,36,14,45,14,4,28,45,3,18,45,18,4,42,26,4,17,17,17,18,36,36,42,26,17,36,26,3}

    {58805,23476,59900,51666,998,31760,95015,58805,998,51666,95015,51666,15830,31175,59900,33277,95015,28140,31175,33277,95015,11608,95015,33277,31175,23476,33277,95015,11608,11608,31175,31175,2262,15830,51666,59900,33277,15830,33277,48024,28140,11608,83872}

    {42,36,26,14}

    40

    Returns: 0

  26. {37,6,11,36,6,49,24,42,38,50,25,25,6,24,41,20,49,6,36,41,38,6,41,36,38,11,29,2,6,49,37,50,36,2,6,41,11,6,24,37,20,20,29}

    {53569,18862,42003,52510,52510,56383,62828,33686,53569,18862,53569,42003,11535,9816,53569,52510,43349,33686,43349,53569,56383,66564,11535,52510,43349,9816,9816,43349,62973,66564,66564,66564,62973,18862,62973,9816,11535,42003,66564,62973,52510,66564,62973}

    {37,41,2,20,24,49,38,36,6,11,29}

    17

    Returns: 3027070016

  27. {30,39,5,5,39,9,27,39,30,13,10,26,25,23,27,27,39,31,26,23,5,20,25,30,47,39,20,23,31,20,23,30,47,10,26,10,23,5,20,39,10,5,5,31,39}

    {94267,9930,2763,69633,85519,9930,38833,95131,95131,65873,12682,38833,85519,33151,12682,85519,2763,85519,94267,69633,2763,38833,38833,38833,95131,33151,33151,65873,94267,69633,18434,38833,76423,2502,95131,12682,94267,85519,38833,69633,94267,94267,69633,95131,18434}

    {5,25,31,10,20,39,9,26,47,30,27,23}

    35

    Returns: 506727059

  28. {26,41,18,11,2,42,27,50,29,7,2,41,35,26,50,7,42,1,7,41,27,1,2,42,11,2,18,27,18,50,2,7,11,41,11,18,1,11,26,1,44,18,42,26,2,27}

    {10136,29157,48163,10136,39317,97531,87858,19160,48163,10136,97531,19160,10136,10136,29157,69986,95259,62397,29157,10136,33546,69986,68554,19160,10136,48163,92435,48163,97531,29157,68554,68554,19160,62397,95259,19160,92435,33546,82878,68554,39317,69986,48163,10136,69986,73910}

    {1,42,26,2,7,35,41,27,44,50,18,11}

    31

    Returns: 71969558319

  29. {28,20,12,3,32,10,15,44,6,26,28,13,32,6,32,40,46,20,12,40,44,16,1,20,6,10,47,3,46,32,3,40,46,16,44,16,15,44,28,46,6,49,32,46,15,32,46,22,49}

    {41754,90476,68478,20985,41754,32886,68478,32886,20985,1472,68478,41754,32886,1472,65942,1472,32886,20985,20985,90476,1472,68478,65942,68478,95324,90476,90476,41754,68478,65942,7674,20985,95324,41754,65942,65942,20985,41754,20985,95324,41754,32886,68478,65942,90476,32886,41754,90476,7674}

    {3,15,40}

    14

    Returns: 3516169412

  30. {35,21,1,14,10,21,7,35,33,2,38,23,44,10,7,34,45,26,22,7,22,2,33,26,21,22,44,26,44,48,22,2,13,1,2,48,34,7,23,35,21,1,44,21,45,2,2,45,23}

    {61630,84340,4971,61630,65825,37712,95965,79401,16836,79401,47793,10582,10582,65825,21555,4971,33635,65825,61630,14439,69364,14439,69350,61630,7909,99058,95223,3,37712,65825,7909,99058,69350,21555,81417,76449,79401,81417,3,55429,3,95965,79401,14439,7909,99058,57034,52087,81417}

    {45,26,1,2,44,22,21,7,35}

    14

    Returns: 615055534

  31. {44,46,16,16,50,13,13,1,13,38,43,46,13,8,43,33,31,44,1,33,50,30,13,38,13,39,44,33,41,13,13,1,13,41,20,16,1,38,50,31,16,1,13,50,49,50,13,13,39}

    {42696,63701,369,185,59767,185,496,39962,89297,68906,3550,85441,53984,39962,80780,89297,25880,53984,59312,91602,93477,78677,369,185,74881,80780,63701,63021,78677,80780,40345,78677,185,53984,63701,45482,63021,85441,59312,25544,74881,53984,3550,89297,54164,25311,34045,496,53984}

    {44,20,8,16,50,41,30,1,38,39,13,33,31}

    29

    Returns: 100288981825

  32. {17,19,30,30,9,30,30,17,9,30,17,9,9,3,30,19,19,3,9,9,30,19,3,19,17,3,30,30,17,3,30,3,9,17,19,9,17,9,19,3,17,30,3,3,9,3,17,3,19}

    {19884,42986,75743,62988,16858,75743,49545,84009,23823,75591,38449,76971,69143,42986,49239,88062,76394,84009,19884,62988,83730,25274,65587,84009,23823,76394,20340,88062,83730,32449,48778,88062,20397,75591,84009,32449,75591,75743,69143,48778,21310,83730,65587,32449,84009,21310,83730,84326,32449}

    {19,3,17,30,9}

    30

    Returns: 18847368053502

  33. {11,20,8,11,11,8,11,11,26,11,26,26,26,11,11,8,11,20,20,26,11,26,8,11,20,20,11,11,11,8,11,11,11,20,11,8,8,11,11,11,20,20,11,11,20,8,8,11,8}

    {59048,58210,3892,89371,41734,23609,35605,47889,59048,91880,23609,67931,59048,53443,47889,86370,74912,47889,91880,3892,74166,58210,3892,58210,19237,7867,86370,74878,7867,86370,99846,58210,35605,74878,35605,19237,67931,53443,58210,77188,89371,68027,74166,74166,59048,3892,23609,77188,91880}

    {11,20,26,8}

    30

    Returns: 18814048525589

  34. {11,11,20,46,48,39,20,50,4,9,4,20,49,11,46,11,28,49,20,30,35,4,47,49,16,7,7,4,7,17,47,11,41,18,4,41,50,50,4,47,47,11,47,49,46,30,47,35,33,28}

    {88435,89123,74023,39052,35789,83584,39052,45304,67139,67139,94080,29483,38558,16623,39052,64612,45157,80710,73724,16440,73724,21847,99381,9964,73724,85084,64612,21847,35789,46779,17502,50272,35789,14815,57616,39010,29483,8390,16440,13647,73724,98047,98047,21847,80710,43756,17502,23747,47271,99921}

    {20,17,4,18,41,11,35,9,47,16,28,50,7}

    23

    Returns: 2692612261

  35. {50,16,38,23,8,48,12,39,38,50,2,40,21,28,18,14,28,20,21,40,2,4,47,6,20,36,32,18,6,37,50,22,4,24,20,12,16,20,39,37,47,38,27,25,20,2,42,38,16,20}

    {65700,9269,28294,87257,31024,81530,51757,87511,17366,98244,48504,87257,32905,98244,55361,77855,81501,87257,10497,28385,7204,18544,81530,90489,99478,87511,31594,99478,34225,99478,59377,7204,11273,38965,28748,63473,55524,40860,59377,48504,74318,84358,37000,9269,30239,38900,32422,31594,90489,99478}

    {32,21,37,20,18,47,38,6,40,50,23,28,48,16,22,2,12}

    25

    Returns: 455001288

  36. {5,1,24,48,45,24,15,28,20,16,38,21,21,42,36,33,20,30,34,1,6,15,26,3,1,20,30,30,24,1,6,20,28,43,13,6,26,45,2,21,48,3,45,48,6,38,3,35,45,34}

    {48337,48337,54073,88692,88692,48337,48337,54073,54073,88692,88692,54073,54073,48337,54073,88692,88692,88692,88692,48337,88692,48337,88692,54073,48337,88692,54073,88692,48337,88692,88692,48337,48337,88692,88692,48337,54073,54073,54073,48337,48337,48337,88692,88692,48337,88692,48337,48337,48337,88692}

    {30,36,26,21,20,24,33,35,45,1,48,3,6,28,42,34,43}

    25

    Returns: 3381201552

  37. {34,24,34,34,34,24,24,34,34,24,34,24,34,34,34,24,24,34,24,24,24,34,34,24,34,24,24,24,34,24,34,24,34,34,24,34,24,34,24,24,34,34,34,34,24,24,24,24,24,24}

    {79381,90030,29966,90030,79381,79381,29966,29966,79381,79381,90030,79381,79381,29966,29966,90030,29966,29966,79381,29966,29966,79381,79381,79381,90030,79381,29966,79381,29966,90030,29966,29966,79381,29966,79381,29966,29966,79381,90030,79381,79381,29966,29966,29966,90030,29966,90030,29966,29966,90030}

    {24,34}

    25

    Returns: 126410606437726

  38. {31,39,39,11,39,31,11,11,11,39,39,39,11,31,11,31,11,39,39,39,39,31,11,31,31,31,39,11,31,39,39,39,39,31,39,39,11,31,31,39,31,11,11,31,31,31,39,31,11,31}

    {73898,98054,57242,94422,92000,21812,68681,47494,11225,64568,94422,33808,78425,69893,64499,51144,45739,23584,33808,56397,73898,96904,80104,1701,1593,94422,45739,51144,73899,80104,98054,33808,79157,91554,91554,47494,94422,21812,57242,79510,53825,25806,68681,17802,79157,50679,56397,90319,50679,3319}

    {11,39,31}

    25

    Returns: 126408749852619

  39. {14,13,17,17,42,17,10,42,10,20,38,14,20,17,13,42,20,42,13,14,42,38,42,14,29,29,14,10,13,20,42,42,13,20,17,14,17,29,42,38,13,29,13,14,14,38,10,20,10,38}

    {34259,5035,37511,87768,77600,6788,87768,59120,76122,39554,28095,45094,83543,20725,5035,27587,11886,87768,21833,83543,65946,6788,58626,59120,78565,93867,21229,21229,21229,7877,74728,7877,35503,45094,37511,1526,44315,59120,50025,37511,22548,39191,20025,99333,24338,16123,5035,95071,39191,1526}

    {14,17,38,10,29,42,13,20}

    25

    Returns: 109778040371706

  40. {46,11,46,46,30,11,46,28,32,32,46,11,30,11,11,46,30,30,32,30,11,46,46,28,46,32,11,46,46,28,46,11,46,46,46,30,28,28,28,30,32,32,11,32,46,28,11,30,28,11}

    {85126,89774,89774,6983,85450,85450,26179,85450,83502,74492,83502,6983,86299,83502,72419,53142,97440,6983,6983,23790,89774,28488,68824,85126,94982,83502,58828,89774,68824,68824,63131,26179,86299,83502,68824,94982,83502,6983,89774,89774,53142,26179,58828,63131,28488,94982,94982,85126,83502,94982}

    {11,32,30,28,46}

    25

    Returns: 125278211028100

  41. {42,4,24,23,28,32,15,23,36,42,44,50,42,23,8,24,32,23,28,42,23,23,41,15,48,32,20,39,36,32,50,10,3,36,20,42,23,23,31,15,8,42,47,36,3,20,42,42,23,33}

    {19140,63578,63578,56762,81697,68583,56762,72780,68583,33262,72780,87299,37803,19140,68583,37950,81697,72780,31036,16975,33262,72780,46033,18461,34640,37803,80952,8290,86777,24551,63578,68583,24551,25211,86777,16975,25211,61450,56762,68583,87299,87299,13559,80952,81697,52227,29826,68583,16975,68583}

    {15,23,42,32,39,4,28,47,31,33,44,3,8,24,41,50,10,36,20}

    42

    Returns: 19524004

  42. {49,38,43,3,23,18,43,19,3,49,48,48,48,18,18,48,38,12,38,43,38,43,23,49,19,48,43,48,43,48,19,23,18,3,18,38,38,23,38,12,12,3,18,19,19,43,23,3,38,12}

    {6735,75046,5989,84832,74266,31555,78242,18009,78242,5989,85697,94786,94786,75046,42967,13522,21614,59218,31555,23853,85697,54455,21630,42967,84832,58948,28656,58948,75046,35855,38254,35855,78242,74266,49042,85697,31555,18009,21630,28656,9006,54463,13522,20185,59218,60885,58948,59218,9006,42967}

    {48,23,12,43,3,18,49,19,38}

    42

    Returns: 535137969

  43. {19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19}

    {38826,65269,37021,68172,82353,92443,83296,68172,47557,20626,92705,66631,81645,89128,47722,47443,75516,84456,64462,81645,65825,71671,71671,47443,89128,38565,92443,937,65269,38565,38826,53706,92705,82353,65825,15280,20626,73737,82353,38565,84456,89128,64462,92443,83296,64768,52043,84456,47443,84456}

    {19}

    25

    Returns: 126410606437752

  44. {4,3,3}

    {100000,1,100000}

    {3}

    2

    Returns: 2

  45. {4,3,3}

    {100000,1,100000}

    {4}

    2

    Returns: 0

  46. {1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3}

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

    {1}

    21

    Returns: 129024479

  47. {1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3}

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

    {3}

    21

    Returns: 0

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

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

    {2, 3, 7, 9 }

    19

    Returns: 121173740413

  49. {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }

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

    {50 }

    18

    Returns: 9075135300

  50. {4, 4, 9, 17, 3, 4, 8, 4, 12, 5, 14, 3, 9, 3, 18, 5, 9, 18, 17, 9, 20, 9, 8, 15, 11, 10, 1, 14, 20, 16, 13, 1, 4, 7, 8, 16, 20, 18, 18, 17, 15, 1, 19, 2, 16, 2, 11, 3, 6, 10 }

    {4781, 12727, 91637, 12727, 3710, 82261, 81779, 20732, 14388, 94850, 84144, 72232, 65255, 32465, 49121, 90153, 36992, 27336, 93688, 41371, 13499, 45174, 29811, 63026, 28711, 95098, 28401, 20587, 62213, 64823, 38954, 60667, 52972, 55129, 36849, 1185, 56394, 15994, 51005, 9249, 39656, 29244, 96209, 68755, 3754, 33166, 9074, 63058, 64224, 97770 }

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

    15

    Returns: 3695400

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

    {6, 8, 10, 15, 8, 2, 9, 11, 8, 7, 8, 9, 14, 11, 8, 12, 5, 1, 3, 10, 13, 8, 6, 14, 4, 8, 4, 9, 6, 8, 4, 12, 12, 12, 14, 14, 6, 10, 10, 7, 11, 10, 14, 12, 2, 15, 3, 11, 5, 11 }

    {1, 2, 3, 4, 5 }

    10

    Returns: 5062329

  52. {1, 1, 2, 2 }

    {10, 15, 10, 20 }

    {1 }

    2

    Returns: 3

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

    {25548, 27645, 32663, 32758, 20038, 12860, 8724, 9742, 27530, 779, 12317, 3036, 22191, 1843, 289, 30107, 9041, 8943, 19265, 22649, 27447, 23806, 15891, 6730, 24371, 15351, 15007, 31102, 24394, 3549, 19630, 12624, 24085, 19955, 18757, 11841, 4967, 7377, 13932, 26309, 16945, 32440, 24627, 11324, 5538, 21539, 16119, 2083, 22930, 16542 }

    {3 }

    25

    Returns: 9800705640

  54. {1, 2, 1 }

    {1, 2, 3 }

    {1 }

    3

    Returns: 1

  55. {1, 2, 1 }

    {10, 11, 12 }

    {1 }

    3

    Returns: 1

  56. {10, 9, 39, 47, 31, 19, 42, 6, 10, 38, 34, 42, 1, 37, 21, 22, 50, 35, 35, 50, 39, 39, 18, 44, 34, 22, 18, 15, 17, 2, 50, 7, 4, 9, 10, 3, 36, 44, 38, 4, 1, 19, 47, 32, 49, 8 }

    {32210, 24222, 6423, 27507, 16414, 901, 18763, 17411, 27625, 21549, 27596, 3603, 10292, 9375, 4597, 27349, 19669, 8282, 54, 26419, 6901, 18128, 3729, 24649, 17808, 14311, 22814, 14310, 18936, 20601, 16520, 22799, 6225, 5845, 14990, 3196, 3094, 30524, 29315, 7449, 13459, 20581, 14799, 19590, 28010, 20473 }

    {1, 6, 9, 10, 18, 19, 21, 22, 31, 34, 35, 37, 38, 39, 42, 44, 47, 50 }

    27

    Returns: 6417968

  57. {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 }

    {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 }

    50

    Returns: 1

  58. {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, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25 }

    {34, 137, 28, 116, 44, 136, 37, 143, 50, 122, 13, 128, 41, 110, 14, 127, 41, 127, 23, 137, 12, 119, 18, 130, 33, 131, 13, 124, 18, 136, 30, 103, 23, 109, 20, 118, 44, 107, 12, 143, 30, 124, 22, 120, 35, 138, 49, 125, 16, 121 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }

    33

    Returns: 483780

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

    {48, 45, 13, 8, 38, 10, 24, 42, 30, 29, 17, 36, 41, 43, 39, 7, 41, 43, 15, 49, 47, 6, 41, 30, 21, 1, 7, 2, 44, 49, 30, 24, 35, 5, 7, 41, 17, 27, 32, 9, 45, 40, 27, 24, 38, 39, 19, 33, 30, 42 }

    {1, 3, 5, 7, 9, 10 }

    25

    Returns: 1051805360549

  60. {5, 8, 11, 5, 4, 15, 8, 1, 20, 19, 18, 6, 20, 3, 18, 10, 17, 1, 14, 21, 7, 2, 16, 10, 12, 9, 13, 6, 25, 22, 2, 25, 22, 17, 23, 12, 11, 19, 15, 21, 24, 7, 4, 14, 9, 13, 16, 24, 23, 3 }

    {1, 64239, 42490, 83659, 44559, 96433, 70059, 24869, 55060, 79471, 15444, 90853, 22956, 15809, 15402, 11602, 36307, 91239, 17075, 85433, 79224, 39438, 11881, 3325, 48979, 99122, 69020, 17747, 48008, 34883, 79639, 76330, 97416, 21942, 81361, 89209, 76786, 36780, 15667, 25919, 12148, 5469, 13201, 88532, 100000, 93632, 16410, 61076, 41085, 69908 }

    {4, 11, 22, 16, 13, 10, 9, 24, 12, 8, 5, 19, 17, 20, 14, 2, 15, 21, 23, 25, 18, 3, 7, 6, 1 }

    35

    Returns: 107110727680

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: