Hi, I hope this is correct. Please correct if I am wrong.
Short answer: Let a = (k-n)/(n-1) Let b = (k-n)%(n-1) steps = (n-1)(a)(a+1)/2 + b Put = steps + n Remove = steps Explanation: Example with n = 3 & k =10: Start by putting balls in 1,2,3 1 2 3 x x x x x x Now move balls from 1-3 to 3-5 using (n-1) steps 1 x 3 4 x x x x x REMOVE 2, PUT 4 x x 3 4 5 x x x x REMOVE 1, PUT 5 Moving balls from 3-5 to 5-7 using steps 1 and 2. 1) move first n-1 balls to 1 to n -1 slots. This takes ( reached_so_far - n ) steps x x 3 4 5 x x x x REMOVE 4, PUT 2 x 2 3 x 5 x x x x REMOVE 3, PUT 1 1 2 x x 5 x x x x 2) move balls in 1 to n-1 slots to (reached_so_far + 1) to (reached_so_far + n -1) slots. This takes (n-1) steps 1 2 x x 5 x x x x REMOVE 2, PUT 6 1 x x x 5 6 x x x REMOVE 1, PUT 7 x x x x 5 6 7 x x Similarly we can move from 5-7 to 7-9 in ( 4 + 2 = 6 steps ) Now we can directly complete with one more step. Summary: Move from 1-3 to 3-5 in 2 steps Move from 3-5 to 5-7 in 4 steps Move from 5-7 to 7-9 in 6 steps Move 1 ball to 10 in 1 step PUT = 13(steps) + 3 (initial) REMOVE = 13(steps) Thanks, Balaji. On Fri, Mar 18, 2011 at 7:06 PM, shubham <[email protected]> wrote: > You have N marbles and K slots. You have to follow the below mentioned > rules : > > 1. You can put in a marble or take out a marble from slot numbered > 1 at any time. > 2. You can put in a marble or take out a marble from slot numbered > i only if there exists a marble at the slot i - 1. > 3. The game stops when a marble reaches the slot numbered K for the > first time. > > Your task is to finish the game in minimum number of valid moves. > > for further clarification one can visit: > > http://www.spoj.pl/problems/MOVMRBL/ > > I am not able to calculate manually the steps for some (N,K) pair > (except the cases where K is less than or equal to N*(N-1)/2). > e.g how to proceed with just 3 marbles and 10 slots... > > any idea in this direction will be appreciated... > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
