1579. Function Run Fun

We all love recursion! Don't we?

Consider a three-parameter recursive function w(a, b, c):

· if a ≤ 0 or b ≤ 0 or c ≤ 0, then w(a, b, c) returns: 1

· if a > 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)

· if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) – w(a, b-1, c)

· otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) – w(a-1, b-1, c-1)

This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion.

Input. The input for your program will be a series of integer triples, one per line, until the end-of-file flag of -1 -1 -1. Using the above technique, you are to calculate w(a, b, c) efficiently and print the result.

Output. Print the value for w(a, b, c) for each triple.

Sample Input

1 1 1

2 2 2

10 4 6

50 50 50

-1 7 18

-1 -1 -1

Sample Output

w(1, 1, 1) = 2

w(2, 2, 2) = 4

w(10, 4, 6) = 523

w(50, 50, 50) = 1048576

w(-1, 7, 18) = 1

РЕШЕНИЕ

графы – максимальное паросочетание

Анализ алгоритма

Поскольку вычиления следует проводить для 0 ≤ a, b, c ≤ 20, то реализуем рекурсию с запоминанием значений в трехмерном массиве: m[a][b][c] = w(a, b, c).

Реализация алгоритма

#include <stdio.h>

#include <string.h>

#define MAX 21

int m[MAX][MAX][MAX];

int w(int a, int b, int c)

{

if((a <= 0) || (b <= 0) || (c <= 0)) return 1;

if((a > 20) || (b > 20) || (c > 20)) return w(20,20,20);

if (m[a][b][c] != -1) return m[a][b][c];

return m[a][b][c] = ((a < b) && (b < c)) ?

w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c) :

w(a-1,b,c) + w(a-1,b-1,c) +

w(a-1,b,c-1) - w(a-1,b-1,c-1);

}

int main(void)

{

int a, b, c;

memset(m,-1,sizeof(m));

while(1)

{

scanf("%d %d %d", &a,&b,&c);

if((a == -1) && (b == -1) && (c == -1)) break;

printf("w(%d, %d, %d) = %d\n", a, b, c, w(a,b,c));

}

return 0;

}