Function Run Fun

프로그램 명: frf

제한시간: 1 초

우리 모두는 재귀를 사랑합니다. 그렇죠?

여기 인수 세개를 가지는 함수 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)

이 함수를 구현하는 것은 쉽다. 하지만 이를 바로 구현 한다면 적당한 a,b,c ( 예를들어 , a=15,b=15,c=15) 에서는 과도한 호출로 답을 내는데 몇 시간이 걸린다.

입력으로 세 정수 a,b,c 가 입력으로 주어진다.(a,b,c <= 50)

효율적인 w(a,b,c) 를 계산해서 출력 예의 형식으로 출력한다.

입력

1 1 1

출력

w(1, 1, 1) = 2

입력

50 50 50 

출력

w(50, 50, 50) = 1048576

출처:Pacific Northwest 1999