Discussion @ 1138. Integer Percentage @ Timus Online Judge

It may be useful: (if You use Dynamic Programming), increasing percentage doesn't exceed 100%

Posted by Pasha 28 Jun 2005 14:48

Simply use DP with Recurse and You'll get AC!

Re: It may be useful: (if You use Dynamic Programming), increasing percentage doesn't exceed 100%

Posted by jedimastex 17 Apr 2006 12:51

Can you prove it?

Re: It may be useful: (if You use Dynamic Programming), increasing percentage doesn't exceed 100%

Posted by Grandmaster 11 May 2017 02:05

not to much to prove, suppose we have dp[x] where x is an integer number beetwen s and n, we calculate the numbers wich are integer percent of x. for example y is a number wich is an integer percent of x like(y = x*(50/100)), the reccurence is dp[x] = max(dp[x], dp[y] + 1) among all y which are integer percent

Discussion of Problem 1138. Integer Percentage