Instead of brute force is there any trick or formula to solve this problem.

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36

Instead of brute force is there any trick or formula to solve this problem.

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36

With brute force you have to memoize the result also. So that you can use the previously calculated result without needing to calculate again.