Problem F
Busy Programmer
Input: Standard Input
Output: Standard Output
Our famous programmer Gordov Mia (Mr. Donkey) is having a very busy time in his office. His erratic boss has assigned him to two projects (project MICRO & project GOO) at the same time. Consequently, problems have occurred while making a feasible work schedule for him. The boss needs to submit a report to the CEO specifying the schedule of work for all the resources working under him for a period of 2D days. Gordov must work D days on each project. He doesn’t work more than a single project on a particular day. Gordov must finish the work of the project he started earlier (i.e. on the first day of the schedule) first. As the progress of both the projects depends on him, he can not be away from any project for more than G consecutive days. (of course unless a project is already complete.) For example, if D = 3 & G = 2, there can be ten valid schedules,
|
|
Day 1 |
Day 2 |
Day 3 |
Day 4 |
Day 5 |
Day 6 |
|
1 |
MICRO |
MICRO |
GOO |
MICRO |
GOO |
GOO |
|
2 |
GOO |
GOO |
MICRO |
GOO |
MICRO |
MICRO |
|
3 |
MICRO |
MICRO |
GOO |
GOO |
MICRO |
GOO |
|
4 |
GOO |
GOO |
MICRO |
MICRO |
GOO |
MICRO |
|
5 |
MICRO |
GOO |
MICRO |
MICRO |
GOO |
GOO |
|
6 |
GOO |
MICRO |
GOO |
GOO |
MICRO |
MICRO |
|
7 |
MICRO |
GOO |
MICRO |
GOO |
MICRO |
GOO |
|
8 |
GOO |
MICRO |
GOO |
MICRO |
GOO |
MICRO |
|
9 |
MICRO |
GOO |
GOO |
MICRO |
MICRO |
GOO |
|
10 |
GOO |
MICRO |
MICRO |
GOO |
GOO |
MICRO |
Now, Given D & G, you are to determine the number of possible schedules with the given constraints.
There are around 2400 test cases in the input file. Every test case has two non-negative integers, D & G (D,G<=33) on a line by itself. A case with D = G = -1 terminates the input. This case must not be processed.
For each test case, print a line in the format “Case x: y” where x is the case number & y is the number of possible schedules.
|
3 2 3 1 -1 -1 |
Case 1: 10 Case 2: 2 |
Problemsetter: Mohammad Mahmudur Rahman
Special
Thanks: Abdullah al Mahmud (Satej)