#include <iostream>
#include <map>
int const N = 10000000;
class mypair {
public:
int m, n;
mypair(int m, int n) { this->m = m; this->n = n; }
bool operator<(const mypair &r) const {
return (this->m * N + this->n) < (r.m * N + r.n);
}
};
std::map<mypair, int> mpair;
static int c = 0;
static int xmax = 0;
int ack(std::map<mypair, int> &mpair, int m, int n, int x) {
c++;
if (xmax < x)
xmax = x;
if (mpair.find(mypair(m, n)) != mpair.end()) {
goto label;
int r;
r = mpair[mypair(m, n)];
return r;
} else {
label:
int r;
if (m == 0)
r = n + 1;
else if (n == 0)
r = ack(mpair, m - 1, 1, x + 1);
else { r = ack(mpair, m - 1, ack(mpair, m, n - 1, x + 1), x + 1); }
mpair[mypair(m, n)] = r;
return r;
}
}
int main() {
std::cout << ack(mpair, 4, 1, 0) << std::endl;
std::cout << "calls:" << c << ", nest:" << xmax << std::endl;
return 0;
}
/* end */
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWFwPgoKaW50IGNvbnN0IE4gPSAxMDAwMDAwMDsKY2xhc3MgbXlwYWlyIHsKcHVibGljOgogIGludCBtLCBuOwogIG15cGFpcihpbnQgbSwgaW50IG4pIHsgdGhpcy0+bSA9IG07IHRoaXMtPm4gPSBuOyB9CiAgYm9vbCBvcGVyYXRvcjwoY29uc3QgbXlwYWlyICZyKSBjb25zdCB7CiAgICByZXR1cm4gKHRoaXMtPm0gKiBOICsgdGhpcy0+bikgPCAoci5tICogTiArIHIubik7CiAgfQp9OwoKc3RkOjptYXA8bXlwYWlyLCBpbnQ+IG1wYWlyOwpzdGF0aWMgaW50IGMgPSAwOwpzdGF0aWMgaW50IHhtYXggPSAwOwppbnQgYWNrKHN0ZDo6bWFwPG15cGFpciwgaW50PiAmbXBhaXIsIGludCBtLCBpbnQgbiwgaW50IHgpIHsKICBjKys7CiAgaWYgKHhtYXggPCB4KQogICAgeG1heCA9IHg7CgogIGlmIChtcGFpci5maW5kKG15cGFpcihtLCBuKSkgIT0gbXBhaXIuZW5kKCkpIHsKICAgIGdvdG8gbGFiZWw7CiAgICBpbnQgcjsKICAgIHIgPSBtcGFpcltteXBhaXIobSwgbildOwogICAgcmV0dXJuIHI7CiAgfSBlbHNlIHsKICBsYWJlbDoKICAgIGludCByOwogICAgaWYgKG0gPT0gMCkKICAgICAgciA9IG4gKyAxOwogICAgZWxzZSBpZiAobiA9PSAwKQogICAgICByID0gYWNrKG1wYWlyLCBtIC0gMSwgMSwgeCArIDEpOwogICAgZWxzZSB7IHIgPSBhY2sobXBhaXIsIG0gLSAxLCBhY2sobXBhaXIsIG0sIG4gLSAxLCB4ICsgMSksIHggKyAxKTsgfQogICAgbXBhaXJbbXlwYWlyKG0sIG4pXSA9IHI7CiAgICByZXR1cm4gcjsKICB9IAp9CgppbnQgbWFpbigpIHsKICBzdGQ6OmNvdXQgPDwgYWNrKG1wYWlyLCA0LCAxLCAwKSA8PCBzdGQ6OmVuZGw7CiAgc3RkOjpjb3V0IDw8ICJjYWxsczoiIDw8IGMgPDwgIiwgbmVzdDoiIDw8IHhtYXggPDwgc3RkOjplbmRsOwogIHJldHVybiAwOwp9Ci8qIGVuZCAqLwo=