#ifndef MAIN_H
#define MAIN_H

#include <vector>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <unordered_map>
#include <gmpxx.h>

typedef mpz_class big_int;

class State {
public:
    std::vector<int> stacks;
    int size;
    int max_width;

    State(std::vector<int> stacks, int _size);
    void print_simple();
    State copy();
    void swap(int i, int j);
    void sort_insertion();
    int min_stack(int forbidden);
    void relocate_k(int k, int i1, int i2);
    void retrieve(int i, int k);
    void add(int i, int k);
    void step_L(int i, int j);
    bool operator==(const State& other) const;
    int sum_depth();
};

typedef std::unordered_map<State,big_int> memo_t;

namespace std {
    template <>
    struct hash<State> {
        size_t operator()(const State& s) const {
            size_t hash_value = 0;
            for (int stack : s.stacks) {
                hash_value ^= std::hash<int>()(stack) + 0x9e3779b9 + (hash_value << 6) + (hash_value >> 2);
            }
            return hash_value;
        }
    };
}

class Average_cost {
public:
    std::vector<memo_t*> memo_L;
    memo_t* memo_opt;
    std::vector<big_int> memo_fact;


    Average_cost();
    big_int fact(int n);
    std::vector<std::vector<int>> gen_subset_sum(int sum, int forbidden);
    void gen_subset_sum_aux(std::vector<int>& subset, int forbidden, int sum, std::vector<std::vector<int>>& result);
    big_int average_cost_L(State& s);
    big_int average_cost_opt(State& s, int depth);

};

#endif // MAIN_H