Pebbles
SRM 119 · 2002-11-07 · by axchma
Problem Statement
Suppose you have pebbles arranged into several piles. On each round you take one pebble from each pile and make a new pile out of the pebbles you took. As the number of ways to divide the pebbles into piles is finite, it is obvious that arrangements of piles will start to repeat themselves.
Your task is, given an arrangement of pebbles into piles, return the first round when the cycle starts. Consider the original arrangement as round zero.
Comment
This problem is based on the following math problem. You have an arrangement
with 45 pebbles, prove that after several rounds it stabilizes (i.e. the final cycle is actually an arrangement that repeats itself at each round). This math
problem sounds easy, but in fact it is not that trivial.
Notes
- The arrangement doesn't depend on how you order the piles. Namely, the arrangement {3, 2, 1} is considered the same as {1, 2, 3}.
Constraints
- initialPiles has between 1 and 20 elements inclusive
- each element in initialPiles is between 1 and 100 inclusive
{1,2,3,4,5,6,7,8,9}
Returns: 0
If we take one pebble away from each of the piles to form a new pile, we will have a new pile with 9 pebbles. Each of the other piles has one less pebble than originally, in particular, the pile which had 1 pebble disappears. Thus, we end up with piles with the same numbers of pebbles that we started with - {1,2,3,4,5,6,7,8,9}.
{5}
Returns: 2
We take one pebble from the only pile and make a new pile with it. Thus, on the next round we have the arrangement {1, 4}. On the next round we have {2, 3}, the next round - {1, 2, 2}, the next round - {1, 1, 3}, and the next round - {2, 3}. The last arrangement of piles is the same as round two, return 2.
{100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100}
Returns: 2762
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 15
{10,20,30,40,50,60,70,80,90,100,10,20,30,40,50,60,70,80,90,100}
Returns: 246
Submissions are judged against all 27 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Pebbles with a public method int cycleStart(vector<int> initialPiles) · 27 test cases · 2 s / 256 MB per case