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

Автор learner_cf, 10 лет назад, По-английски

Problem: We are given N boxes in a row. We have to place minimum balls in boxes such that each M consecutive boxes have at least K balls. Find the number of ways of placing balls in boxes. Given N, M, K. 1<=K<=M<=50 M<=N<=10^9 If N = 3, M = 2, K = 1 Ans : 1 If N = 6, M = 3, K = 2 Ans: 6 What is the state of DP ?

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

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

Can you please post the question link ?

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

You can't use dynamic programming. The problem will be solved using matrix exponentiation.

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

are you sure if N = 3, M = 2, K = 1 Ans : 1 ?

all boxes must have at least 1 ball ? you didn't say that !

did you mean each M consecutive boxes or at least one ? ? ? you did not say any thing !