When time is short

Revision en1, by micklepru, 2015-08-27 20:37:14

Hello, Codeforces! I just want to thank all of you guyz for this wonderful place uniting these wonderful people. Place where you can improve yourself and if you having any troubles you won't be left alone. Thank you, community! Now to the topic.

I ask you to help me improve my algorithm, which gives TLE.

Here is the problem: For given N (1<=N<=1000) find the smallest positive integer with the sum of digits N which is divided by N. Samples: - input: 1; output: 1 - input: 10; output: 190 Time limit: 2sec.

My solution I used DP approach: dp[sum][rem] — smallest positive integer with the sum of digits sum and remainder after division by N is rem. Now for every integer dp[sum][rem] we iterate through all possible digits and add them to the end. With obtained number we try to improve dp[sum+lastDigit][(rem*10+lastDigit)%N]. Answer is dp[N][0].

But this solution is too slow and runs more than 4 seconds on max test.

Any tips will be appreciated.

Tags dp, tle, dynamic programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English micklepru 2015-08-28 23:43:23 461 Tiny change: '-248340). [My code](ht' -
en1 English micklepru 2015-08-27 20:37:14 1037 Initial revision (published)