roose's blog

By roose, 12 years ago, In English

LUCKY 2 — Codechef

Chef loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Let F(X) equals to the number of lucky digits in decimal representation of X. Chef wants to know the number of such integers X, that L ≤ X ≤ R and F(X) is a lucky number. Help him and calculate that number modulo 109+7.

How to Solve this problem using DP ?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

It seems that you can view someone's successful solution.

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The DP is quite similar to the first part of CF #157 Div1-B, you can read the editorial here. You need to omit 1 state, though.