All Tracks Algorithms Dynamic Programming Problem

Dragon's Gift



John Snow recently discovered his blood relationship with Daenerys Targaryen, so he wanted to meet her and tell the entire truth. John has already heard about the dragons of Daenerys, so he decided to take gifts for the dragons.

He knew dragons love to eat chocolates, Yes, Dragons too love the chocolates :) . However, they get furious if they see less than 'm' chocolates at a time.

John brought ‘n’ number of chocolates and infinite number of boxes from the market. John asked his intelligent friend Samwell Tarly to put chocolates in the boxes in such a way that opening a gift box will not make the dragon furious.

Samwell is ready to do the task, but wonders in how many ways he can put the chocolates into the boxes such that dragons don't become furious after opening the box. Since, Samwell Tarly is in hurry, as he has to shoot for the next episode, can you quickly tell him the number of ways he can put the chocolates inside the boxes.

See sample test explanation for more details.

Input : First line contains an integer ‘T’, i.e. the number of test cases.

Each test case has two spaced integers ‘n’ and ‘m’, i.e. the total no. of chocolates and the minimum no. of chocolates to be put in each box repectively.

Output : A single new line containing the number of ways in which Samwell Tarly can put the chocolates inside the boxes.

Constraints :

  • 1<=T<=250
  • 1<=n,m<=250
5 1

There are 5 chocolates and for not making dragons furious, each box must have at least 1 chocolate in it. There can be 7 number of ways to do this as described below :

  • 1,1,1,1,1 - Five boxes each having 1 chocolate each.
  • 1,1,1,2 - Four boxes, three having 1 chocolate each and last one having 2 chocolates.
  • 1,1,3 - Three boxes, two having 1 chocolate each and last one having 3 chocolates.
  • 1,2,2 - Three boxes, one having 1 chocolate while remaining having two chocolates each.
  • 1,4 - Two boxes, one having 1 chocolate while other having 4 chocolates.
  • 2,3 - Two boxes, one having 2 chocolates, other having 3 chocolates.
  • 5 - One box, having all 5 chocolates
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in

ABV- Indian Institute of Information Technology and Management, Gwalior

Challenge Name

CodeMaze v3.0

View All Notifications