Statistics

Problem Statement for "MoveStonesEasy"

Problem Statement

There are n piles of stones arranged in a line. The piles are numbered 0 through n-1, in order. In other words, for each valid i, piles i and i+1 are adjacent.

You are given two int[]s a and b, each with n elements. For each i, a[i] is the current number of stones in pile i, and b[i] is the desired number of stones for this pile. You want to move some stones to create the desired configuration. In each step you can take any single stone from any pile and move the stone to any adjacent pile. Find and return the smallest number of steps needed to create the desired configuration, or -1 if the desired distribution of stones cannot be reached.

Definition

Class:
MoveStonesEasy
Method:
get
Parameters:
int[], int[]
Returns:
int
Method signature:
int get(int[] a, int[] b)
(be sure your method is public)

Notes

  • At any moment during the game some piles may be empty. Empty piles still remain in place. For example, if pile 5 is empty, you are not allowed to move a stone from pile 4 directly to pile 6 in a single step. Instead, you must place the stone onto the empty pile 5 first.

Constraints

  • n will be between 1 and 50, inclusive.
  • a will have exactly n elements.
  • b will have exactly n elements.
  • Each element of a and b will be between 0 and 1,000,000 (10^6), inclusive.

Examples

  1. {1, 2}

    {2, 1}

    Returns: 1

    We need to move one stone from pile 1 to pile 0.

  2. {10, 0}

    {0, 10}

    Returns: 10

  3. {0, 0, 1}

    {1, 0, 0}

    Returns: 2

    Note that in a single step we can only move a stone between adjacent piles. Hence, we need two steps to move a stone from pile 2 to pile 0.

  4. {12, 12}

    {12, 12}

    Returns: 0

    The desired configuration of stones is the same as the current configuration. No steps necessary.

  5. {5}

    {6}

    Returns: -1

    We cannot add or remove stones, we can only move them between piles.

  6. {3,10,0,4,0,0,0,1,0}

    {5,5,0,7,0,0,0,0,1}

    Returns: 9

    Move 2 stones from pile 1 to pile 0. Move 3 stones from pile 1 to pile 2. Move 3 stones from pile 2 to pile 3. Move 1 stone between two last piles. The total number of steps is 2 + 3 + 3 + 1 = 9.

  7. {280679, 91421, 806309, 427023, 279501, 112931, 879234, 944975, 917321, 40007, 397540, 562248, 589633, 348334, 357352}

    {279501, 879234, 562248, 40007, 944975, 357352, 91421, 427023, 397540, 917321, 112931, 589633, 806309, 280679, 348334}

    Returns: 5160778

  8. {6915, 330782, 767598, 470099, 106993, 949379, 46019, 97270, 699545, 149081, 132382, 828450, 950647, 22267, 305976}

    {699545, 949379, 22267, 330782, 470099, 950647, 767598, 132382, 6915, 828450, 106993, 97270, 149081, 46019, 305976}

    Returns: 12337103

  9. {417582, 936316, 806647, 677542, 537659, 455487, 718103, 564678, 669361, 835156, 699041, 625480, 933335, 873999, 509751}

    {835156, 537659, 933335, 564678, 873999, 625480, 677542, 936316, 806647, 417582, 509751, 455487, 718103, 699041, 669361}

    Returns: 5295067

  10. {926853, 76850, 758239, 478954, 406486}

    {76850, 478954, 926853, 758239, 406486}

    Returns: 1577187

  11. {871999, 658838, 381173, 13452, 939680, 369008, 240259, 425427, 557839, 525344, 758816, 864121, 953316, 62627, 669831}

    {525344, 871999, 240259, 369008, 864121, 669831, 658838, 381173, 62627, 557839, 13452, 758816, 953316, 425427, 939680}

    Returns: 5019470

  12. {10645, 141272, 478507, 202560, 22029, 268815, 837695, 369148, 718239, 285139, 455363, 665078, 440776, 372, 113897, 647584, 65650, 535109, 372308, 741398, 93101, 86932, 454243, 941075, 8977, 834388, 561828, 395794, 77053, 573133, 727927, 665943, 423842, 30552, 338121, 275293, 495463, 34635, 787286, 588867, 351095, 434185, 365289, 24947, 670174, 666982, 171818, 926815, 439393, 67367}

    {573133, 454243, 670174, 727927, 561828, 665943, 369148, 455363, 395794, 423842, 478507, 34635, 67367, 787286, 837695, 495463, 535109, 77053, 665078, 10645, 113897, 22029, 141272, 372, 440776, 275293, 834388, 439393, 93101, 434185, 65650, 86932, 718239, 171818, 588867, 372308, 926815, 741398, 338121, 8977, 30552, 202560, 351095, 268815, 647584, 365289, 941075, 285139, 24947, 666982}

    Returns: 54625763

  13. {97367, 284951, 974982, 530895, 255054, 213146, 929557, 337701, 277399, 417511, 45114, 983839, 524861, 84265, 206668, 529668, 209190, 794941, 934350, 934080, 17993, 203594, 281280, 592051, 242145, 89233, 629252, 332428, 87808, 357715, 581471, 563800, 139950, 974519, 933767, 848318, 980896, 560131, 142025, 824264, 945703, 507467, 516200, 766048, 417706, 814695, 29595, 269328, 748435, 873230}

    {933767, 848318, 507467, 29595, 281280, 209190, 560131, 417511, 255054, 934350, 17993, 417706, 529668, 974982, 794941, 766048, 934080, 87808, 284951, 524861, 213146, 242145, 629252, 814695, 929557, 983839, 45114, 84265, 332428, 873230, 581471, 974519, 357715, 592051, 530895, 337701, 269328, 748435, 516200, 142025, 97367, 945703, 824264, 277399, 139950, 206668, 89233, 203594, 563800, 980896}

    Returns: 68977452

  14. {54110, 614432, 407285, 313014, 112686, 488162, 601390, 802784, 740652, 340467, 254460, 678256, 467059, 278831, 881694, 460557, 590103, 599283, 360766, 260480, 994876, 724008, 477611, 525332, 602887, 949446, 967863, 288380, 353557, 51137, 191056, 129330, 20879, 448916, 692274, 520574, 769405, 138296, 500508, 561098, 44837, 493153, 568236, 148427, 341669, 912751, 387743, 934839, 987492, 231585}

    {313014, 387743, 129330, 934839, 520574, 678256, 191056, 493153, 278831, 769405, 599283, 467059, 44837, 525332, 912751, 802784, 561098, 353557, 340467, 949446, 448916, 692274, 148427, 740652, 614432, 601390, 488162, 724008, 460557, 568236, 260480, 987492, 288380, 477611, 967863, 254460, 341669, 590103, 112686, 881694, 602887, 994876, 54110, 138296, 360766, 231585, 20879, 51137, 407285, 500508}

    Returns: 40754832

  15. {426154, 836520, 829966, 470344, 116337, 63073, 597696, 453676, 798696, 685861, 457191, 542419, 373781, 161321, 517177, 141096, 203905, 974767, 221910, 253033, 39381, 256354, 954229, 218287, 77007, 423258, 972174, 27119, 11488, 432247, 688089, 337556, 573495, 31404, 43874, 969589, 987199, 258507, 766267, 929833, 921835, 894326, 456826, 732771, 305537, 972206, 194959, 318960, 118194, 296273}

    {453676, 43874, 929833, 457191, 829966, 194959, 203905, 11488, 798696, 118194, 221910, 597696, 256354, 63073, 954229, 253033, 318960, 426154, 974767, 542419, 766267, 31404, 688089, 470344, 969589, 732771, 141096, 258507, 296273, 305537, 987199, 337556, 116337, 77007, 373781, 423258, 27119, 972206, 921835, 972174, 517177, 432247, 685861, 218287, 836520, 573495, 161321, 39381, 894326, 456826}

    Returns: 32924771

  16. {402950, 188530, 439132, 132274, 918901, 498245, 147400, 892712, 904683, 5573, 170462, 827152, 832591, 90499, 347105, 33859, 102982, 153521, 229714, 479834, 451103, 982473, 210576, 693429, 424322, 62521, 59107, 159066, 119942, 483744, 729490, 94673, 140854, 700815, 43178, 376368, 460822, 851463, 859518, 216372, 856589, 250758, 246554, 822896, 452251, 358043, 704208, 149953, 93745, 708079}

    {832591, 729490, 250758, 43178, 358043, 94673, 159066, 822896, 859518, 498245, 856589, 439132, 460822, 147400, 424322, 452251, 693429, 140854, 982473, 700815, 170462, 119942, 5573, 479834, 188530, 90499, 216372, 149953, 483744, 827152, 153521, 59107, 102982, 708079, 904683, 851463, 93745, 33859, 892712, 918901, 376368, 704208, 132274, 347105, 210576, 62521, 246554, 451103, 229714, 402950}

    Returns: 37727538

  17. {200990, 215317, 757383, 375670, 448131, 815813, 504224, 297061, 685227, 933564, 579679, 571135, 171290, 406102, 28012, 273011, 764119, 32629, 801502, 958136, 944685, 655760, 705131, 169193, 817993, 202034, 383275, 192940, 105710, 143007, 749154, 634066, 106320, 283587, 127145, 936129, 958695, 77166, 378651, 59539, 959097, 267230, 378695, 136410, 264316, 430700, 97272, 651247, 272611, 544650}

    {383275, 283587, 375670, 106320, 136410, 579679, 944685, 764119, 169193, 192940, 264316, 28012, 202034, 430700, 215317, 933564, 749154, 97272, 272611, 634066, 32629, 378651, 757383, 448131, 936130, 143007, 77166, 958695, 406102, 59539, 171290, 685227, 571135, 705131, 817993, 267230, 504224, 651247, 815813, 200990, 273011, 105710, 958136, 544650, 959097, 801502, 655760, 297061, 127145, 378695}

    Returns: -1

  18. {626467, 573993, 822383, 693959, 354647, 23761, 697913, 152322, 323080, 298723, 922980, 209677, 447716, 222263, 521660, 47151, 443256, 68851, 908173, 837977, 839526, 161435, 178419, 698428, 49642, 576590, 233178, 941111, 869572, 65778, 470785, 606381, 199040, 420184, 597000, 753234, 856869, 903635, 455110, 745685, 560777, 984533, 382864, 78229, 990731, 871297, 904302, 226688, 94047, 460658}

    {447716, 560777, 606381, 152322, 47151, 521660, 903635, 626467, 455110, 922980, 837977, 698428, 871297, 68851, 65778, 745685, 323080, 226688, 443256, 753234, 460658, 908173, 382864, 178419, 869572, 839526, 597000, 856869, 354647, 199040, 94047, 23761, 904302, 941111, 576590, 209677, 161435, 49642, 470785, 233178, 693959, 697913, 420184, 984533, 298723, 822382, 78229, 222263, 573993, 990731}

    Returns: -1

  19. {657374, 837336, 867883, 578003, 502688, 30881, 389717, 310649, 847251, 789486, 488006, 391616, 679362, 776091, 298022, 873985, 564663, 800686, 590006, 614990, 683939, 824281, 355073, 208333, 177400, 41604, 393104, 54932, 614389, 101532, 514672, 841195, 390543, 791002, 441843, 695518, 185810, 948204, 109808, 689237, 648068, 76375, 242775, 601691, 402332, 142392, 531083, 712644, 747441, 104263}

    {614389, 142392, 185810, 390543, 402332, 441843, 712644, 689237, 867883, 776091, 657374, 488006, 847251, 590006, 177400, 614990, 564663, 310649, 76375, 208333, 679362, 355073, 948204, 30881, 242775, 41604, 54932, 502688, 837336, 101532, 695518, 789486, 578003, 389717, 873985, 391616, 514672, 601691, 800686, 393104, 531083, 109808, 683939, 824281, 841195, 104263, 648068, 298022, 747440, 791002}

    Returns: -1

  20. {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    Returns: 625000000

  21. {12, 12 }

    {12, 12 }

    Returns: 0

  22. {100, 0, 0, 0, 0 }

    {0, 0, 0, 0, 100 }

    Returns: 400

  23. {4, 5, 2, 1, 8, 6, 3, 8 }

    {6, 3, 4, 4, 4, 3, 6, 7 }

    Returns: 13

  24. {3, 2, 11 }

    {5, 6, 5 }

    Returns: 8

  25. {6 }

    {5 }

    Returns: -1

  26. {5 }

    {6 }

    Returns: -1

  27. {4, 5, 2, 1, 8, 6, 3, 8, 20, 8 }

    {6, 3, 4, 3, 0, 3, 6, 12, 16, 12 }

    Returns: 27

  28. {2, 2, 0, 0, 2 }

    {0, 0, 0, 0, 0 }

    Returns: -1

  29. {999999, 1, 999999, 999999, 999999, 999999, 999999, 999999, 1, 999999, 999999, 999999, 999999, 1, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 1, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 1, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 1, 999999 }

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

    Returns: 44999910

  30. {1, 1, 1 }

    {0, 3, 0 }

    Returns: 2

  31. {0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 1000 }

    {1000, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0 }

    Returns: 12990

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: