Hide

# Problem CNinety-One

Letâ€™s say you want to write a function that takes a single parameter $n$ and, if $n$ is greater than 100, returns $n$ minus 10, and 91 otherwise. Besides being a somewhat pointless function, it would also be trivial to implement:

if n > 100 then
return n - 10
else
return 91
end if


It turns out there is recursive function, called the McCarthy 91 function, that behaves the same way but which requires multiple recursive calls to produce the final result. The function is defined thusly:

$M(n) = \left\lbrace \begin{array}{l l} n-10 & \text {if }n>100 \\ M(M(n+11)) & \text {if }n\leqslant 100 \end{array}\right.$

Even though this function may seem pointless, its complex recursive pattern makes it a useful test case for programming languages and formal proof systems.

Your solution must use a RECURSIVE function, using the definition presented above.

On the exam, any other type of solution will receive zero points!

EVEN IF KATTIS JUDGES IT AS CORRECT!

## Input

The input contains a single positive integer: $n$.

## Output

The output is the value of $M(n)$

Sample Input 1 Sample Output 1
1000

990

Sample Input 2 Sample Output 2
20

91

Sample Input 3 Sample Output 3
1

91

Sample Input 4 Sample Output 4
1872681

1872671

Hide