jainor's blog

Spoj problem
By jainor, 12 years ago, In English

somebody can help me?

http://www.spoj.pl/problems/DRACULA/

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

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

Let F(G, S) is number of tickets between 1 and G inclusive with sum of digits equal to S. we need to know for each S between 1 and 18 * 9 value F(B, S) — F(A — 1, S). we can compute F(G, S) using DP.
D(pos,b,s) — how many tickets there is with sum of digits equal to s, pos — is position in the string GS representing number G (from left to right), b — currently constructed digits coincide with prefix of GS (with length pos) or not.

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

i had a similar idea but using DP to count the sums was what i need. thanks

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice to see the interest in this problem.

I am the Writer, if you need the test cases just give me your e-mail and I can send them :).

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually I got it. If you have more interesting problems please send them. thanks anyway :)

    → Reply