ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1009. K-based Numbers

Why is this problem DP?
Posted by Grandmaster 16 Mar 2016 01:17
i solved this by using Optimized backtracking and i don't understand why it needs DP?
Re: Why is this problem DP?
Posted by IlushaMax 1 Apr 2016 16:17
I've done with DP in 0.001 sec
It's very difficult to explain how you can get this formula. Maybe you'll understand :
Just it necessary to know how many new numbers you can get with knowing that numbers having 0 in the end give less than numbers having any another digit in the end.
Sorry if I have some mistakes in it.
Re: Why is this problem DP?
Posted by Grandmaster 3 Apr 2016 01:18
I have solved it both ways with DP and BackTracking, my question is aren't limits to easy to pass?