Statistics

Problem Statement for "LibraryWorker"

Problem Statement

You work in a large library. It is the end of the day and you have to replace a number of returned books back on the shelves. The shelves are located at integer positions (positive and negative) along a long corridor and the pile of books is located at position 0. You start off standing at the pile of books (position 0). You can carry at most N books at a time and want to know the minimum total distance that you will have to walk in order to replace all the books.

You are given a int[] books, where each element describes the position of the shelf where a single book must be returned. Return the minimum total distance that you have to walk to replace all the books. You do not need to return to the pile of books after you have finished.

Definition

Class:
LibraryWorker
Method:
replaceBooks
Parameters:
int[], int
Returns:
int
Method signature:
int replaceBooks(int[] books, int N)
(be sure your method is public)

Constraints

  • books will contain between 1 and 50 elements, inclusive.
  • Each element of books will be between -10,000 and 10,000, inclusive.
  • The elements of books will be distinct.
  • No element of books will be 0.
  • N will be between 1 and 50, inclusive.

Examples

  1. {-8472,-8661,1349,-9954,-3528,-7186,-2796,3445,1946,3510,-9183,-4803,5467,9577,3689,6593,316,-8073,-1396,7905,-4563,-7837,-8947,5102,2532,-2522,-9709,-6554,-683,-3559,-7107,-5987,-2777,-485,9092,-6859,2374,-5223,9490,9507,4943,8940,-7052,9007,5744,-5635,-4658,-4956,5537,7698}

    50

    Returns: 29108

  2. {7032,-383,8172,8305,-8932,5381,5492,-5296,3997,-7599,5251,1645,1264,5112,2584,6061,2012,-1263,-7418,8156,-8354,4739,-2282,2696,8755,2468,9306,5219,-3482,-9363,-2564,-859,-9345,-1068,9899,-1744,7181,7045,-6646,7843,88,8430,-1880,2178,-9970,-4262,-3518,-4293,-854,9315}

    33

    Returns: 29768

  3. {5104,6606,-1411,-7829,2459,9568,-6227,1073,2756,5240,-8657,1162,3442,-5098,-1574,-6295,6998,9701,9986,6497,-7716,2432,7467,1542,5107,9472,4526,-2257,5856,-32,8018,7847,6043,7880,-672,-4863,-4263,5878,-7231,-3273,-4564,-8199,-3665,-3942,4313,-1144,7513,1684,-3483,-4942}

    22

    Returns: 32218

  4. {8586,-6262,-2285,-53,-1592,-2045,6431,-9086,-7223,-4808,-159,-2816,-4281,8697,9822,-2890,1887,6383,5563,4600,2136,-1794,-7444,-961,3614,-3956,-6055,-9588,4675,-8719,-4095,-383,-1250,-6986,9863,-21,-3275,-4995,9801,-6626,5982,-9187,-3597,-4518,9809,-9919,8051,173,-1676,2176}

    6

    Returns: 89017

  5. {5311,5165,8537,-6700,5931,-5240,-5686,-3567,-6346,4368,6615,-953,8906,5826,-1401,140,-4453,3858,-2901,5584,9707,8753,1274,-3219,3292,-3752,8804,7194,-35,8751,-4280,9681,-9743,-8770,-7474,-8926,3834,2729,3069,5067,534,1305,-1936,-4062,-1188,-3807,-4198,31,5622,-207}

    16

    Returns: 43695

  6. {-3824,8691,8990,3010,5884,3451,-6499,-1117,2024,-6207,8600,8214,-6123,2712,3046,-2318,213,4809,688,-4345,-9710,-9795,-4848,-7695,-576,-6041,3509,-7471,1179,-4320,7682,9867,3150,-6888,4349,-3767,-2955,5055,-1244,3993,2093,7618,2828,8791,-9233,2485,-5317,5731,-821,-9645}

    3

    Returns: 170723

  7. {8674,-3287,-4073,-1347,9825,-8243,-8275,-9228,6654,3725,-9122,-9105,463,2271,7800,-3591,1117,8257,4326,-7633,-1324,-5319,-5922,-304,-179,1992,-1432,3293,-7034,4780,9171,-3157,280,6997,-1854,5929,3343,-4268,-5498,-1128,-4822,4482,-4276,5868,3639,817,4985,1436,-3779,8286}

    9

    Returns: 58905

  8. {-1153,2252,-1983,6831,-4302,-6243,-7296,-7475,3169,7076,6549,9427,-2246,801,-4417,-3042,-7849,-3852,2929,-8814,2496,-9211,6984,9252,-481,-5110,-5675,5364,2930,-6977,7537,9338,9389,-1206,-2944,6545,-9268,-679,2262,-9764,-6279,-5505,9775,-6841,2422,-4851,7749,2438,9245,3658}

    2

    Returns: 269045

  9. {-8092,8685,-9856,-5708,5883,-6224,-1774,-8038,4639,3138,-7259,-1909,-9356,-940,-860,-3194,2499,-5250,-1237,6904,-3756,-8659,5463,-4754,8877,6309,-811,2841,-5964,-1475,-1482,-6108,-4000,1951,-638,-7801,3800,5497,3524,8316,-1692,6300,8803,855,-1074,-2220,5695,-5701,-275,1830}

    1

    Returns: 445976

  10. {7111,-6956,-9212,2634,2947,9450,503,-4451,4807,-5415,-1986,-9307,395,-888,1963,4708,-7746,4995,-2081,-1442,7845,-2284,-5729,-9263,8908,-1700,-3651,4717,2575,-6747,3447,9510,-2706,3097,-763,-3833,3410,981,2897,-412,-6061,9372,-8873,3212,-8914,5016,2130,4517,-1650,-1814}

    22

    Returns: 31862

  11. {8044,5285,3087,8295,9556,3388,6323,9589,6593,1750,7155,3752,7181,6206,7256,1307,3168,7835,5805,2384,9365,7404,6870,5081,9594,6346,1093,1082,9142,6417,8310,9054,3012,3782,6341,3529,1273,6199,7539,1813,7627,5074,7481,7480,4629,6843,6746,727,2186,849}

    31

    Returns: 19742

  12. {9446,3973,1079,3600,3156,7366,3337,5991,3007,1801,249,75,5620,5523,4087,1,6107,9313,1217,305,8041,8675,839,2562,9847,2244,4189,5556,5350,5971,7420,8395,4131,8009,6044,4382,9986,5160,4902,7477,8000,4870,7196,1143,3798,3070,2463,9,6642,4148}

    5

    Returns: 91812

  13. {8292,2925,660,5213,361,746,480,6141,6580,8169,1977,3591,2064,5999,1299,6810,796,9251,5592,4620,4296,6250,9036,2335,5266,4427,4926,2601,5997,9147,177,474,9532,3648,3831,9512,2207,2624,6364,9267,7948,9730,37,9563,1526,5124,9102,9839,4872,2415}

    23

    Returns: 21035

  14. {2299,563,4532,7772,371,9196,475,4155,1673,9113,1520,6983,7491,683,8339,6444,1993,943,5106,8191,3433,224,1369,2232,3216,8874,1806,5124,2694,6773,8980,4256,488,5276,4921,5732,9569,1088,7019,4042,1885,5534,1998,7958,3084,2617,8304,8793,8227,8139}

    13

    Returns: 36207

  15. {1761,1197,6363,6725,3539,666,725,2711,482,4548,1593,1927,8856,3180,8623,7352,7100,6941,3462,9572,1641,3906,1792,58,5716,447,5508,6847,8647,897,5534,4906,9028,3992,5993,9177,514,544,8435,2933,1504,192,1828,8564,3776,2133,940,958,9713,3290}

    17

    Returns: 24303

  16. {1894,5937,1330,9806,5315,8422,2494,671,7706,2515,7432,20,9777,3623,8108,9862,7438,3457,3322,2482,9369,6383,3989,5316,1655,6267,7561,8048,6507,6717,9771,1179,8714,4896,1979,62,6195,4410,4459,4211,4605,2588,6216,5047,2054,9726,6686,6609,3413,8529}

    32

    Returns: 17840

  17. {6923,6786,6114,2422,9097,5038,4551,4553,8386,5894,3929,9943,5542,3160,5156,5386,7543,6959,9219,5488,3329,9080,1147,7261,1101,8599,9129,544,353,8970,3904,2073,6262,6552,8639,2636,3120,2296,7559,1425,9903,6282,8709,963,822,625,3529,721,6305,4513}

    40

    Returns: 14089

  18. {5844,275,1485,7529,8490,1289,6959,945,7047,9296,7944,2695,5077,5435,55,8418,8676,9736,5431,9645,7120,2181,6830,9125,1478,586,8581,1122,58,1340,4196,1509,4097,4228,2305,1769,7370,7306,545,2631,4149,2043,9930,1139,366,8512,5390,2900,7444,9569}

    19

    Returns: 26546

  19. {3393,721,8002,4524,7323,6263,3851,1100,8681,9546,3210,1223,4459,4585,7478,8850,4352,3094,5287,2981,1604,4662,4854,8626,7448,2108,9509,3962,7825,9442,9975,8672,7045,72,7016,8014,8491,6150,7426,6546,2171,3293,2761,6380,3216,1254,4769,7189,9744,1146}

    44

    Returns: 12483

  20. {5525,8723,6367,9208,2543,9626,5031,9505,923,6681,23,1370,1832,7687,5241,3041,1929,9652,4734,6115,5877,621,1475,988,331,3649,687,1753,8734,634,2759,5539,2983,4475,3487,1978,7313,4735,7312,6097,9668,1798,4652,8262,8201,1162,5734,1032,1,2189}

    8

    Returns: 53876

  21. {-9356,-1915,-3128,-1881,-4275,-6987,-7089,-6054,-3053,-7132,-8310,-6154,-1470,-3603,-5275,-4493,-8947,-1467,-8168,-7459,-9778,-6573,-3407,-1550,-727,-8926,-8471,-1993,-2987,-4035,-6882,-2055,-2264,-5116,-4233,-3515,-1027,-2584,-6289,-4995,-9994,-9619,-2523,-4033,-6216,-4285,-715,-9565,-9155,-7127}

    11

    Returns: 45376

  22. {-8694,-9302,-4326,-5733,-2711,-8676,-5331,-1819,-6866,-5337,-5348,-2460,-9889,-4660,-2745,-1553,-1826,-8805,-9828,-6769,-9434,-1577,-9129,-2370,-3502,-3215,-7948,-3952,-8151,-3862,-3264,-5226,-3184,-5246,-872,-7104,-6022,-8153,-584,-7116,-2693,-9686,-2944,-137,-6467,-2546,-6426,-8748,-8289,-4150}

    20

    Returns: 27025

  23. {-7425,-958,-2071,-7113,-3983,-8619,-6820,-7326,-2064,-831,-2156,-2619,-1080,-3552,-9911,-6598,-4356,-1556,-6410,-321,-1649,-4745,-5149,-4184,-4750,-6563,-7426,-7607,-3287,-4478,-7604,-9369,-3842,-6811,-5180,-2709,-4804,-5410,-156,-9797,-6019,-1115,-2197,-4378,-9699,-373,-4018,-1278,-9529,-7202}

    12

    Returns: 38663

  24. {-9942,-1619,-2723,-3760,-1249,-7187,-8113,-7957,-3165,-1909,-2281,-6833,-5418,-4593,-8819,-3412,-4073,-5841,-8528,-7412,-6056,-5186,-790,-7717,-6708,-8922,-5604,-6643,-3586,-3121,-2951,-7196,-1154,-3283,-8984,-228,-395,-3175,-7822,-961,-2344,-2679,-9796,-8760,-6787,-4612,-5847,-8246,-3071,-6108}

    19

    Returns: 27604

  25. {-8335,-2675,-2116,-1213,-5488,-2598,-6021,-8882,-6174,-6195,-7363,-924,-437,-8881,-9219,-7607,-918,-8086,-2379,-3479,-6215,-219,-7096,-870,-8111,-7488,-3052,-708,-5663,-6072,-3110,-4585,-3848,-9217,-9141,-2085,-4116,-8246,-1631,-9767,-382,-8545,-5181,-4330,-1171,-5799,-9937,-4497,-2968,-7819}

    26

    Returns: 19107

  26. {-1895,-4123,-2381,-1201,-7077,-5272,-646,-9390,-1728,-9132,-9803,-9301,-4200,-6141,-4333,-9984,-8253,-8701,-976,-3795,-5374,-6632,-7002,-1032,-8820,-5896,-5161,-8648,-2225,-1575,-5915,-8224,-2901,-4598,-6113,-2857,-6909,-4409,-9382,-6070,-2951,-1718,-7695,-9900,-7914,-6202,-9330,-4307,-4927,-2968}

    49

    Returns: 11276

  27. {-7714,-1776,-6641,-7774,-6265,-4436,-6544,-905,-8486,-1044,-8945,-1881,-8365,-8186,-9791,-8146,-7128,-7077,-6564,-1020,-7260,-3693,-9302,-3386,-5790,-7901,-6325,-5798,-5677,-5607,-4075,-8938,-2362,-4800,-7412,-658,-1456,-2288,-8060,-3059,-3695,-4082,-8204,-7061,-7611,-124,-8226,-4067,-3123,-3295}

    4

    Returns: 134103

  28. {-4449,-56,-2436,-7644,-9376,-7596,-8431,-7274,-7376,-4827,-2645,-735,-9730,-4520,-7103,-3307,-7462,-9662,-4090,-2991,-6215,-8587,-6381,-1865,-139,-4461,-6664,-8777,-1749,-5427,-8076,-8423,-8223,-8009,-7570,-8014,-9710,-6301,-8033,-1571,-7209,-7192,-4125,-912,-8865,-9432,-7890,-7350,-1990,-239}

    21

    Returns: 28160

  29. {-4659,-8704,-3203,-8125,-1752,-2287,-1451,-1845,-7120,-4964,-4658,-6961,-6639,-5217,-801,-5926,-3349,-5726,-1602,-4157,-1656,-5258,-9239,-1255,-2893,-7851,-4367,-8156,-1595,-2074,-179,-1440,-3897,-1609,-2651,-6784,-6268,-4981,-1743,-8663,-4444,-1197,-5568,-7331,-9497,-7643,-7883,-2677,-2406,-4974}

    17

    Returns: 25445

  30. {-7913,-8584,-9212,-8863,-6688,-1231,-1742,-5477,-7725,-8800,-1277,-190,-2806,-5242,-4693,-5259,-3395,-7970,-3904,-6534,-8878,-900,-4072,-3328,-4123,-288,-9913,-6857,-3127,-3001,-7907,-2105,-4124,-7372,-2913,-2170,-3987,-6461,-673,-7898,-6871,-905,-1821,-5656,-7409,-6586,-6569,-358,-1172,-5220}

    48

    Returns: 10489

  31. {-37,2,-6,-39,-29,11,-28}

    2

    Returns: 131

    First replace the book going to position -6 on its own and then return to the pile at 0. This requires you to walk a distance of 12. Then pick up the books going to 2 and 11. You walk past shelf 2 on the way to 11, so you have to walk a total distance of 22. Now replace books -28 and -29. The distance walked is 58. Finally replace books -37 and -39. Since you don't have to return to 0, you only need to walk 39 units. Total distance = 12 + 22 + 58 + 39 = 131

  32. {-18,-9,-4,50,22,-26,40,-45}

    3

    Returns: 158

    An optimal schedule could be: -4, -9 : distance 18 -18, -26, -45 : distance 90 22, 40, 50 : distance 50 Total distance = 158

  33. {-6980,443,-3134,-6639,-65,-142,4688,-8323,-5966,1308,-5241,-3799,-8091 ,-6388,-7974,-5682,1820,-6516,-879,-3677,-266,9308,5250,-4418,-8052,6935 ,-9134,-5068,-835,5396,7262,6579,-7672,-3723,-6781,-9466,327,4973,2066,3418}

    6

    Returns: 73920

  34. {3, 4, 5, 6, 11, -1}

    2

    Returns: 29

  35. {1}

    50

    Returns: 1

  36. {9972,9969,9993,9983,9999,9957,9959,9998,9952,9986,9951,9997,9979,9962,9968,9955,9992,9975,9977,9954,9970,9967,9982,9996,9965,10000,9984,9985,9960,9964,9989,9981,9991,9988,9994,9953,9987,9961,9980,9973,9956,9958,9971,9963,9978,9974,9976,9995,9990,9966}

    18

    Returns: 49892

  37. {9992,9955,9958,9969,9961,9951,9957,9988,9996,9960,9980,9987,9995,9994,9952,9984,9979,9964,9985,9954,9981,9978,9975,10000,9973,9986,9971,9970,9959,9956,9972,9982,9989,9990,9974,9998,9967,9991,9965,9983,9953,9963,9962,9968,9977,9976,9966,9993,9997,9999}

    10

    Returns: 89800

  38. {9983,9986,9988,9955,9969,9960,9978,9958,9972,9982,9984,9977,9979,9966,9994,9963,9964,9959,9952,9956,9990,9951,9975,9968,10000,9974,9971,9992,9985,9962,9970,9953,9961,9957,9967,9991,9973,9976,9996,9995,9999,9987,9965,9980,9997,9998,9989,9981,9954,9993}

    1

    Returns: 987550

  39. {-9952,-9982,-9960,-9990,-9958,9959,-9968,-9974,-9980,9993,-9966,9991,9971,9975,9963,9969,-9962,9985,-10000,-9972,9961,-9964,9989,9979,-9970,9953,-9994,9967,-9954,9965,-9998,9951,9997,9957,9987,-9986,9995,-9988,-9984,-9996,-9956,9973,9981,-9976,-9992,9983,9999,9977,-9978,9955}

    13

    Returns: 69892

  40. {9955,9971,-9984,-9994,-9974,-9958,-9998,-9976,-9986,-9952,9965,9961,9963,9987,9959,-9972,-9980,9985,9975,9957,9979,-9960,9951,9989,9999,-9992,-9954,-9982,9983,9969,9991,9981,-9968,9967,-9964,-9988,9997,-9978,9977,9993,-9970,9953,9973,-9966,9995,-9956,-10000,-9996,-9962,-9990}

    13

    Returns: 69892

  41. {9963,-9994,-9976,-9962,-10000,-9982,-9954,9991,9981,-9956,9987,-9984,-9960,9997,9995,-9998,-9970,-9980,-9978,-9996,-9964,9971,-9972,-9992,9973,-9974,9985,9961,-9968,9951,9969,9975,9993,9989,9999,9977,-9958,9967,9953,-9952,-9966,9979,9983,-9990,-9988,9955,-9986,9959,9957,9965}

    9

    Returns: 109778

  42. {-1 }

    1

    Returns: 1

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

    3

    Returns: 34

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: