/** This code is in the public domain 
 If you don't want to link libstdc++ with your binary, compile like this:
  g++ -c treeverse.c
  and link with gcc the object treeverse.o.

  -DDEBUG: print debuging infos on what treeverse is doing
  -DMAIN: define a main routine to test the code
   g++ -o treeverse -DMAIN -DDEBUG treeverse.cc

*/

#include <string.h>
#include <cstdio>
#include <cmath>
#include <cassert>

typedef signed long long int llint;

#ifndef _STACK_SIZE
#define _STACK_SIZE 64
#endif
/* Hack so as to not link with libstdc++ */
int __gxx_personality_v0;

/** A templated clas to hold the stack needed for 
  the automate implemented in reverse
  @param T a type to hold in the stack
  @param size the max size of the stack
 */
template <typename T, int size> struct stack {
    // Members
    // Elements
    T array[size];
    int pos;
    
    // Constructor
    stack() : pos(-1)  {}
    
    // Methods
    T &look() 
    { 
        return array[pos];
    }
    T pop() 
    { 
        pos--;
        return array[pos+1];
    }
    void push(T car) {
        pos++;
        array[pos] = car;
    }
    bool empty() {
        return pos == -1;
    }
};


/** Compute the factorial of n
  @param n a long long integer
 */
llint fact(llint n) {
    assert(n >= 0);
    if (n <= 1)
        return 1;
    return fact(n-1)*n;
}
/** Return  /     \ this a binomial law.
            | s+t |
            |  t  |
            \     /
  @param s number of snapshots
  @param t number of reexecution
 */
unsigned int beta(unsigned int s,unsigned int t)
{
    if (s > 0 && t > 0) {
       unsigned int ret = 1;
       for (int i = 1; i <= s; ++i) {
            ret *= t+i;
            ret /= i;
       }
       return ret;
    }
    return fact(s+t)/(fact(s)*fact(t));
}

/** Find the biggest t so that beta(s,t) < m
  @param s the number of checkpoints that can be used
  @param l the length of the evolution to reverse */
static unsigned int find_max_t_under (unsigned int s, unsigned int l) {
    llint c;
    unsigned int t = 0;
    int incr = 1;
    static unsigned int last = 0;


    if (l <= s)
        return 0;
    /* Try to begin with the last result... */
    if (last > 0) 
    {
        t = last;
        if (beta (s, t) > l) 
        {
            do {
                t--;
                c = beta (s, t);
            } while (t > 0 && c > l);
            return t+1;
        }
    }
    else {

        do {
            t++;
            c = beta (s, t);
        } while (c < l);
        return t-1;
    }
}  

unsigned int choose_m_hat (unsigned int s, unsigned int m) {
    unsigned int t = find_max_t_under (s, m);

    return beta (s, t);
}

struct arg 
{
    // member methods
    arg() {}
    arg(int a, int b,int c, int state) 
        : s(a), m(b), start(c), state(0) {}
    // member variables
    int s, m, start, state, m_hat;
};

enum { rev, finish, forw, pop, look, takeshot };


#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif

/** A non-reentrant implementation of the treeverse
 checkpointing scheme, this function use a global state to
 drive a little automaton, the first
 call initialize it with the value in s and m.
 out is an output parameter when there is forward sweeps
 to do. 
 @param s the maximum number of snapshots to do
 @param m the length of the evolution */

int treeverse(int s, int m, int *out) {
    using namespace std;
    int start;

    static stack<struct arg,_STACK_SIZE> args;


    if (args.empty())
        args.push(arg(s,m,0,0));

    while (! args.empty()) {
        arg &last = args.look();

        s = last.s;
        m = last.m;
        start = last.start;
        int &state = last.state;
        int &m_hat = last.m_hat;

        switch (state) {
            case 0:
                if (m == 1) {
                    state = 10;
                    debug("Reverse %d\n", start+m);
                    return rev;
                }
                if (s > 1) {
                    m_hat = choose_m_hat (s, m);
                    if (m_hat != 0) {
                        debug("Forward until %d\n", start+m_hat);
                        *out = m_hat;
                        state = 1;
                        return forw;
            case 1:
                        debug("Takeshot %d\n", start+m_hat);
                        state = 2;
                        return takeshot;
            case 2:
                        state = 3;
                        args.push(arg(s-1, m-m_hat, start+m_hat, 0));
                        continue;
            case 3:
                        state = 4;
                        debug("Remove shot %d\n", start+m_hat);
                        return pop;
            case 4:
                        state = 5;
                        debug("Look at shot %d\n", start);
                        return look;
            case 5:
                        state = 10;
                        args.push(arg(s, m_hat, start, 0));
                        continue;
                    } else
                        debug ("ca arrive\n");
                } else {
                    static int j;

                    for (j = m; j > 0; --j) 
                    {
                        if (j != m) 
                        {
                            state = 6;
                            debug("Look at shot %d\n", start);
                            return look;
                        }
            case 6:
                        if (j != 1) 
                        {
                            state = 7;
                            debug("Forward until %d\n", start+j-1);
                            *out = j-1;
                            return forw;
                        }
            case 7:
                        state = 8;
                        debug("Reverse %d\n", start+j);
                        return rev;
            case 8:
                        ;;
                    }
                }
            case 10:
                ;;
        }
        args.pop();
    }
    return finish;
}

#include <cstdlib>

#ifdef MAIN
int main (int argc, char **argv) {
    int s, l;
    assert(argc > 2);
    s = atoi(argv[1]);
    l = atoi(argv[2]);
    int ret, out;
    int etat[100];
    int where = 1;
    int last[100] = {1}, j = 0;

    memset (etat, 0, sizeof(etat));

    while ((ret = treeverse(s,l,&out)) != finish) {
        switch(ret) {
            case forw:
                {
                    for (int i = 0; i < out; ++i) {
                        etat[where]++;
                        where++;
                    }
                    break;
                }
            case rev:
                //reverse
                break;
            case takeshot:
                ++j;
                last[j] = where;
                //PUSH
                break;
            case pop:
                //POP
                where = last[j];
                --j;
                break;
            case look:
                //LOOK
                where = last[j];
                break;
        }
    }
    for (int u = 0; u < 60; ++u)
        printf("%d %d\n", u, etat[u]);
    printf ("t = %d\n", find_max_t_under(s,l)+1);
}

#endif
#ifdef DUMPENUM
int main() {
  char *name[] = { "REVERSE", "FINISH", "FORWARD", "POP",
  "LOOK", "TAKESHOT" };
  int value[] = { rev, finish, forw, pop, look, takeshot };

  for (int i = 0; i < sizeof(name)/sizeof(name[0]); ++i)
      printf("      %s = %d\n", name[i], value[i]);
}
#endif