SPOJ : ANARC05H

My OJ Blog

It’s a simple DP. State = (position, sum_of_right_sequence). Start from the right and decrement ‘position’. For each recursive call, start with a sum of 0 and add the digit at each position to this. If current sum is less than sum_of_right_sequence, then recurse.

Data set for this problem is not consistent. Any non-digit character signals end of input. Probably has blank lines or some other inconsistensies. Using gets() (I know it’s evil) kept giving WA. Using scanf() finally gave me ACC.

View original post