Statistics

Problem Statement for "AlienOccupation"

Problem Statement

There are N planets in the galaxy. The planets are numbered from 0 to N-1. Planet number A is the home planet of an aggressive alien race.

The alien race has decided to occupy as much of the galaxy as they can. The occupation will happen according to a pre-determined plan. The great shaman of the alien race has determined the data for the plan: two equally long int[]s X and Y.

The occupation will consist of zero or more years. In each year, the aliens will attack and occupy all planets that can be safely attacked from the planets they already control. The arrays X and Y are used to determine which planets can be safely attacked from where, as follows: If the aliens already control some planet p, they can use it as a home base from which they can safely attack each planet of the form (X[i] * p + Y[i]) modulo N.

Determine three numbers:

  • T = the total number of planets this alien race will eventually control
  • U = the number of years the occupation process will take
  • V = the maximum number of new planets occupied in some year

Return the int[] {T, U, V}.

Definition

Class:
AlienOccupation
Method:
getInfo
Parameters:
int, int, int[], int[]
Returns:
int[]
Method signature:
int[] getInfo(int N, int A, int[] X, int[] Y)
(be sure your method is public)

Notes

  • If no planets ever get occupied (see Example #2), V should be zero.

Constraints

  • N will be between 1 and 1,000,000, inclusive.
  • A will be between 0 and N-1, inclusive.
  • X will have between 1 and 10 elements, inclusive.
  • Y will have the same number of elements as X.
  • Each element of X and Y will be between 0 and N-1, inclusive.

Examples

  1. 7

    4

    {1}

    {1}

    Returns: {7, 6, 1 }

    There are 7 planets, the alien race starts on planet 4. There is only one rule: if you control some planet p, you can safely occupy planet (1*p + 1) modulo 7. The occupation will take six years. In those years, the aliens will occupy one planet each year, in the order 5, 6, 0, 1, 2, 3. In the end all planets will be occupied.

  2. 100

    47

    {2, 14, 14}

    {10, 2, 4}

    Returns: {51, 5, 20 }

    In the end, planet 47 and all even-numbered planets will be occupied. The aliens will occupy three planets during the first year (these are planets 4, 60, and 62), 8 planets during the second year, 20 planets during the third year, 16 planets during the fourth year, and three planets during the last, fifth year of the campaign.

  3. 100

    47

    {1, 11}

    {0, 30}

    Returns: {1, 0, 0 }

    Both formulas tell us the same thing: if we control planet 47, it is safe to occupy planet 47. Thus, there will be no occupation at all.

  4. 123456

    0

    {3, 4, 55555}

    {6, 7, 88888}

    Returns: {123456, 20, 18004 }

    Watch out for integer overflow when computing the values (X[i] * p + Y[i]).

  5. 1000000

    123456

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

    {999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999}

    Returns: {1000000, 999999, 1 }

  6. 1000000

    654321

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

    {999999, 999999, 999999, 999999, 999999, 999999, 999999, 999998, 999999, 999999}

    Returns: {1000000, 500000, 2 }

  7. 230

    23

    {2, 2}

    {0, 0}

    Returns: {5, 4, 1 }

    The two rules these aliens have are identical. So, they will only occupy one planet each year.

  8. 999998

    47

    {2, 4, 6, 8, 10, 12, 14, 16, 18, 3}

    {2, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    Returns: {580009, 80009, 262020 }

  9. 1000000

    47

    {1, 1}

    {1, 500001}

    Returns: {1000000, 500000, 2 }

  10. 999999

    47

    {1, 1}

    {1, 500001}

    Returns: {999999, 333334, 3 }

  11. 368938

    32781

    {290266, 237854, 299258, 180077, 134966, 268668, 202667}

    {205738, 322731, 21447, 219431, 345310, 12404, 53716}

    Returns: {368938, 9, 213221 }

  12. 657

    270

    {559, 9, 323, 581, 437, 235, 243, 535}

    {526, 367, 452, 247, 34, 574, 383, 361}

    Returns: {657, 5, 307 }

  13. 630169

    358522

    {603039, 205503, 250210, 36992, 131595, 350148, 102704, 380463, 606446}

    {402211, 532997, 566365, 265116, 101815, 237982, 351125, 229170, 493910}

    Returns: {630169, 8, 322782 }

  14. 780329

    115496

    {634026, 370198, 707636, 300226, 250591, 582238, 274296}

    {374282, 558560, 592847, 42058, 507454, 327372, 590073}

    Returns: {780329, 9, 334731 }

  15. 817538

    414688

    {765681, 544629, 231669, 635798, 119470}

    {657884, 217145, 398319, 508977, 265435}

    Returns: {817538, 11, 395449 }

  16. 632837

    585150

    {465448, 15928, 178567}

    {573563, 86796, 78228}

    Returns: {632837, 18, 153304 }

  17. 278659

    268034

    {249828, 228386, 191668, 17396, 138943, 271039, 247364, 165147, 11656, 127412}

    {110815, 181384, 226302, 96477, 92629, 246306, 104163, 67044, 51599, 71649}

    Returns: {278659, 7, 181961 }

  18. 765901

    597291

    {553020, 411419, 113335, 279828, 465484, 473}

    {684327, 128320, 434183, 70427, 387185, 21728}

    Returns: {765901, 9, 438879 }

  19. 277084

    21865

    {94990, 268256, 257416}

    {105459, 259362, 276968}

    Returns: {277084, 14, 89717 }

  20. 475625

    295491

    {5236, 364398, 38716, 91814, 438185, 78940, 284921, 177388, 333198, 454604}

    {24476, 460083, 326132, 122946, 373420, 32104, 198563, 64565, 11646, 46446}

    Returns: {475625, 7, 326087 }

  21. 317434

    28254

    {161305, 125366, 280435, 79274, 288320, 303960, 143214, 299281, 42311}

    {295152, 257558, 179681, 291777, 27358, 60080, 216781, 218966, 185463}

    Returns: {317434, 8, 174759 }

  22. 950648

    317521

    {885304, 796629, 513021, 626692, 146435, 66622, 532545, 122753, 947173, 483671}

    {684670, 825079, 475808, 863675, 18746, 455693, 849004, 591323, 547487, 800497}

    Returns: {950648, 8, 526927 }

  23. 69407

    37700

    {65849, 14959, 32128, 46162, 43399, 21878, 60628, 2961}

    {12869, 60223, 60362, 36279, 3117, 24810, 37624, 5359}

    Returns: {69407, 7, 39519 }

  24. 809296

    276049

    {506129, 402342, 71791, 757514, 114331, 546164, 743504, 618656, 628010}

    {500504, 563249, 780489, 379545, 606560, 326838, 432113, 807391, 715974}

    Returns: {809296, 8, 410600 }

  25. 939649

    214821

    {107668, 537281}

    {848427, 319812}

    Returns: {939649, 23, 230201 }

  26. 424757

    174459

    {188807, 57042, 48853, 326330, 390057, 223413, 189021, 26342, 183386}

    {305572, 29609, 205446, 332365, 423154, 140463, 133345, 110420, 151899}

    Returns: {424757, 8, 259634 }

  27. 219370

    121897

    {116718, 203345, 115461, 83218, 176814}

    {14357, 40704, 152118, 125750, 161}

    Returns: {219370, 10, 104194 }

  28. 28861

    13852

    {17046, 14348, 20121, 26694, 28176, 8445, 9632, 3358}

    {9931, 4058, 5562, 13863, 11031, 16303, 13959, 7684}

    Returns: {28861, 7, 14654 }

  29. 527807

    275881

    {24187, 397746, 484259, 188219, 395328, 44875}

    {190457, 190276, 81718, 508511, 430984, 63198}

    Returns: {527807, 9, 267404 }

  30. 235322

    121037

    {156745, 104305, 1170}

    {163694, 36461, 194837}

    Returns: {235322, 14, 81049 }

  31. 76322

    73425

    {98, 50380, 65447, 59653, 48916, 16054, 67010}

    {52492, 13383, 11277, 55088, 53995, 72155, 13665}

    Returns: {76322, 8, 42812 }

  32. 893298

    647272

    {697427, 522784, 498912}

    {460584, 625299, 868905}

    Returns: {510453, 63803, 72213 }

  33. 98278

    51839

    {66274, 42912, 56698, 98163, 25774, 41469, 52050, 9776, 17368}

    {93419, 63913, 43654, 85188, 85105, 13741, 33095, 63630, 12151}

    Returns: {98278, 7, 50616 }

  34. 374506

    15588

    {327524, 42636, 315386, 117565, 270426, 337677, 110510}

    {266232, 135098, 373957, 160733, 262178, 317483, 59631}

    Returns: {374506, 9, 217715 }

  35. 957678

    589462

    {300840}

    {754592}

    Returns: {2281, 2280, 1 }

  36. 185879

    127997

    {106002, 160071, 124272, 1855}

    {154431, 104747, 159659, 61669}

    Returns: {185879, 11, 87812 }

  37. 655694

    581310

    {111898, 354261, 67415, 164705, 618534, 111033}

    {250593, 192127, 83856, 148598, 539994, 176317}

    Returns: {655694, 10, 348049 }

  38. 753698

    173444

    {97191, 132068}

    {617727, 412913}

    Returns: {753698, 23, 177999 }

  39. 904153

    365232

    {434809, 309198}

    {575934, 671651}

    Returns: {904153, 23, 223850 }

  40. 230210

    178019

    {201492, 23619, 168145, 82353, 26716, 9381}

    {52906, 212613, 146561, 35513, 86561, 23827}

    Returns: {230210, 9, 121916 }

  41. 874215

    334840

    {530809, 572481, 600392, 789475, 807200, 713092, 369259}

    {836234, 546647, 544714, 446168, 668835, 460452, 457221}

    Returns: {874215, 9, 405375 }

  42. 709040

    433181

    {23776, 204277, 342291, 51455, 628797, 449342, 106023, 460423}

    {611112, 130057, 100970, 350921, 458390, 61878, 349914, 196581}

    Returns: {709040, 9, 419507 }

  43. 958306

    852729

    {491576, 777452, 543113, 498061, 726411, 541504, 125327}

    {240584, 208255, 657825, 27661, 566148, 517550, 341010}

    Returns: {958306, 9, 475184 }

  44. 964867

    148905

    {811704, 303116, 76117}

    {49243, 782848, 878398}

    Returns: {964867, 15, 341328 }

  45. 948686

    634002

    {46362, 673113, 647375, 894103, 701838}

    {6608, 268626, 361409, 947161, 201562}

    Returns: {948686, 11, 475001 }

  46. 582496

    225505

    {388691, 140100, 212229, 469132, 36216, 316260}

    {314137, 442264, 116177, 443157, 438631, 364384}

    Returns: {582496, 11, 241327 }

  47. 793549

    521959

    {47600, 759226, 592390, 756800, 722937}

    {514634, 240884, 283716, 425228, 61315}

    Returns: {793549, 10, 392311 }

  48. 915071

    25167

    {200005, 802816, 437576, 384656, 545470, 93024, 361917}

    {757665, 909517, 654971, 658079, 355470, 462642, 908049}

    Returns: {915071, 9, 467650 }

  49. 877012

    71071

    {496148, 279766}

    {67482, 170143}

    Returns: {657759, 23, 154693 }

  50. 214672

    59619

    {123900, 207963, 51761, 77781, 1556, 29933, 158469}

    {147958, 213532, 3109, 65825, 139828, 55836, 139540}

    Returns: {214672, 8, 109854 }

  51. 390773

    246945

    {174285, 209958, 20098, 352850}

    {338935, 307482, 217432, 170629}

    Returns: {390773, 12, 152542 }

  52. 850336

    843437

    {361470, 7845, 114596, 21555, 326077, 830212, 50948, 638554, 229296}

    {549703, 641637, 3523, 36609, 581598, 616711, 51650, 402072, 800139}

    Returns: {850336, 8, 439384 }

  53. 486579

    100122

    {145361, 353955}

    {333352, 465123}

    Returns: {324386, 22, 75925 }

  54. 414639

    267499

    {19823, 34218, 159405, 315326, 374506, 163152}

    {27279, 319924, 231603, 242960, 213263, 381955}

    Returns: {414639, 10, 187683 }

  55. 755323

    348771

    {265509, 440844}

    {391642, 102995}

    Returns: {755323, 23, 189012 }

  56. 742713

    395724

    {184990, 310055, 31239, 31959, 603048, 709001, 604808}

    {200684, 132102, 588415, 233626, 90495, 7986, 443484}

    Returns: {742713, 9, 404236 }

  57. 448407

    218241

    {303202, 384590, 66888, 80734, 405356, 378353, 387909}

    {388783, 446758, 196980, 282533, 336271, 241214, 137699}

    Returns: {448407, 9, 256036 }

  58. 671467

    154731

    {41546, 618505}

    {253203, 616320}

    Returns: {671467, 22, 166587 }

  59. 134498

    18482

    {35907}

    {32149}

    Returns: {738, 737, 1 }

  60. 543689

    133465

    {306305, 438637, 511776, 24599, 175536, 152944, 242460, 122980, 158873, 298990}

    {507855, 513856, 482999, 324234, 429622, 471554, 192394, 13414, 448734, 511028}

    Returns: {543689, 7, 372674 }

  61. 513421

    383803

    {180083, 196576, 291359, 158277, 419282, 470465, 161113}

    {206817, 436307, 433987, 197378, 18641, 327018, 400035}

    Returns: {513421, 9, 314139 }

  62. 551914

    281777

    {490069, 411441, 106265}

    {112873, 35596, 385634}

    Returns: {551914, 14, 210917 }

  63. 983418

    669519

    {696090, 710649, 599490, 787888, 154657, 1149}

    {273031, 368304, 167765, 650951, 900982, 41707}

    Returns: {983418, 11, 440880 }

  64. 835603

    432346

    {752035, 339192, 154683, 278571, 268598, 346832, 428601, 689135}

    {116955, 215482, 701481, 185180, 651626, 241712, 295862, 696541}

    Returns: {835603, 8, 536347 }

  65. 257632

    120759

    {89372, 242212, 40913, 248266, 138395, 94620, 29234, 235072, 38399}

    {241466, 46587, 148010, 242511, 59638, 141531, 221504, 149793, 205383}

    Returns: {257632, 8, 146212 }

  66. 553109

    335957

    {215950, 261276, 42782, 383242, 398859, 180289, 514021, 178556, 202693}

    {422190, 56275, 491686, 342660, 78275, 271434, 99863, 145234, 540379}

    Returns: {553109, 8, 302773 }

  67. 784055

    607664

    {286989, 626285, 408413, 116380}

    {267976, 579760, 375079, 125434}

    Returns: {627244, 12, 272306 }

  68. 394100

    195163

    {117957, 152535, 131564, 319082, 354922, 366494, 341104, 168200, 298671}

    {20094, 324164, 108767, 155308, 233857, 170500, 59883, 76680, 310390}

    Returns: {394100, 9, 194001 }

  69. 191967

    68270

    {71824, 24817, 77218, 54526, 9926, 70923}

    {160741, 170560, 56900, 51997, 179032, 129066}

    Returns: {191967, 9, 108915 }

  70. 519257

    40601

    {340286, 12206, 343094, 402115, 495181, 310812, 78592}

    {55798, 465232, 219842, 157809, 484718, 115515, 447183}

    Returns: {519257, 9, 317130 }

  71. 434159

    393794

    {45170, 112310, 336761, 332561}

    {348392, 117183, 287331, 46806}

    Returns: {434159, 12, 164401 }

  72. 582542

    439649

    {330682, 392069, 124513, 95496, 329531}

    {476688, 222149, 123170, 90850, 561846}

    Returns: {582542, 11, 239059 }

  73. 696586

    357211

    {507774, 229565, 62248, 334462, 323389, 397401, 277692, 620657, 62248, 79608}

    {268498, 479435, 528551, 230956, 537835, 535887, 508918, 297158, 333985, 457621}

    Returns: {696586, 8, 439038 }

  74. 541348

    260883

    {344561, 219917, 186089, 198604, 250898, 43523, 30808, 534316, 273193, 309012}

    {208202, 359977, 353079, 528862, 182256, 343702, 390805, 193781, 164830, 517400}

    Returns: {541348, 8, 357635 }

  75. 79203

    4612

    {60845, 58989, 38570, 12313, 64529, 35452, 43749}

    {36998, 28441, 56031, 9892, 33479, 50142, 42409}

    Returns: {79203, 8, 41763 }

  76. 482040

    153057

    {126906, 95622, 190142}

    {120706, 161999, 19015}

    Returns: {39340, 204, 7255 }

  77. 227116

    180975

    {124168, 6462, 93205, 2419, 165242, 74550, 71786, 144936, 108998, 198614}

    {138829, 61883, 119040, 119079, 13868, 215171, 21683, 189012, 34112, 192423}

    Returns: {227116, 7, 142309 }

  78. 421945

    232385

    {129959, 24068, 210620}

    {352689, 237060, 279012}

    Returns: {421945, 16, 114212 }

  79. 549319

    104559

    {27782, 470128, 509073, 169081, 166232, 249961, 288999, 333977, 203070}

    {517025, 533351, 288086, 482113, 267787, 353380, 122188, 231583, 266584}

    Returns: {549319, 8, 301222 }

  80. 822613

    236971

    {819573}

    {144595}

    Returns: {42640, 42639, 1 }

  81. 256418

    180608

    {192903, 187232, 228073, 203755, 22222, 84965, 190934, 143557}

    {193504, 169413, 171874, 252562, 249596, 56639, 84807, 250886}

    Returns: {256418, 8, 139462 }

  82. 657215

    98652

    {543706, 164705, 291493, 378372, 146300}

    {172624, 82558, 193208, 58504, 533882}

    Returns: {657215, 11, 287105 }

  83. 188279

    158298

    {160412, 160915, 26915, 74998, 11002, 84033, 48620, 22656, 117869}

    {72297, 25856, 78235, 51211, 155364, 129744, 163578, 37747, 35719}

    Returns: {188279, 8, 114616 }

  84. 255114

    186569

    {222539, 63038, 159533, 81915, 67330, 176441, 193817, 235490, 253194}

    {119109, 212327, 6891, 81018, 240100, 49413, 195367, 239586, 6667}

    Returns: {255114, 7, 167407 }

  85. 451699

    91372

    {366532, 255283, 98930, 235152, 6738}

    {193742, 333472, 129688, 210465, 265945}

    Returns: {451699, 10, 210885 }

  86. 187765

    46235

    {158076, 13155, 56396}

    {82615, 159902, 105536}

    Returns: {187765, 15, 50464 }

  87. 687272

    314453

    {656185, 97345, 317476, 241252, 45588}

    {587890, 494158, 320908, 247401, 310154}

    Returns: {687272, 11, 298966 }

  88. 873723

    478651

    {185399, 581147, 317468}

    {830251, 482505, 303200}

    Returns: {873723, 15, 294154 }

  89. 305592

    27148

    {19889, 35954, 209551, 297444, 265367}

    {222815, 76737, 198407, 201627, 284602}

    Returns: {305592, 11, 118466 }

  90. 235084

    138955

    {108412, 181333, 116645, 141496, 213258, 232212, 47815, 66192, 105021}

    {83970, 87864, 32674, 99113, 114139, 36845, 23534, 192574, 113677}

    Returns: {235084, 8, 144161 }

  91. 261745

    61781

    {67378}

    {142089}

    Returns: {47580, 47579, 1 }

  92. 857661

    26616

    {415887, 557240, 317591, 747604, 207634, 265915}

    {70958, 711627, 53085, 254704, 183101, 640039}

    Returns: {857661, 10, 466916 }

  93. 369712

    181541

    {358830, 261715}

    {136784, 147118}

    Returns: {185076, 219, 40906 }

  94. 806200

    626555

    {214299, 50279, 273096, 510913, 244087, 696792}

    {114672, 553804, 320510, 193547, 416061, 294832}

    Returns: {806200, 10, 429967 }

  95. 776576

    620476

    {553698, 293878, 168238, 169289}

    {335652, 160677, 291743, 505497}

    Returns: {776576, 12, 359040 }

  96. 103508

    37446

    {19792, 51254, 88402, 28750, 29072}

    {98705, 23345, 11302, 38019, 67742}

    Returns: {103508, 9, 42754 }

  97. 152826

    121931

    {8276, 27941, 145467, 57900, 54349}

    {27866, 51627, 130913, 100468, 79280}

    Returns: {152826, 10, 66437 }

  98. 751415

    267744

    {351711}

    {377880}

    Returns: {3066, 3065, 1 }

  99. 440374

    50694

    {172799, 136346}

    {279608, 437604}

    Returns: {220187, 28, 19923 }

  100. 242996

    152312

    {64473, 176536, 240785}

    {210052, 130356, 144404}

    Returns: {60749, 12, 23264 }

  101. 731972

    662846

    {35769, 175857, 24852, 597012}

    {328981, 238595, 719396, 384607}

    Returns: {731972, 12, 305659 }

  102. 885186

    240198

    {512371, 388487, 211578, 864533}

    {445300, 195492, 486123, 624483}

    Returns: {885186, 13, 349821 }

  103. 644780

    233275

    {426453}

    {488771}

    Returns: {2652, 2651, 1 }

  104. 977215

    243093

    {957916, 802853, 19065, 443297, 648242, 537552, 69143}

    {514438, 202759, 409829, 196627, 759682, 2159, 251216}

    Returns: {977215, 9, 474809 }

  105. 516155

    272523

    {438660}

    {288634}

    Returns: {2791, 2790, 1 }

  106. 982192

    309941

    {329506, 321283, 640757, 733945, 697220, 544275, 743900, 726038}

    {781635, 657278, 529367, 393769, 655047, 233232, 706931, 56487}

    Returns: {982192, 9, 453825 }

  107. 228078

    57281

    {154117, 115615, 130648, 221842, 104839, 142552, 105419, 36687}

    {109733, 93644, 3388, 182552, 137406, 89039, 143063, 194886}

    Returns: {228078, 8, 130135 }

  108. 112245

    100329

    {47429, 109807, 66832, 50569, 34337, 20041, 6920, 28195, 6920, 73799}

    {34305, 90218, 33888, 23101, 49056, 80403, 48969, 30274, 74775, 75866}

    Returns: {112245, 7, 56534 }

  109. 580634

    139773

    {111250, 140885, 376917, 53872}

    {152171, 183087, 409080, 283715}

    Returns: {580634, 12, 237820 }

  110. 547598

    65912

    {161449, 252579, 337840, 476555, 543586, 275424, 98777, 367688, 269022, 9917}

    {292674, 280618, 487517, 489666, 157871, 381149, 141499, 218021, 20664, 102996}

    Returns: {547598, 8, 348162 }

  111. 368957

    32781

    {253981, 208117, 157563, 118090, 235081, 177331, 180019, 18760}

    {191996, 10850, 46998, 287, 121016, 220913, 250789, 4186}

    Returns: {368957, 8, 169491 }

  112. 595158

    448475

    {109060, 240044, 235774, 164724, 202867}

    {111034, 15253, 257334, 171647, 328797}

    Returns: {595158, 11, 246509 }

  113. 630188

    358522

    {113067, 149793, 38529, 46914, 155046, 165273, 143355, 179886, 183933, 6936}

    {24672, 65652, 19257, 71334, 113706, 75414, 99936, 106191, 159837, 49707}

    Returns: {630188, 7, 418271 }

  114. 680344

    237982

    {286460, 617380, 144370, 546120, 462740, 375280, 313230}

    {342870, 467850, 52570, 634310, 409210, 518360, 341100}

    Returns: {340172, 9, 170401 }

  115. 838476

    231669

    {822350, 271430, 497890}

    {636220, 331790, 791040}

    Returns: {419239, 15, 151959 }

  116. 156469

    116362

    {8370, 26883}

    {30825, 39534}

    Returns: {156469, 20, 38338 }

  117. 78248

    34832

    {59913, 45891, 40311, 35127, 57672, 59112, 32112, 26946, 67716, 55971}

    {2439, 44811, 19530, 66294, 47502, 44865, 38106, 69561, 49698, 67050}

    Returns: {78248, 7, 44483 }

  118. 958861

    742586

    {20398, 529326, 222971, 193921, 317422, 396025, 634718}

    {168833, 162099, 431032, 182280, 117327, 90293, 125384}

    Returns: {958861, 9, 457274 }

  119. 553040

    411419

    {52467, 87276, 87}

    {128310, 24060, 81408}

    Returns: {553040, 22, 79130 }

  120. 387205

    10864

    {8199, 27609, 35619, 100596, 96531, 39546}

    {97260, 103863, 89178, 110808, 111540, 1962}

    Returns: {387205, 10, 179637 }

  121. 183649

    39470

    {110860, 15290, 76840, 20060, 124100, 40350, 7270, 29020, 99190, 17650}

    {179520, 100810, 78350, 175270, 49540, 180200, 89500, 26440, 160970, 112300}

    Returns: {183649, 7, 100128 }

  122. 54737

    7510

    {34210, 28970, 24800, 46220, 40070, 48960, 11440, 5200}

    {41600, 9590, 37780, 53480, 37170, 1460, 35600, 46190}

    Returns: {54737, 7, 27490 }

  123. 800517

    69406

    {578259, 592641, 134631, 289152, 415458, 390591}

    {196902, 545652, 26649, 693306, 115821, 542007}

    Returns: {266840, 9, 140429 }

  124. 290252

    285695

    {110136, 37212}

    {162024, 133614}

    Returns: {145127, 20, 34996 }

  125. 42892

    17253

    {27678, 22001, 3920, 6251, 29862, 27370, 20755, 17871, 23625, 11746}

    {5243, 5887, 29379, 17486, 23226, 19075, 20650, 6237, 5341, 24430}

    Returns: {42892, 6, 29658 }

  126. 322833

    4097

    {31745, 26012, 19691, 14756, 29379, 22162, 22498, 2345}

    {23996, 1351, 5873, 35, 15127, 27608, 31346, 518}

    Returns: {46120, 7, 20872 }

  127. 520758

    56059

    {13629, 30002, 29470, 20587, 25354}

    {13874, 1904, 32165, 21455, 41097}

    Returns: {74395, 9, 35859 }

  128. 236319

    44815

    {14133, 18723, 4815, 5862, 19380, 20658, 17919, 22485, 22989, 867}

    {3084, 8205, 2406, 8916, 14211, 9426, 12492, 13272, 19977, 6213}

    Returns: {78774, 6, 49253 }

  129. 850420

    29747

    {35800, 77170, 18040, 68260, 57840, 46910, 39150}

    {42850, 58480, 6570, 79280, 51150, 64790, 42630}

    Returns: {85043, 8, 46655 }

  130. 289600

    19868

    {25690, 8480, 15550}

    {19880, 10360, 24720}

    Returns: {1633, 10, 464 }

  131. 58674

    14545

    {1044, 3360}

    {3852, 4941}

    Returns: {11177, 21, 1366 }

  132. 88020

    4354

    {7488, 5733, 5031, 4383, 7209, 7389, 4014, 3366, 8460, 6993}

    {297, 5598, 2439, 8280, 5931, 5607, 4761, 8694, 6210, 8379}

    Returns: {8966, 6, 4963 }

  133. 742600

    83666

    {2912, 31848, 27696, 45344, 56568, 24112, 23152}

    {61576, 26040, 16760, 12896, 17912, 45088, 69120}

    Returns: {92826, 7, 53961 }

  134. 28336

    4372

    {0, 2672, 500, 1696, 274, 1512, 84, 1082, 170}

    {574, 742, 2094, 2010, 822, 2026, 2162, 1856, 2308}

    Returns: {14168, 7, 7204 }

  135. 182202

    9679

    {4932, 17806, 11086, 1528}

    {7684, 2006, 12410, 4034}

    Returns: {91102, 11, 36622 }

  136. 46452

    4959

    {4488, 2520}

    {1956, 4380}

    Returns: {3872, 23, 448 }

  137. 576656

    35803

    {36888, 32192, 22456}

    {36472, 3416, 7504}

    Returns: {72083, 13, 25572 }

  138. 547430

    23182

    {46220, 40070, 48960, 11440, 5200, 41600}

    {9590, 37780, 53480, 37170, 1460, 35600}

    Returns: {54744, 9, 22708 }

  139. 17354

    4712

    {1028, 232, 1546, 502, 720, 1630, 678, 340, 946}

    {46, 1202, 200, 1374, 940, 942, 566, 1306, 1114}

    Returns: {8677, 6, 4118 }

  140. 660852

    24810

    {3006, 56898, 19404, 39978, 35586, 28287}

    {5040, 53262, 57942, 8037, 64818, 38394}

    Returns: {48953, 9, 17625 }

  141. 1000000

    0

    {1 }

    {1 }

    Returns: {1000000, 999999, 1 }

  142. 999983

    0

    {3, 4, 55555, 11159, 11351, 11489, 11549, 11699, 17, 951581 }

    {6, 7, 88888, 100129, 100151, 100183, 100189, 100193, 100213, 100213 }

    Returns: {999983, 8, 537178 }

  143. 1000000

    999997

    {999999 }

    {999999 }

    Returns: {2, 1, 1 }

  144. 1000000

    4

    {1 }

    {1 }

    Returns: {1000000, 999999, 1 }

  145. 123456

    0

    {3, 4, 55555 }

    {6, 7, 88888 }

    Returns: {123456, 20, 18004 }

  146. 1000000

    5

    {995999, 155111, 255222 }

    {115132, 245521, 552553 }

    Returns: {1000000, 16, 341389 }

  147. 1000000

    0

    {1, 999999 }

    {1, 1 }

    Returns: {1000000, 500001, 2 }

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: