kingofnumbers's blog

By kingofnumbers, 5 years ago, In English,

I need help to solved this intersting problem link .

thank you in advance.

 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it  

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

if you now know how to solve it then please help .

  • »
    »
    6 months ago, # ^ |
    Rev. 4   Vote: I like it -8 Vote: I do not like it

    not sure at all but this might work:

    First, let's work on finding the # of cool numbers <= X, for a given X (then we can get the answer by computing that for B and A-1).

    For a fixed X, we can get the # of cool numbers with a dp[digit][sum1][sum2][alreadyless_bit]

    digit will be the position of the digit we're trying, We will go from most significative to least. sum1 and sum2 are the sums of the two sets. alreadyless_bit tells if we are already strictly less than X, if so, the new digit can be any digit, otherwise, it has to be between 0 and the respective X's digit.

    This counts the cool numbers but it might count each one many times, I don't know if you can avoid that hehe