kuroko's blog

Can someone explain the idea behind the solution?
By kuroko, 11 years ago, In English

I tried to solve this problem http://mirror.codeforces.com/problemset/problem/459/C . After some time I checked out the editorial and i understood the basic idea but i cant understand how the sequence is generated.

http://mirror.codeforces.com/contest/459/submission/7495236 is the solution given in the editorial.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
11 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

It's similar to dp approach..

ans[i][0....d-1] gives you the ith k-based number of d digits.

So ans[i][...]=next number after ans[i-1][..]

So start from the 0th place (ans[i][d-1]) and add 1, take modulo.

If the resulting digit is not zero, u've already obtained the next number, then break;

Else if it is zero, u have to go to the next higher place and repeat the procedure.

→ Reply