Statistics

Problem Statement for "HardDequeSort"

Problem Statement

A "deque" is a data structure which allows constant time insertion and removal at both the front and back ends. In this problem, you will be given a int[] data, and asked to sort the numbers contained therein using the following algorithm. For each number x in data, you must do exactly one of the following:

  • 1. Push x onto the front end of an existing deque.
  • 2. Push x onto the back end of an existing deque.
  • 3. Create a new deque with x as its only element.

You must process each number in data in the order they are given. It is not permissible to skip a number temporarily and process it at a later time. It is also not permissible to insert a number into the middle of an existing deque; only front and back insertions are allowed.

Once all the numbers have been processed, if you have created your deques wisely, you should be able to create a single, sorted list by placing the resulting deques on top of each other in an order of your choice. Your method should return the minimum number of deques needed for this to be possible.

Definition

Class:
HardDequeSort
Method:
minDeques
Parameters:
int[]
Returns:
int
Method signature:
int minDeques(int[] data)
(be sure your method is public)

Constraints

  • data will contain between 3 and 50 elements, inclusive.
  • Each element of data will be between -1000 and 1000, inclusive.

Examples

  1. {50, 45, 55, 60, 45, 65, 40, 70, 70, 35, 30, 75}

    Returns: 1

    Only one deque is necessary to sort this list. The first element, 50, starts the deque. For each successive element encountered, if that element is less than 50, push it onto the front of the deque. Otherwise, if it is greater than 50, push it onto the back of the deque. Once all the data has been processed, the deque will contain all the elements and be in sorted order.

  2. {3, 6, 0, 9, 6, 3}

    Returns: 2

    Your algorithm could process the numbers in the following way: Create a new deque d1 = {3}. Create a new deque d2 = {6}. Push 0 onto the front of d1; d1 = {0, 3} Push 9 onto the back of d2; d2 = {6, 9} Push 6 onto the front of d2; d2 = {6, 6, 9} Push 3 onto the front of d2; d2 = {3, 6, 6, 9} We can now combine the deques together by putting d2 after d1, resulting in the sorted list {0, 3, 3, 6, 6, 9}. Two deques were used (and it is impossible to succeed using any less than two), so the method returns 2.

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

    Returns: 5

    The five deques will be {0,1}, {2,3}, {4,5}, {6,7}, and {8,9}. It is impossible to use fewer than five deques and still be able to combine them into a single, sorted list at the end.

  4. {100, 100, 100, -100, -100, -100, -50, -50, -50}

    Returns: 2

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

    Returns: 6

  6. {454,537,7,976,537,908,976,908,-94,454,908,64,454,-731,908,-646,537}

    Returns: 4

  7. {724,724,724,724,724,-471,-471,802,-481,343,65,-471,343,994,994,-806,318}

    Returns: 3

  8. {226,226,226,778,226,226,778,778,-308,-960,12,893,-960,245,608,226,893,88,-988,-988,-248,778,-43,-708,84,-495,-117,-960,-708,-792}

    Returns: 6

  9. {902, 878, 895, 860, 869, 791, 829, 772, 784, 731, 759, 651, 665, 541, 586, 409, 534, 264, 405, 230, 247, 159, 224, 36, 124, -5, 31, -177, -58, -327, -194, -357, -340, -474, -391, -494, -492, -508, -505, -577, -554, -723, -662, -824, -768, -908, -880, -975, -930, -993}

    Returns: 25

  10. {-858, -790, -791, -750, -769, -571, -746, -464, -509, -439, -449, -416, -426, -388, -412, -369, -378, -316, -364, -279, -287, -123, -194, -48, -71, 61, 28, 304, 94, 346, 311, 411, 387, 460, 453, 547, 527, 604, 580, 665, 621, 730, 718, 802, 733, 871, 809, 921, 884, 985}

    Returns: 25

  11. {-790, -791, -750, -769, -571, -746, -464, -509, -439, -449, -416, -426, -388, -412, -369, -378, -316, -364, -279, -287, -123, -194, -48, -71, 61, 28, 304, 94, 346, 311, 411, 387, 460, 453, 547, 527, 604, 580, 665, 621, 730, 718, 802, 733, 871, 809, 921, 884, 985}

    Returns: 24

  12. {860, 869, 791, 829, 772, 784, 731, 759, 651, 665, 541, 586, 409, 534, 264, 405, 230, 247, 159, 224, 36, 124, -5, 31, -177, -58, -327, -194, -357, -340, -474, -391, -494, -492, -508, -505, -577, -554, -723, -662, -824, -768, -908, -880, -975, -930, -993}

    Returns: 23

  13. {902, 878, 895, 860, 869, 791, 829, 772, 784, 731, 759, 651, 665, 541, 586, 409, 534, 264, 405, 230, 247, 159, 224, 36, 124, -5, 31, -177, -58, -327, -194, -357, -340, -474, -391, -494, -492, -508, -505, -577, -554, -723, -662, -824, -768, -908, -880, -975, -930}

    Returns: 25

  14. {902, 878, 895, 860, 869, 791, 829, 772, 784, 731, 759, 651, 665, 541, 586, 409, 534, 264, 405, 230, 247, 159, 224, 36, 124, -5, 31, -177, -58, -327, -194, -357, -340, -474, -391, -494, -492, -508, -505, -577, -554, -723, -662, -824, -768, -908, -880, -975, 930}

    Returns: 24

  15. {-330, -628, -730, 289, -189, -538}

    Returns: 3

  16. {-571, -538, 956, 354, 174, -188, -708, -989}

    Returns: 2

  17. {451, -333, -266, -148, -513, 396, -726, -694}

    Returns: 3

  18. {721, 172, 334}

    Returns: 2

  19. {-263, 983, -45, 880, 558, -393, -20, -419, -87, -466, 115, 37, 393, -529, 138, 303, -444, -296, 190, -641, -883, -249, 122, -950, 974, 240, 227, 100, 266, 434, 240, -913, -968}

    Returns: 11

  20. {832, -73, -386, -648, 228, -3, -878, 734, 927, -83, -570, -783, -84, 918, 182, -503, -166, 526, 62, -147, 246, -749, -169, -522, -280, -969, -650, -327}

    Returns: 8

  21. {334, 351, 959, -631, -57, -326, -147, -168, 4, -627, -939, 632, -455, -764, -650, -894, -62, -417, 543, 668, -918, -294, 644, -460, -546, 94}

    Returns: 10

  22. {-604, -441, 270, 773, 87, -898, -997, 115, -278, -700, -135, -98, -954, -126, -567, -471, -404, 427, 648, -968, 794, -6, 143, -532, -490, 193, -526, -231, 743, 49, -850, -964, -578, 152, 867, -74, 764, -535, -197}

    Returns: 13

  23. {-331, 950, 957, 236, 83, 578, 66, -455, 94, -835, -878, -116, -108, -207, 29, 475, -853, -954, -880, 160, 428, -405, 897}

    Returns: 9

  24. {697, -704, 915, 182, -724, 146, 180, -273, -436, 976, 993, 732, 387, -267, 360, 540, -724, 747, -365, -584, -689, 553, -718, 642, -459}

    Returns: 10

  25. {-583, 693, 410, -153, -243, 13, -318, -949, 917, -32, -973, 873, 381, 494, -449, -612, 148, -442, 638, -271, 831, 903, 409, 306, -282, -275, 447, 872, -751, -485, -388, 941, 328, -262, 833, -160, 311, 200}

    Returns: 15

  26. {679, 549, 912, 399, 593, -477, -609, -662, 901, 468, -992, 231, -327, 235, -372, -372, -545, -6, -308, 939, 438, 552, 20, 380, -431, 366, 461, 850, 677, -229}

    Returns: 10

  27. {884, 66, -476, 68, 998, 427, -86, 214, 626, -970, -445, -81, 427, -739, 98, -318, -104, 986, -13, -570, 614, -438, 253, 113, -996, 490, -564, -886, -524}

    Returns: 10

  28. {685, -270, -175, -9, -170, 874, 218, 422, 983, 14, -798, 377, -507, -974, 524, -846, -235, 945, 942, 254, -687, -463, -398, -751, 773, -525, 888, -561, -241, -772, -943, -590, 807, 981, 608, 931, -11, -47, 383, 50, 253, 655, 419, 82, -706, 233}

    Returns: 15

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

    Returns: 8

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

    Returns: 10

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

    Returns: 10

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

    Returns: 8

  33. {-3, 6, -4, -7, 0, -3, 9, 4, -9, 2, 9, 4, 2, 4, 3, 3, -7, 0, 7, -3, -2, 2, -10, 6, 3, -1, 4, 3, -4, 0, 6, 0, -7, 10, -2, -2, -4, -1, 0, 3}

    Returns: 6

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

    Returns: 10

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

    Returns: 8

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

    Returns: 8

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

    Returns: 9

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

    Returns: 8

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

    Returns: 3

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

    Returns: 3

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

    Returns: 3

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

    Returns: 3

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

    Returns: 3

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

    Returns: 3

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

    Returns: 3

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

    Returns: 3

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

    Returns: 3

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

    Returns: 3

  49. {902, 878, 895, 860, 869, 791, 829, 772, 784, 731, 759, 651, 665, 541, 586, 409, 534, 264, 405, 230, 247, 159, 224, 36, 124, -5, 31, -177, -58, -327, -194, -357, -340, -474, -391, -494, -492, -508, -505, -577, -554, -723, -662, -824, -768, -908, -880, -975, -930, -993}

    Returns: 25

  50. {-858, -790, -791, -750, -769, -571, -746, -464, -509, -439, -449, -416, -426, -388, -412, -369, -378, -316, -364, -279, -287, -123, -194, -48, -71, 61, 28, 304, 94, 346, 311, 411, 387, 460, 453, 547, 527, 604, 580, 665, 621, 730, 718, 802, 733, 871, 809, 921, 884, 985}

    Returns: 25

  51. {-858, -750, -769, -571, -746, -464, -509, -439, -449, -416, -426, -388, -412, -369, -378, -316, -364, -279, -287, -123, -194, -48, -71, 61, 28, 304, 94, 346, 311, 411, 387, 460, 453, 547, 527, 604, 580, 665, 621, 730, 718, 802, 733, 871, 809, 921, 884, 985}

    Returns: 24

  52. {902, 878, 895, 860, 869, 791, 829, 772, 784, 731, 759, 651, 665, 541, 586, 409, 534, 264, 405, 230, 247, 159, 224, 36, 124, -5, 31, -177, -58, -327, -194, -357, -340, -474, -391, -494, -492, -508, -505, -577, -554, -723, -662, -824, -768, -880, -908, -975, -993}

    Returns: 23

  53. {-79, -86, -70, -61, -44, -221, -16, 11, -222, -225, 93, 140, 207, -261, 230, -269, 254, -377, -559, -589, -623, 257, -659, 284, 299, -671, 358, -752, -765, 373, 397, -784, 424, -840, 494, -856, 525, -882, -886, -890, 648, 670, -904, -909, -920, 687, 743, 791, 839, -963}

    Returns: 1

  54. {-672,-883,944,-883,-412,-672,-802,-672,-321,944,944,-802,-883,-321,-354}

    Returns: 3

  55. {433,359,359,876,-642,-960,809,-699,638,319,751,900,22,586,-639,973,-300,22,638,-699,-566,842,-828,-562,881,433,470,-1000,913,-960,-49,913,928,-828,-392,-642,359,470,-362,11,-574,1000,-642,982,778,961,11,614}

    Returns: 14

  56. {23,488,-533,-457,250}

    Returns: 3

  57. {291,-613,511,-918,473,-920,-48,-37,-551,442,550,-902,-412,937,558,511,545,-920,718,-197,777,-918,-1000,136,-551,-309,1000,718,-218,230,-138,-48,-613,-37,-412,291,-640,-551,-309,-218,563,373,373,-269,136,1000,-269,563,718}

    Returns: 12

  58. {-793,930,64,868,204,930,64,-615,271,-282,773,187,208}

    Returns: 5

  59. {407,-607,-607,607,407,863,296,848,-294,-117,-148,-869,135,-180,53,135,848,391,-641,622,-25,102,841,-419}

    Returns: 8

  60. {-506,-943,-946,-360,-6,6,-668,835,-554,69,871,82,-760,542,-173,-1000,1000,-367,-857,445,204,462,-41,-351,986,110,-544,-610,211,-544,257,-967,-688,-982,-941,633,-857,108,-73,-87,-262,734,50,495}

    Returns: 15

  61. {295,466,466,466,295,295,466,404,-1000,295,295,295,-576,295,-576,295,295,1000,1000,404,466,1000,466,-576}

    Returns: 3

  62. {716,716,-973,-241,716,-241,-241,-241,137,-241,-241,0,-334,-659,-973,-973,-563,137,-973,-241,-522,-241,816,549,-224,816,-511,-241}

    Returns: 4

  63. {172,-766,172,172,172,172,-766,-766}

    Returns: 1

  64. {-818,-497,-57,-717,629,-340,-407,-560,266,-197,-57,-407,-468,-497,-143,415,868,-287,1000,333,868,261,437,860,-1000,646,-287,-407,1000,415,-1000,498}

    Returns: 9

  65. {-395,-37,-433,-120,-220,703,228,1000,-825,-812,966,-177,-1000,-338,999,82,568,-148,-84,28,-968,503,544,-329,-812,937,-162,-1000,657,51,-482,387,729,387,-695,-565,580,-44}

    Returns: 12

  66. {-469,1000,1000,-692,-692,-397,-692,-765,1000,363,-158,1000,363,363,-397,-1000,363,-314,1000,-469,-158,-692,-469,1000,-765,-1000,-397}

    Returns: 5

  67. {-947,-571,-1000,-296,-482,161,287,919,817,520,1000,-350,828,536,-309,-350,-831,-641,-947,-387,-724,-154,-154,-152,-426,449,-152,161,-641,-406,504,817,-571,555,-296,555,253,-615,-406,551,449,-715}

    Returns: 11

  68. {25,941,1000,471,-265,1000,-284,-1000,25,471,-928,471,-265,1000,-1000,1000,941,-265,-265,471,-618,967,-284,471,-742}

    Returns: 5

  69. {362,362,-839,362,-612,-839,-839,-170,913,804,-788,-249,787,913}

    Returns: 4

  70. {797,976,976,976,-105,699,764,376,689,-254,-920,-197,-888,81,-949,756,699,764,745,-920,-90,887,-92,-410,150,392,738,122,392,-216,150,376,-920,9,9,939,376,887,376,-341,-493,-251,-504,742,-619,865}

    Returns: 13

  71. {-471,-471,-471,-471,-471,-471,-471,-471,-471,-471,-471,-471,-471,-471}

    Returns: 1

  72. {16,-522,8,-93,657,994,-785,-21,980,-409,584,-415,-484,-351,-750,312,708,402,-327}

    Returns: 7

  73. {-973,572,-918,114,-910,896,-889,513,1000,829,399,52,-211,372,-284,-717,501,65,126,-1000,896,-624,-510,337,357,-622,822,-143,-452,231,147,-729,-944,966,733,891,-833,-618,-43,896,673,513,191}

    Returns: 13

  74. {-710,-190,-763,1000,563,51,573,-956,-595,-507,345,-595,292,-696,-435,-190,-956,448,532,-956,-1000,-595,-595,-435,1000,448}

    Returns: 6

  75. {-350,295,730,-784,-163,707,756,-942,707,889,611,737,744,564,228,833,-164,-465,-975,572,-371,-673,638,41,707,-91,475,1000,890,647,375,-711,-805,-891,-495,830,-1000,85,-774,158,-902,44,-627,-578,227,728,-392,-774,-740}

    Returns: 16

  76. {-1000,-1000,91,-892,-892,-429,276,590,-792,1000,162,944,91,944,-938,50,876,-39,-464,-890,916,-238,-934,730,752,102,-184,-464}

    Returns: 8

  77. {-1000,643,-1000,-680,255,-680,708,297,-240,257,-240,94,-384,-46,94,-843,227,255,1000,255,-901,-966,1000,-575,-1000,1000,-533,1000,-4,-533,-575,-46,-345,-901,-843,-405,708,-535,255,-345,-240,-680,257,-666,444,643,444,-345,94,257}

    Returns: 12

  78. {-1000,1000,901,-42,901,1000,901,901}

    Returns: 2

  79. {770,-869,770,-183,322,-183,140,770,-869,798,-39,-39,-646,605,142}

    Returns: 5

  80. {227,411,770,107,-949,-826,118,-749,845,155,275,322,266,-664,-400,-444,1000,-622,-614,792,78,-1000,169,-818,-241,407,-885,390,-279,-232,-443,-670}

    Returns: 12

  81. {-835,300,300,643,-835,-561,300,-730,-730,694,-314,-730,-387,228,-98,-566,-788,308,-561,724,-32,-314,435}

    Returns: 6

  82. {-492,-492,-492,-492,-492,-492,-492,-492,-492,996,287,35,112,-210,227,-432,-465,32,-492,-492,-492,-332,114,114,951,-210,996,-465,-492,504,-634}

    Returns: 6

  83. {320,893,659,28,-544,893,-951,711,774,-791}

    Returns: 3

  84. {748,748,174,680,174,174,748,-379,680,680,-656,-379,174,680,-379,482}

    Returns: 3

  85. {177,177,304,-675,304,304,401,304,-675,-203,304,304,407,216,304,262,881,-84,704,-675,-699,-458,-399,179,-886,-458,-699,409,177,454,454,-209,881,-399}

    Returns: 8

  86. {-837,218,218,-837,-837,-837,-837,659,659,611,611,-837,-304,218,-289,-304,346,-304,-121,-861,-837,-837,176,218,-289,783,176,-747,-861,260,659,611,-304,260,-747,-121,-121,-304,611,58,260,659,-747,58}

    Returns: 6

  87. {-234,365,624,287,228,941,-1000,673,-960,-847,-847,228,673,287,165,-300,-599,109,287,673,1000,718,871,-1000,-105,-770,941,358,624,-92,-847,425,-92,-234,-770,158,881,-300,624,350}

    Returns: 8

  88. {249,766,733,-109,-408,-523,990,878,-638,-666,881,71,940,940,-1000,-666,71,-523,-848,-761,-1,406,910,-928,-141,809,-197,-928,-409,-873,733,-718,-693,1000,-96,170,-599,-693,-874,580,659,-523,-408,303,-718}

    Returns: 12

  89. {-685,-685,-685,-685,94,-683,-683,94,226,-683,96}

    Returns: 3

  90. {1000,576,-791,-189,691,710,417,-1000,-757,576,576,691,-791,-1000,-256,691,-189,130,710,-757,-124,-596,-899,-593,-596,-189,-17,-467,268,-1000,320,456,268,-596,157,-899,-596,-1000,320,-443,130,-443}

    Returns: 10

  91. {-69,-69,-69,-69,852,852,-69,-348,688,-69,-141,843,-69,852,-192,477,747,587,-961,-961,758,21,600,688,491,-643}

    Returns: 7

  92. {-1000,123,-160,750,750,750,-160,-160,-535,750,-258,-1000,-258,750,-1000,-312,-312,123,-160,-160,123,1000,1000}

    Returns: 3

  93. {-112,-387,-216,-1000,811,163,-533,-387,-6,-436,1000,163,-1000,-436,568,-387,-984,163,-155,-216,-785,810,234,810,-387,-922,-155,-6,1000,163,-1000,744,811,731,-159,336,-785,811,568,-159}

    Returns: 8

  94. {-625,875,-625,600,875,-559,600,-116,-356,875,-559,875,271,875,875,875,-434,-559,600,-677,271,-322,-434,881,982,271,-116,875,-349,-275,-625,-434,-220,881,-625,-625,413,-538,-116,982,-434,121,-625,-538,-322,-349,-349,-220,-677}

    Returns: 8

  95. {-884,-884,-884,-884,262,52,-623,262,156,690,690,538,52,563,364,690,-404,355,538,673,683,156,355,683,-201,673,262,135,52,355,683,262,878,355,364,-884,52,-201,690,-674,878,878,-135,378}

    Returns: 8

  96. {94,94,94,94,94,94,94,94,-11,-11,644,-11,-11,644,-11,-11,-11,94,644,-11,94,94,94,644,644,644,94,-11,206,206,259,94,206,-778}

    Returns: 3

  97. {44,347,176,733,192,782,-411,465,344,-35,-190,571,118,986,901,672,519,-226,-206,716,544,-62,1000,-1000,-259,150,535,-740,-68,-694,-532,19,966,-106,311,-710,540,745,-242,-497,646,917,142,-694}

    Returns: 14

  98. {-1,-2,0,-3,-2,-1}

    Returns: 2

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

    Returns: 1

  100. {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: 1

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

    Returns: 5

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

    Returns: 13

  103. {-70, -639, -270, 811, 915, -82, 830, 678, -52, 878, -994, 633, -38, 574, -140, -154, 180, -479, -626, 800, -696, 179, 111, -885, -980, 366, -350, 638, -201, 165, 501, -122, -521, 672, -792, 399, -432, -580, 863, 244, 767, -164, -266, -3, -347, 556, -741, -422, -987, 966 }

    Returns: 17

  104. {0, -1, -2, -3, -4, -5, -6, 100, 99, 98, 97, 96, 95, 94, 200, 199, 198, 197, 196, 195, 194, 300, 299, 298, 297, 296, 295, 294, 400, 399, 398, 397, 396, 395, 394, 500, 499, 498, 497, 496, 495, 494, 600, 599, 598, 597, 596, 595, 594, 596 }

    Returns: 8

  105. {1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7 }

    Returns: 4

  106. {454, 537, 7, 976, 537, 908, 976, 908, -94, 454, 908, 64, 454, -731, 908, -646, 537 }

    Returns: 4

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

    Returns: 25

  108. {50, 45, 55, 60, 45, 65, 40, 70, 70, 35, 30, 75 }

    Returns: 1

  109. {914, -235, 704, -448, 174, -275, 368, 20, -29, 240, -877, -394, -546, 276, 737, 425, 573, 470, -673, 695, 898, 256, -832, -281, -442, -101, -241, 152, -250, 937, -654, -121, 738, 127, 386, -324, -774, -655, -154, -64, 881, 680, -221, -207, 573, 710, -461, -517, -310, 159 }

    Returns: 17

  110. {95, 94, 92, 82, 78, 73, 69, 69, 68, 67, 67, 64, 61, 53, 47, 45, 41, 38, 36, 35, 34, 33, 27, 27, 26, 24, 21, 18, 3, 2, 0, 4, 5, 11, 11, 12, 16, 22, 41, 42, 53, 58, 62, 64, 71, 81, 91, 91, 95, 99 }

    Returns: 9

  111. {-289, 261, -448, 282, -468, 411, 491, 971, 163, -95, 123, -230, 776, 722, 127, 123, -856, -629, -9, -275, 203, -139, 88, 524, 7, 648, -979, -228, -788, -248, -661, -529, -511, 782, 692, 783, 486, 948 }

    Returns: 11

  112. {454, 537, 7, 976, 537, 908, 976, 908, -94, 454, 908, 64, 454, -731, 908, -646, 537, 123, 123, 123, 56, 231, 123, 123, 666, 454, 537, 7, 976, 537, 908, 976, 908, -94, 454, 908, 64, 454, -731, 908, -646, 537, 123, 123, 123, 56, 231, 123, 123, 666 }

    Returns: 7

  113. {95, 210, 690, 566, 722, 882, 330, 456, 840, 314, 112, 805, 285, 159, 80, 261, 512, 52, 863, 100, 500, 39, 580, 859, 303, 31, 808, 972, 373, 10, 468, 319, 199, 238, 542, 26, 825, 483, 76, 481, 120, 878, 793, 380, 699, 97, 322, 196, 591, 719 }

    Returns: 18

  114. {2, 3, 2, 1, 2 }

    Returns: 2

  115. {1, 10, 2, 9, 5, 234, 2, 23, 313, 31, 35, 135, 341, 234, 531, 324, 1, 35, 234, 43, 123, 67, 23, 65, 123, 54, 54, 23, 654, 32, 43, 57, 234, 45, 123, 46, 23, 54, 324, 21, 56, 23, 76, 23, 567, 23, 435, 1, 3, 2 }

    Returns: 11

  116. {3, 4, 2, 3, 4, 2, 3, 4, 2 }

    Returns: 2

  117. {3, 6, 0, 9, 6, 3 }

    Returns: 2

  118. {1, 2, 3, 4, 5, 6, 3, 4, 5, 2, 8, 10, 45, 9, 8, 10, 45, 9, 7, 1000, -1000, 1000, 999, -999, 999, -999, 998, 996, 995, 995, 994, 995, 1000, -1000, 982, 384, 283, 381, 192, 281, 291, -122, 198, 291, 312, 1, 0, 1, 0, 2 }

    Returns: 9

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: