#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

/* The larger this is, the longer the program can compute.
 * But this can use a lot of memory.  Roughly 20 * MAX_STACK bytes + change.
 */
#define MAX_STACK 16777216

/* For extra output define DEBUG 1 */
#define DEBUG 0

/* You should not need to modify anything below this line */

typedef int32_t s32;

int main(int argc, char *argv[])
{
    if (argc != 3) {
        fprintf(stderr, "Usage: %s <M> <N>\n", argv[0]);
        exit(1);
    }

    s32 M = atoi(argv[1]);
    s32 N = atoi(argv[2]);

    if ((M == 4 && N > 1) || (M == 5 && N > 0) || (M > 5)) {
        printf("Warning: It is unlikely that this program will be able to compute A(%d, %d).\n", M, N);
    }
    else if ((M == 3 && N > 10) || (M == 4 && N > 0) || M > 4) {
        printf("Warning: There is likely to be a noticeable delay before the computation of A(%d, %d) completes.\n", M, N);
    }

    /* Pending requests */
    s32 *stack_m = malloc(MAX_STACK * sizeof(s32));
    s32 *stack_n = malloc(MAX_STACK * sizeof(s32));

    /* Previously computed values */
    s32 *known_m = malloc(MAX_STACK * sizeof(s32));
    s32 *known_n = malloc(MAX_STACK * sizeof(s32));
    s32 *known_val = malloc(MAX_STACK * sizeof(s32));

    if (!stack_m || !stack_n || !known_m || !known_n || !known_val) {
        fprintf(stderr, "Sorry, I couldn't allocate enough memory.\n");
        exit(1);
    }

    /* A(0, 0) = 1 by definition.  Don't assume anything else. */
    for (s32 i = 0; i < MAX_STACK; i++) {
        known_m[i] = 0;
        known_n[i] = 0;
        if (i > 0) {
            known_val[i] = 0;
        }
        else {
            known_val[i] = 1;
        }
    }
    s32 kpos = 1;

    /* Initialize the stack with the user-requested M and N */
    s32 spos = 0;
    stack_m[spos] = M;
    stack_n[spos] = N;

    while (spos >= 0) {
        if (DEBUG == 1) {
            printf("> Stack size: %" PRId64 "\n", spos);
        }
        s32 found = -1;
        for (s32 i = 0; i < kpos; i++) {
            if ((stack_m[spos] == known_m[i]) && (stack_n[spos] == known_n[i])) {
                found = i;
                break;
            }
        }
        if (found > -1) {
            if (DEBUG == 1) {
                printf("A(%d, %d) = %d\n", stack_m[spos], stack_n[spos], known_val[found]);
            }
            spos--;
        }
        else {
            /* A(0, n) = n + 1 */
            if (stack_m[spos] == 0) {
                known_m[kpos] = stack_m[spos];
                known_n[kpos] = stack_n[spos];
                known_val[kpos] = known_n[kpos] + 1;
                if (DEBUG == 1) {
                    printf("A(%d, %d) = %d\n", known_m[kpos], known_n[kpos], known_val[kpos]);
                }
                kpos++;
                spos--;
            }
            /* A(m, 0) = A(m - 1, 1) if m > 0 */
            else if (stack_n[spos] == 0) {
                s32 found = -1;
                for (s32 i = 0; i < kpos; i++) {
                    if ((known_m[i] == stack_m[spos] - 1) && (known_n[i] == 1)) {
                        found = i;
                        break;
                    }
                }
                if (found > -1) {
                    known_m[kpos] = stack_m[spos];
                    known_n[kpos] = stack_n[spos];
                    known_val[kpos] = known_val[found];
                    if (DEBUG == 1) {
                        printf("A(%d, %d) = %d\n", known_m[kpos], known_n[kpos], known_val[kpos]);
                    }
                    kpos++;
                    spos--;
                }
                else {
                    spos++;
                    stack_m[spos] = stack_m[spos - 1] - 1;
                    stack_n[spos] = 1;
                }
            }
            /* A(m, n) = A(m - 1, A(m, n - 1)) if m, n > 0 */
            else {
                s32 second = -1;
                for (s32 i = 0; i < kpos; i++) {
                    if ((known_m[i] == stack_m[spos]) && (known_n[i] == stack_n[spos] - 1)) {
                        second = i;
                        break;
                    }
                }
                if (second > -1) {
                    s32 first = -1;
                    for (s32 i = 0; i < kpos; i++) {
                        if ((known_m[i] == stack_m[spos] - 1) && (known_n[i] == known_val[second])) {
                            first = i;
                            break;
                        }
                    }
                    if (first > -1) {
                        known_m[kpos] = stack_m[spos];
                        known_n[kpos] = stack_n[spos];
                        known_val[kpos] = known_val[first];
                        if (DEBUG == 1) {
                            printf("A(%d, %d) = %d\n", known_m[kpos], known_n[kpos], known_val[kpos]);
                        }
                        kpos++;
                        spos--;
                    }
                    else {
                        spos++;
                        stack_m[spos] = stack_m[spos - 1] - 1;
                        stack_n[spos] = known_val[second];
                    }
                }
                else {
                    spos++;
                    stack_m[spos] = stack_m[spos - 1];
                    stack_n[spos] = stack_n[spos - 1] - 1;
                }
            }
        }
    }
    /* Fetch the value we computed above */
    s32 found = -1;
    for (s32 i = 0; i < kpos; i++) {
        if (known_m[i] == M && known_n[i] == N) {
            found = i;
            break;
        }
    }
    if (found > -1) {
        printf("Result: A(%d, %d) = %d\n", M, N, known_val[found]);
    }
    else {
        printf("Sorry, I couldn't compute A(%d, %d).\n", M, N);
    }
    return 0;
}