/* 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,0,%d)%n",n,n
+1); System.
out.
println(tarai
(n,
0,n
+1,
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);
}
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXN0YXRpYyBpbnQgY291bnQgPSAwOwoJc3RhdGljIGludCBtYXhEZXB0aCA9IDA7CglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiAoU3RyaW5nW10gYXJncykgdGhyb3dzIGphdmEubGFuZy5FeGNlcHRpb24KCXsKCQlmb3IgKGludCBpID0gMTsgaSA8PSA3OyBpKyspCgkJCWNhbGwoaSk7CgkJCgl9CgkKCXN0YXRpYyB2b2lkIGNhbGwoaW50IG4pIHsKCQljb3VudCA9IDA7CgkJU3lzdGVtLm91dC5wcmludGxuKCItLS0tLS0tLS0tLS0tIik7CgkJU3lzdGVtLm91dC5wcmludGYoInRhcmFpKCVkLDAsJWQpJW4iLG4sbisxKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4odGFyYWkobiwwLG4rMSwxKSk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJjb3VudDogIiArIGNvdW50KTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImRlcHRoOiAiICsgbWF4RGVwdGgpOwoJfQoJCglzdGF0aWMgaW50IHRhcmFpKGludCB4LCBpbnQgeSwgaW50IHosIGludCBkKSB7CgkJY291bnQrKzsKCQlpZiAoeCA8PSB5KSB7CgkJCW1heERlcHRoID0gTWF0aC5tYXgobWF4RGVwdGgsIGQpOwoJCQlyZXR1cm4geTsKCQl9IGVsc2UgewoJCQlyZXR1cm4gdGFyYWkodGFyYWkoeC0xLHkseixkKzEpLHRhcmFpKHktMSx6LHgsZCsxKSx0YXJhaSh6LTEseCx5LGQrMSksZCsxKTsKCQl9Cgl9Cn0=
-------------
tarai(1,0,2)
2
count: 5
depth: 2
-------------
tarai(2,0,3)
3
count: 17
depth: 5
-------------
tarai(3,0,4)
4
count: 57
depth: 9
-------------
tarai(4,0,5)
5
count: 213
depth: 14
-------------
tarai(5,0,6)
6
count: 893
depth: 20
-------------
tarai(6,0,7)
7
count: 4137
depth: 27
-------------
tarai(7,0,8)
8
count: 20885
depth: 35