Блог пользователя Mehedi33

Автор Mehedi33, 9 лет назад, По-английски
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

the input size if small (the largest factorial you will need is 20!) so here you can generate all the possible factorials and use bitmasking (or recursion) to pre-calculate all possible values and cache them ... then for every case you just output the answer

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I pre-calculate all the value upto 20. But now i cant understand how can i find my desired number .

    I have no idea about bitmasking. Is there any other way ?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Use brute-force. For each number there are two cases — to use or not to use :)

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        If i use brute-force, at some stage summation of fact(num) may exceed my desired n , at that case i may avoid that fact(num) . But can i surely say that at any stage summation of fact(num) will be equal to my desired n ?

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I think that this approach will result in TLE since the limit is 0.5 :) I think it is better to read Caraz96's idea and ask if you misunderstood something in it.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      It is possible to use a greedy approach: since fact(n) > fact(0)+fact(1)+...+fact(n-1) (this is true for each n > 2) you can iterate from the greatest factorial(20!) to the smallest one, if fact[i] is less than or equal to N you must take it, decrease N by fact[i] and proceed with the next factorial. At the end, if N is 0 you found the solution, otherwise it is impossible to obtain N adding factorials.