Statistics

Problem Statement for "PairingPawns"

Problem Statement

"Pairing pawns" is a game played on a strip of paper, divided into N cells. The cells are labeled 0 through N-1. Each cell may contain an arbitrary number of pawns.

You are given a int[] start with N elements. For each i, element i of start is the initial number of pawns on cell i.

The goal of the game is to bring as many pawns as possible to cell 0.

The only valid move looks as follows:

  1. Find a pair of pawns that share the same cell X (other than cell 0).
  2. Remove the pair of pawns from cell X.
  3. Add a single new pawn into the cell X-1.

You may make as many moves as you wish, in any order.

Return the maximum number of pawns that can be in cell 0 at the end of the game.

Definition

Class:
PairingPawns
Method:
savedPawnCount
Parameters:
int[]
Returns:
int
Method signature:
int savedPawnCount(int[] start)
(be sure your method is public)

Notes

  • You may assume that the answer will always fit into an int.
  • Note that you are only given the int[] start. The number of cells N can be determined as the length of start.

Constraints

  • start will contain between 1 and 20 elements, inclusive.
  • Each element of start will be between 0 and 1,000,000, inclusive.

Examples

  1. {0,2}

    Returns: 1

    There are two pawns on cell 1. You can remove them both and place a pawn onto cell 0.

  2. {10,3}

    Returns: 11

    There are 10 pawns already on cell 0. You can add another one by removing two pawns from cell 1. Note that at the end of the game cell 1 will still contain one pawn that cannot be used anymore.

  3. {0,0,0,8}

    Returns: 1

    After 7 moves you can get a single pawn to cell 0. The rest of the board will be empty.

  4. {0,1,1,2}

    Returns: 1

    Again, a single pawn can reach the leftmost cell.

  5. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,123456}

    Returns: 0

    That's a lot of pawns! But they are too far away. In this case it is impossible for a pawn to reach cell 0.

  6. {0,0,0,7,0,0,7,0,0,7,0,0,7,0,0,7,0,0,8}

    Returns: 1

  7. {0,0,0,7,0,0,7,0,0,7,0,0,7,0,0,7,0,0,7}

    Returns: 0

  8. {0}

    Returns: 0

  9. {47}

    Returns: 47

  10. {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    Returns: 1999998

  11. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 0

  12. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 1

  13. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1000000}

    Returns: 1

  14. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,524288}

    Returns: 1

  15. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,524287}

    Returns: 0

  16. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1000000}

    Returns: 3

  17. {296172,23166,484266,687650}

    Returns: 514777

  18. {326498,573090,43163,237303,308856,936954,287349,333671,380443,816305,136232,641843,537022}

    Returns: 712834

  19. {935806,930822,726198,91596,874671,926003,584880,583333,951900,125157,843631,706680,969893}

    Returns: 1696885

  20. {628467,764087,996960,189181,290032,661246,371913,786053,69227,748484,934722,481379,226438}

    Returns: 1337076

  21. {408610,692840,133581,606047,377552,418390,970948,386835,434282,499504,772163,21519,499425}

    Returns: 922604

  22. {104312,205556,385889,515195,524230,805166,698782,462888,867430,910398}

    Returns: 445588

  23. {834584,374313,670825}

    Returns: 1189446

  24. {90628,745761,174598,344859,199502,691156,750761,643245,374202,20591,178485,274317,625374}

    Returns: 603051

  25. {595437,681024,987140,560231,71792,231829}

    Returns: 1264494

  26. {619305,859420,298876,481878,962945,304731,366576,963210,619741,615607,410461,592172}

    Returns: 1271241

  27. {370011,663212,762762,458496,914591,269474,482930,972100,798919,20788,982460,802120,978784,896382,550700,844141,771965,178721,287008}

    Returns: 1035277

  28. {23487,827261,753020,725053,884126,526825,227472,568060,720019,555970,405658,943208,222104}

    Returns: 800526

  29. {420184,260533,909871,307463,561129,210216,916947,936018,576308,433888}

    Returns: 882729

  30. {472170,503962,680078,46334,586035,384550,894619,358283,931703,379962,537917,352437}

    Returns: 970463

  31. {414916,216937,350163,990649,124295,12533,502296}

    Returns: 750764

  32. {143544,742937,588822,51132,18569,678930,551704,539019,87963,81057,344078,76651,892682,655345,453020,816349}

    Returns: 705043

  33. {665901,483893,823767,244403,13778,997276,926260,581622,554753,781922,570864,707929,66155,681048,28483,513813,115033,386375,769387}

    Returns: 1200104

  34. {25703,525269,581823,719566,496756,529524,901339,711643,769279,581100,285451,882139,180353,229155,116604,627613,377505,171870}

    Returns: 595931

  35. {669675,560739,91551,446108,669164,399005,607221,213327,927559,173339,327036,288732,332767,280493,381870,104675}

    Returns: 1098706

  36. {479733,731593,346458,550679,404094,881478,480409,442523,477508,199819,284563,391653,802012}

    Returns: 1067665

  37. {129695,344160,175962,256509,297311,792405,468074,848459,176097}

    Returns: 435803

  38. {639871,278691,310078,786778,777235,416673,581410,832767,402632,952157}

    Returns: 1035704

  39. {377631,783115,555323,679812,124445,339174,192583,153299,716775}

    Returns: 1018379

  40. {846358,465074,919870,265206,710677,736564,181904,293138,847844,413971,821,669847,304173,3882,136508,579580,365473,586875}

    Returns: 1419139

  41. {514815,77494,971997,800270,779312,199340,38552,338413,242151,581449,961285,264528,922495,91620}

    Returns: 958163

  42. {539824,706411,532646,217935,244537,414565,774413,574258,348731}

    Returns: 1099620

  43. {838210,509291,227539,416539,802745,252432,274816,946024,456107,55436,942099,827606,999663,813063,816048}

    Returns: 1275159

  44. {803045,626042,801560,491300,6743,367226,184079,747639,232039,789334,321098,302152,543591,41240,535224,304246,223321,421076,129852,128707}

    Returns: 1401579

  45. {776229,271206,852186,487211,369999,209936,518235,773140,538277,226707,759121,207552,330575,838177,304929,650151,79921}

    Returns: 1233213

  46. {725827,870860,283813}

    Returns: 1232210

  47. {171281,194433}

    Returns: 268497

  48. {844814,545853,937420,185729,396950,986527,529001,120770,793719,870887,514368}

    Returns: 1445462

  49. {111390,593097,152175,781919,886101,249006,455193,597895,731502,390868,54193,620412,642823,386547,133072,715807,91317,451484,461303}

    Returns: 622885

  50. {16486,885946,587769}

    Returns: 606401

  51. {864829,99999,666570}

    Returns: 1081471

  52. {783978,868842,504466,390541,29485,917708,599039,86954,703341,72310,628731,711403,673179,693511,262066,285459}

    Returns: 1438017

  53. {509556,210186,817277,768305,812004,208690}

    Returns: 972278

  54. {441067,908974,684086,692685,780154,548427,147564,371123,213025}

    Returns: 1225096

  55. {47135,797542,30905,540146,100368,310079,150378,684789,643288,162806,458893,191799,969485,110973,496563,984099,647640,234895,449146}

    Returns: 548509

  56. {298485,504433,622026}

    Returns: 706208

  57. {630763,357931,359398,360280,717663}

    Returns: 989466

  58. {293367,60639,60116,60689,61348,60296,60583,60296,60530,121732}

    Returns: 353912

  59. {589110,221135,220185,220443,219518,218538,220338,440048}

    Returns: 809708

  60. {595544,40478,39855,40020,39560,40156,39302,40343,39549,40060,39546,39513,39969,39687,39561,79962}

    Returns: 635715

  61. {660788,96621,96733,95541,95712,97110,96699,95592,97548,95442,96068,95815,193108}

    Returns: 757254

  62. {742366,64522,65092,63906,64071,66162,64154,64271,64244,64264,64354,64144,129396}

    Returns: 806966

  63. {643107,22729,22706,22638,23083,22442,22828,22803,23365,22318,22939,22447,22817,23406,22292,23127,45794}

    Returns: 665836

  64. {625313,97013,97622,98339,97995,97924,97635,98260,97695,195058}

    Returns: 722757

  65. {456451,133971,135547,133939,134792,135502,134590,135549,267902}

    Returns: 590933

  66. {501761,171672,172733,174315,172861,172146,347016}

    Returns: 674175

  67. {486479,125863,125148,124352,125547,126000,123202,250146}

    Returns: 611904

  68. {132644,115472,113462,116034,228904}

    Returns: 247556

  69. {106540,277819}

    Returns: 245449

  70. {641023,234613,235639,234274,235315,235923,234933,470510}

    Returns: 875949

  71. {270491,156475,310160}

    Returns: 426268

  72. {309181,132916,267757}

    Returns: 442578

  73. {63894,2806,2896,3263,2842,2850,2874,2944,3004,3055,3061,2876,2931,2919,2967,3031,2845,3021,5930}

    Returns: 66786

  74. {287718,34002,32959,33426,33144,33100,33186,33209,33162,33311,32939,33198,33140,33009,66382}

    Returns: 321280

  75. {382391,450678,450366,897750}

    Returns: 832540

  76. {403096,39170,38626,38240,39625,37828,38966,38782,38402,38361,38307,38521,38572,38281,77718}

    Returns: 441987

  77. {229978,22876,21694,22706,22168,23018,22520,45001}

    Returns: 252486

  78. {599167,37834,36853,37349,37749,37780,36458,37612,37408,37390,37117,37389,36563,37410,37067,37400,36981,74782}

    Returns: 636661

  79. {616881,49093,49837,50352,50003,49224,50651,49732,49963,50295,49814,50237,49626,49699,99882}

    Returns: 666414

  80. {262318,605651}

    Returns: 565143

  81. {844456,119182,118188,118044,117017,117107,235358}

    Returns: 963000

  82. {788187,122603,123364,122395,123463,122657,123481,123080,121917,124048,123433,124041,122580,246990}

    Returns: 911029

  83. {646118,317398,319261,319634,318605,637304}

    Returns: 964415

  84. {807428,115142,117032,114721,116532,114501,116178,116546,114439,116121,115611,115756,115490,115199,232074}

    Returns: 923084

  85. {734477,95016,95689,94142,94789,94818,191144}

    Returns: 829549

  86. {562247,114189,113560,112649,114277,114491,113899,111770,113385,228582}

    Returns: 676075

  87. {526893,179756,178057,179368,179269,359150}

    Returns: 706134

  88. {645573,242294,240675,243116,242589,483294}

    Returns: 887543

  89. {467694,334537,337157,332816,668896}

    Returns: 802659

  90. {109688,5736,5369,5702,5333,5972,5538,5743,5359,5627,5423,5506,5688,5729,5388,5518,5586,11220}

    Returns: 115305

  91. {362174,85593,83540,84308,84278,84574,85784,84682,169148}

    Returns: 446967

  92. {13362,12283,12891,13096,25582}

    Returns: 25962

  93. {322388,110268,109760,110708,110177,111237,109559,221366}

    Returns: 432604

  94. {48348,25665,25058,51535}

    Returns: 73886

  95. {221969,36085,36869,37218,36723,36283,36430,36928,36861,37185,36962,72785}

    Returns: 258456

  96. {5676,1011,960,962,1138,935,1051,1015,885,1151,903,958,1106,1916}

    Returns: 6674

  97. {632880,106605,106958,106698,107961,106866,106745,107165,105430,108400,213966}

    Returns: 739683

  98. {295504,34564,35139,33814,34033,34380,34655,34556,34460,34479,34489,34929,34661,34607,34560,35296,68760}

    Returns: 330080

  99. {753955,40118,39273,39795,39665,40132,39822,40428,39275,39606,40391,40139,39463,39386,39858,39895,40569,38296,79764}

    Returns: 793787

  100. {221909,20492,21750,20324,20781,21270,20520,20989,20788,20865,21107,20924,20631,20831,20817,20693,20769,20647,20658,41544}

    Returns: 242744

  101. {108876,3888,4050,4445,3986,4211,4061,4055,4116,4074,4069,4139,4098,4103,3911,4272,3983,4035,8304}

    Returns: 112896

  102. {430234,18752,18351,18448,18654,19080,18444,18390,19025,18450,18298,18220,18811,18883,18832,17710,18488,18309,36487}

    Returns: 448844

  103. {72418,919411}

    Returns: 532123

  104. {164202,7538,7395,7990,7515,7795,7435,7240,7728,7360,7582,7870,7234,15634}

    Returns: 171763

  105. {677913,131801,129722,129161,129954,130959,130634,130476,261063}

    Returns: 808683

  106. {578114,133960,133679,133308,132755,267570}

    Returns: 711836

  107. {678514,101497,101912,99862,101007,100437,99865,101139,100698,100143,102749,100528,100698,100702,202672}

    Returns: 779813

  108. {351016,1000000}

    Returns: 851016

  109. {54182,2586,2567,2411,2465,2633,2488,2431,2540,2558,2452,2324,2426,5116}

    Returns: 56732

  110. {899687,66754,66493,66411,66987,65762,66490,67793,66094,66822,66779,67020,66534,65763,67600,66583,66170,66618,133452}

    Returns: 966318

  111. {51117,12379,12470,12632,12012,12434,12467,24178}

    Returns: 63526

  112. {316755,87459,88438,86393,86466,88042,86947,175098}

    Returns: 404275

  113. {884302,60715,59575,60135,60240,61322,60478,60358,121100}

    Returns: 944641

  114. {746433,61232,61874,60872,60071,61941,60744,61716,60131,60882,62105,61063,60876,61226,62345,61066,60477,61485,60930,122404}

    Returns: 807722

  115. {35216,14560,14684,14826,14479,15051,29280}

    Returns: 49853

  116. {19753,1128,1060,1174,1040,1147,1076,1100,929,1192,1043,1043,1042,1085,1029,1036,1167,1050,2116}

    Returns: 20863

  117. {1000,2000,3000,4000,5000,6000,7000,8000}

    Returns: 3921

  118. {0, 1, 1, 2, 32, 11, 21, 1, 0, 99, 87 }

    Returns: 3

  119. {1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000 }

    Returns: 3921

  120. {0, 2 }

    Returns: 1

  121. {0, 0, 4 }

    Returns: 1

  122. {100 }

    Returns: 100

  123. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 1999938

  124. {0, 0, 0, 8 }

    Returns: 1

  125. {0, 2, 0, 0 }

    Returns: 1

  126. {1 }

    Returns: 1

  127. {1, 1, 2 }

    Returns: 2

  128. {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190 }

    Returns: 39

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: