/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static int count = 0;
static int maxDepth = 0;
{
for (int i = 1; i <= 7; i++)
call(i);
}
static void call(int n) {
count = 0;
System.
out.
println("-------------"); System.
out.
printf("tarai(%d,%d,0)%n",
2*n,n
); System.
out.
println(tarai
(2*n,n,
0,
1)); System.
out.
println("count: " + count
); System.
out.
println("depth: " + maxDepth
); }
static int tarai(int x, int y, int z, int d) {
count++;
if (x <= y) {
maxDepth
= Math.
max(maxDepth, d
); return y;
} else {
return tarai(tarai(x-1,y,z,d+1),tarai(y-1,z,x,d+1),tarai(z-1,x,y,d+1),d+1);
}
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXN0YXRpYyBpbnQgY291bnQgPSAwOwoJc3RhdGljIGludCBtYXhEZXB0aCA9IDA7CglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiAoU3RyaW5nW10gYXJncykgdGhyb3dzIGphdmEubGFuZy5FeGNlcHRpb24KCXsKCQlmb3IgKGludCBpID0gMTsgaSA8PSA3OyBpKyspCgkJCWNhbGwoaSk7CgkJCgl9CgkKCXN0YXRpYyB2b2lkIGNhbGwoaW50IG4pIHsKCQljb3VudCA9IDA7CgkJU3lzdGVtLm91dC5wcmludGxuKCItLS0tLS0tLS0tLS0tIik7CgkJU3lzdGVtLm91dC5wcmludGYoInRhcmFpKCVkLCVkLDApJW4iLDIqbixuKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4odGFyYWkoMipuLG4sMCwxKSk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJjb3VudDogIiArIGNvdW50KTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImRlcHRoOiAiICsgbWF4RGVwdGgpOwoJfQoJCglzdGF0aWMgaW50IHRhcmFpKGludCB4LCBpbnQgeSwgaW50IHosIGludCBkKSB7CgkJY291bnQrKzsKCQlpZiAoeCA8PSB5KSB7CgkJCW1heERlcHRoID0gTWF0aC5tYXgobWF4RGVwdGgsIGQpOwoJCQlyZXR1cm4geTsKCQl9IGVsc2UgewoJCQlyZXR1cm4gdGFyYWkodGFyYWkoeC0xLHkseixkKzEpLHRhcmFpKHktMSx6LHgsZCsxKSx0YXJhaSh6LTEseCx5LGQrMSksZCsxKTsKCQl9Cgl9Cn0=
-------------
tarai(2,1,0)
2
count: 9
depth: 3
-------------
tarai(4,2,0)
4
count: 53
depth: 8
-------------
tarai(6,3,0)
6
count: 673
depth: 18
-------------
tarai(8,4,0)
8
count: 12605
depth: 32
-------------
tarai(10,5,0)
10
count: 343073
depth: 50
-------------
tarai(12,6,0)
12
count: 12604861
depth: 72
-------------
tarai(14,7,0)
14
count: 588802013
depth: 98