DCP-131: Contest Prize Back to All Problems

Medium Divide and Conquer > Dynamic Programming

Suppose this year there are K students to participate in ACM ICPC Dhaka Regional 2016 from your university. So, you arranged a contest at DevSkill to find the best from bests. After the completion, every one of the K participants can get a rank between 1 to K, and there are no two students whose ranks are the same. To enable all the K students to participate in the contest, your university decide to distribute scholarship to the K participants according to their ranks. At first your university authorities provide N scholarship which are the same, and then distribute the N scholarships with the rules of this: 1. **The number of scholarships the student ranking i gets cannot be less than the number of scholarships the student ranking i +1 gets.** 2. **Every student at lest gets one scholarship.** 3. **At last there is no scholarship left.** ---------- If N=4 and K=3, there are only one way to distribute the scholarships: the student ranking 1 gets 2 scholarships, the student ranking 2 gets 1 scholarship, and the student ranking 3 gets 1 scholarship. Now give the N and K, you just tell me after the competition, how many different ways to distribute the N scholarships to the K participants. As the result may be very large, print the result module 1000000009 for the output. Input: ------ The first line of input is the number of test cases **(1 ≤ T ≤ 1000)**. For each test case: There is only one line with two integers: **N (1≤ N ≤1000)** and **K (1 ≤ K ≤ 1000)** Output: ------- For each test case, output one line containing "Case x: “, where x is the test case number, followed by the expected answer.See the sample I/O. Sample Input ------------ 2 4 3 10 3 Sample Output ------------- Case 1: 1 Case 2: 8

Problem Setter:

Rezwanul Islam Maruf

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 1.00
Go 1.00
Java 1.00
JavaScript 1.00
Objective-C 1.00
Perl 1.00
PHP 1.00
Python 1.00
Python3 1.00
Ruby 1.00
VB.Net 1.00

Problem Stats




# User Language Timing
01 feodorv C 0.02s
02 phoenix71 Cpp 0.07s
03 kazinayeem Cpp14 0.33s
04 sahedsohel Cpp14 0.50s
05 Robbinb1993 Cpp 0.73s
06 Morass Cpp14 0.81s

Your feedback is our precious!

Or call +88 02 9853138 for support