#include "main.h"
#include <chrono>
#include <algorithm>


State::State(std::vector<int> stacks_arg, int _size = -1) {
    stacks = stacks_arg;
    max_width = stacks.size();
    size = 0;
    if (_size == -1) {
        for (int i = 0; i < max_width; i++) {
            size += stacks[i];
        }
    } else {
        size = _size;
    }   
}

int State::sum_depth() {
    int x = 0;
    for (int i = 0; i < max_width; i++) {
        x += stacks[i] * stacks[i];
    }
    return x;
}

State State::copy() {
    return State(stacks, size);
}

void State::print_simple() {
    std::cout << "[ ";
    for (int i = 0; i < max_width; i++) {
        std::cout << stacks[i] << " ";
    }
    std::cout << "]";
}

void State::swap(int i, int j) {
    int tmp = stacks[i];
    stacks[i] = stacks[j];
    stacks[j] = tmp;
}

void State::sort_insertion() {
    for (int i = 1; i < max_width; i++) {
        int key = stacks[i];
        int j = i - 1;
        while (j >= 0 && stacks[j] > key) {
            stacks[j + 1] = stacks[j];
            j = j - 1;
        }
        stacks[j + 1] = key;
    }
}

int State::min_stack(int forbidden) {
    int min_ind = 0;
    int min = 10000;
    for (int i = 0; i < max_width; i++) {
        if (stacks[i] < min && i != forbidden) {
            min = stacks[i];
            min_ind = i;
        }
    }
    return min_ind;
}

void State::add_subset(int i, std::vector<int>& subset) {
    for (int k = 0; k < i; k++) {
        stacks[k] += subset[k];
        size += subset[k];
    }
    for (int k = i+1; k < max_width; k++) {
        stacks[k] += subset[k-1];
        size += subset[k-1];
    }
    sort_insertion();
}

void State::relocate_k(int k, int i1, int i2) {
    stacks[i1] -= k;
    stacks[i2] += k;
}

void State::retrieve(int i, int k = 1){
    stacks[i] -= k;
    size -= k;
}

void State::add(int i, int k = 1){
    stacks[i] += k;
    size += k;
}

int State::step_L(int i, int j) {
    int to_move = stacks[i] - j - 1;
    for (int k = 0; k < to_move; k++) {
        int i_low = min_stack(i);
        relocate_k(1, i, i_low);
    }
    retrieve(i);
    sort_insertion();
    return to_move;
}

big_int Average_cost::average_cost_L(State& s) {
    if (memo_L->find(s) != memo_L->end()) {
        return memo_L->at(s);
    } else if (s.size > 1) {
        big_int total_cost = s.sum_depth() * fact(s.size - 1);
        for (int i = 0; i < s.max_width; i++) {
            for (int j = 0; j < s.stacks[i]; j++) {
                State s2 = s.copy();
                big_int cost = s2.step_L(i,j);
                total_cost += average_cost_L(s2);
            }
        }
        memo_L->insert({s,total_cost});
        return total_cost;
    } else if (s.size == 1) {
        big_int x = 2;
        return x;
    }
}

bool State::operator==(const State& other) const {
    if (other.size != size) {
        return false;
    }
    for (int i = 0; i < max_width; i++) {
        if (stacks[i] != other.stacks[i]) {
            return false;
        }
    }
    return true;
}

void Average_cost::gen_subset_sum_aux(std::vector<int>& subset, int k, int sum, std::vector<std::vector<int>>& result) {
    if (k == 0 && sum == 0) {
        result.push_back(subset);
        return;
    }
    if (sum < 0 || (k==0 && sum > 0)) {
        return;
    }
    for (int i = 0; i <= sum; i++) {
        subset.push_back(i);
        gen_subset_sum_aux(subset, k-1, sum - i, result);
        subset.pop_back();
    }
}

std::vector<std::vector<int>> Average_cost::gen_subset_sum(int sum, int k) {
    std::vector<int> subset;
    std::vector<std::vector<int>> result;
    gen_subset_sum_aux(subset, k, sum, result);
    return result;
}

Average_cost::Average_cost() {
    memo_L = new memo_t();
    memo_opt = new memo_t();
    memo_fact = std::vector<big_int>();
    memo_fact.push_back(1);
}

big_int Average_cost::fact(int n) {
    for (int i = memo_fact.size(); i <= n; i++) {
        memo_fact.push_back(i * memo_fact[i-1]);
    }
    return memo_fact[n];
}

big_int Average_cost::average_cost_opt(State& s, int depth = 0) {
    auto elt = memo_opt->find(s);
    if (elt != memo_opt->end()) {
        return elt->second;
    } else if (s.size > 1) {
        big_int total_cost = 0;
        int to_move;
        big_int best;
        big_int cost;
        for (int i = 0; i < s.max_width; i++) {
            for (int j = 0; j < s.stacks[i]; j++) {
                to_move = s.stacks[i] - j - 1;
                s.retrieve(i,to_move+1);
                best = -1;
                for (std::vector<int> subset : gen_subset_sum(to_move, s.max_width - 1)) {
                    State s2 = s.copy();
                    s2.add_subset(i, subset);
                    cost = average_cost_opt(s2, depth + 1);
                    if (best == -1 || cost < best) {
                        best = cost;
                    }
                }
                s.add(i,to_move+1);
                if (best >= 0) {
                    total_cost += best + to_move * fact(s.size - 1);
                }
            }
        }
        memo_opt->insert({s,total_cost});
        return total_cost;
    } else {
        return 0;
    }
}

int min(int a, int b){
    if (a < b){
        return a;
    } else {
        return b;
    }
}

void backtrack(int n, int w, int start, std::vector<int> &current, std::vector<std::vector<int>> &results) {
    if ((int)current.size() == w) {
        if (n == 0) results.push_back(current);
        return;
    }

    for (int i = min(n, start); i >= 0; --i) {
        current.push_back(i);
        backtrack(n - i, w, i, current, results);
        current.pop_back();
    }
}

std::vector<std::vector<int>> generateSequences(int n, int w) {
    std::vector<std::vector<int>> results;  // now local to this function
    std::vector<int> current;
    backtrack(n, w, n + 1, current, results);
    return results;
}

void check_LINC(int w, int n) {
    Average_cost helper = Average_cost();
    for (auto tab : generateSequences(n, w)) {
        if (tab[0] >= tab[w-1] + 2) {
            State s(tab);
            State t = s.copy();
            t.relocate_k(1,0,w-1);
            t.sort_insertion();
            big_int c1 = helper.average_cost_L(s);
            big_int c2 = helper.average_cost_L(t);
            if (c1 < c2) {
                s.print_simple();
            }
        }
    }
    std::cout << "OPT for " << w << "," << n << "\n";
}

void check_LINC_until(int w) {
    Average_cost helper = Average_cost();
    int n = 0;
    while (1) {
        n++;
        check_LINC(w,n);
    }
}


int main()
{
    using std::chrono::high_resolution_clock;
    using std::chrono::duration_cast;
    using std::chrono::milliseconds;
    int x;
    std::cin >> x;
    check_LINC_until(x);
    return 0;
}