ashishranjan2828's blog

By ashishranjan2828, history, 7 years ago, In English

how to solve this problem

Given three integers x,y and z you need to find the sum of all the numbers formed by having 4 atmost x times , having 5 atmost y times and having 6 atmost z times as a digit.

example say 4, 5, 6 occurs 1 time

The ans for the above example is 4+5+6+45+54+56+65+46+64+456+465+546+564+645+654=3675

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

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what are the limits ?

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

You can make dp, dp[i][j][k] — sum of all numbers which have 4 — i times, 5 — j times, 6 — k times. I also used cnt, cnt[i][j][k] — count of such numbers:

Code
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain logic behind it ... pls

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

      I'll call number (i, j, k) number with 4 — i times, 5 — j times, 6 — k times. For example we want to calculate sum of numbers (i, j, k). We can get it using sum of (i — 1, j, k), sum of (i, j — 1, k) and sum of (i, j, k — 1). I'll explain the first case, other are similar. All numbers (i, j, k) ending on 4 we can get from (i — 1, j, k) adding 4 to the back. So if sum of (i — 1, j, k) is S1, count of (i — 1, j, k) — C1, we need to add to dp[i][j][k] S1 * 10 + C1 * 4 (shifting each of (i — 1, j, k) and adding 4 to each).