Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

ayushanshul07's blog

By ayushanshul07, history, 5 weeks ago, In English

1985G - D-Function

For numbers with l+1 digits, there are floor(9/k) + 1 (say a) options per digit, hence the total number of numbers should be a^(l+1). Similarly, for l+2 digits, a^(l+2). So on for r digits, a^(r).

Shouldn't the answer be the sum of these numbers?

a^(l+1) + a^(l+2) + .... + a^r

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ayushanshul07 (previous revision, new revision, compare).

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

say l =3 , r =5; means your n will be between 1000 and 100000 1000,1001,1002...1999,... ,99999 will be your probable numbers out of which the valid numbers must have each digits lesser than or equal to 9/k. now say we didnt have a lower limit r then the valid answer would have been : a^r , but we have a lower bound l so we over counted those numbers so we can just do -a^l, final answer being a^r -a^l.

why your approach is wrong : a^r is the number of valid numbers till number of digits are r thats simple catch you missed. so you basically are over counting. why does a^r include all valid numbers upto r digits : since you are also counting 0 as valid digit hence we can get all r-1 , r-2, ... 1 digit numbers too!!