Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1387
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 brides 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
Sample Output Case 1: 7
Case 2: 17
Case 3: 41
Case 4: 97
Case 5: 225
Case 6: 513
Case 7: 1153
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
unsigned long long memo[62][62];
unsigned long long trib(int n, unsigned int back)
{
if(n <= 1) return 1;
else if(memo[n][back] != 0) return memo[n][back];
// start with 1 as this function is called
unsigned long long sum = 1;
for(int i=1;i < =back;i++) sum += trib(n-i,back);
return memo[n][back] = sum;
}
int main()
{
int a,b,tc=1;
while(scanf("%d %d",&a,&b) != EOF>{
if(a > 60) break;
printf("Case %d: %llu\n",tc++,trib(a,b));
}
}
Input
4 4
5 5
6 6
7 7
8 8
9 9
61 61
Output
Case 2: 17
Case 3: 41
Case 4: 97
Case 5: 225
Case 6: 513
Case 7: 1153
Demonstration
UVA Online Judge solution - 10446-The Marriage Interview - UVA Online Judge solution in C,C++,java