Блог пользователя kuroko

Can someone explain the idea behind the solution?
Автор kuroko, 11 лет назад, По-английски

I tried to solve this problem http://codeforces.me/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://codeforces.me/contest/459/submission/7495236 is the solution given in the editorial.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить