DCP-11: Product Owner’s Problem Back to All Problems

Hard Divide and Conquer > Dynamic Programming

Any product owner (PO) of a company feels that being the PO is a very difficult job. More than coding, managing the programmers and distributing the tasks between various programmers prove to be a tiring task. There are many tasks to be completed and he has a team of talented programmers to do this for him. But the PO always has a problem distributing tasks among them. For a programmer i, the PO wants to give him ***at least*** Xi tasks to complete in a day. But different programmers have different capacities. Any programmer i can do ***at most*** Yi number of tasks in a single day. PO is very aware of every programmer's capability and will not give anyone more work than his maximum capacity. Now he needs your help to tell him the number of ways in which he can distribute the given number of tasks among his team. Input: ------ First line contains T (<=60), number of test cases. Then, each test case begins with a single line containing two space separated integers: N (***number of tasks to be completed***) and M (***number of programmers in his team***). **1 <= N, M <= 100 and 0 <= Xi, Yi <= 100** Then follow M lines. The ith line contains two integers which are the corresponding Xi and Yi. Output: ------- For each test case, print the case number followed by the number of ways of distributing the tasks mod **1000000007**. Sample Input ------------ 2 3 2 0 3 1 3 5 3 0 2 1 3 2 3 Sample Output ------------- Case 1: 3 Case 2: 5

Problem Setter:

Rezwanul Islam Maruf

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C/C++ 1.00
Java 2.00
C# 2.00
PHP 2.00

Problem Stats




# User Language Timing
01 sayedgkm Cpp 0.00s
02 seyedssz Cpp 0.00s
03 Protap_Ghose Cpp 0.00s
04 ovis96 Cpp 0.00s
05 njrafi Cpp 0.00s
06 Salty_Coder Cpp 0.01s
07 dmehrab06 Cpp 0.01s
08 sakib_muhit Cpp 0.03s
09 Shadab Cpp 0.17s
10 Zeronfinity Cpp 0.26s
11 ImagineWarrior Cpp 0.38s
12 jayanto Cpp 0.39s
13 clcrr Cpp 0.39s
14 tariqiitju Cpp 0.39s
15 sazal_dev Cpp 0.39s
16 tareq_7 Cpp 0.39s
17 INUA Cpp 0.40s
18 Mahmudul_Tushar Cpp 0.40s
19 as_couple Cpp 0.40s
20 akazad_cse13_ruet Cpp 0.48s
21 musa Cpp 0.49s
22 spy19 Cpp 0.50s

Your feedback is our precious!

Or call +88 02 9853138 for support