Problem C
The Marriage Interview ;-)
Input: standard input
Output: standard output
Time Limit: 2 seconds
Tanbir has recently got married with Nupa. But the steps prior to this event were not easy. He had to submit a novel like curriculum vitae and also he had to face a long interview. A senior computer engineer from the bride’s family took the interview. Just before the interview Tanbir solved a lot of problems from Valladolid Site and many packing problems of Erich Friedman and did well on most parts of the interview. But he had a tough time solving a different type of problem. It may be mentioned that Tanbir loved (!) to solve Geometric (Problem-setter of Problem H of this contest) and Parsing Problems. After the interview Tanbir went to one of his problem-setter friends to discuss about the problem. Tanbir and his so-called veteran problem-setter friend solved that problem correctly (hopefully) in seven days and thirteen nights (!). Now here is that problem for you (Who knows you may have to face a similar interview on a similar occasion in near future!!! Very few of you may arrange such an interview).
You can see a function named trib() below. This function is called with two-integer parameter from main() function.
/*
__int64 is a 64-bit integer data type in Visual C++. So the
following code was written in Visual C++.
*/
typedef unsigned __int64
datatype;
datatype count;
datatype trib(int n,
unsigned int back)
{
datatype sum=0;
int i;
count++;
if(n<=0) return 0;
if(n==1) return 1;
for(i=1;i<=back;i++)
sum+=trib(n-i,back);
return sum;
}
void main(void)
{
count=0;
trib(5,5);
printf(“%I64u\n”,count);
}
If you test you will find that the function trib() is invoked 41 times when it is called from the main function as trib(5, 5). You will have to determine the number of times the function is invoked for different values of n and back.
Input
The input file contains several lines of input. Each line contains two integers n(n<=61) and back(back<=60).
Output
For each line of input produce one line of output. This line contains the case number and then an integer which denotes the number of times the trib() function is invoked for the corresponding input values of n and back. Input is terminated by a case where the value of n is greater than 60. This line should not be processed.
Sample
Input
3 3
4 4
5 5
6 6
7 7
8 8
9 9
61
61
Case 1: 7
Case
Case
Case 4: 97
Case 5: 225
Case 6: 513
(Problem-setter:
Shahriar Manzoor, ACM Valladolid Online Judge)