project euler problem 334

Spilling the beans

An interesting problem! 

I spent several hours on this problem, but failed to find any clue. I wrote a brute force solution for it, checked the  number of moves required when the number of beans are small in each bowl(two bowls for example). I found some analytical formula for any number of beans in only two bowls, but all futile. Since the problem ask for 1500 bowls, the total number of beans is about 1.5 million!  The largest headache I found is to determine the position of the empty bowl.

I played the game again and again on papers, those empty bowls are killing me! Finally I found a solution to make number of empty bowls at minimum. But my program is too slow.  After some time, I found how to make it efficient. The trick is simple, we need to do as much analytical work as we can, leave the task for the computer easy and simple.

It only takes my notebook 0.03 second to get the answer! Isn't that kidding?! I spent a couple of days working for the computer and leave it only 30 millisecond's work.

I really enjoyed in solving the problem. This is the glamour of project euler!