#include <cstdlib>
#include <stdio.h>
using namespace std;
int N = 4;
int* BASE = new int[N + 1];
int* TOP = new int[N];
int* OLDTOP = new int[N];
int* NEWBASE = new int[N];
int* CONTENTS = new int[20];
int* D = new int[N];
int INC = 0;
float T(float a, float b, float q, int d) {
    return q + a + d*b;
}
int toInt(float i) {
    return (int) i;
}
//R3/R5 - ïåðåìåùåíèå ñïèñêà âíèç/ââåðõ
void moving(int j, int direction) {
    int q = direction * (NEWBASE[j] - BASE[j]);
    if (direction < 0) {
        for (int l = BASE[j] + 1; l <= TOP[j]; l++) {
            CONTENTS[l + q * direction] = CONTENTS[l];
            CONTENTS[l] = 0;
        }
    } else {
        for (int l = TOP[j]; l >= BASE[j] + 1; l--) {
            CONTENTS[l + q * direction] = CONTENTS[l];
            CONTENTS[l] = 0;
        }
    }
    BASE[j] = NEWBASE[j];
    TOP[j] = TOP[j] + direction*q;
}
//R2/R4 - ïîèñê íà÷àëà ïåðåìåùåíèÿ âíèç/ââåðõ
void searchBeganMoving(int j, int direction) {
    int q = 0;
    while (1<2) {
        j += direction;
        if (j > N - 1) {
            searchBeganMoving(j, -direction);
            return;
        }
        if (j == 0 && direction < 0) {
            //Ïðåêðàùåíèå àëãîðèòìà
            return;
        }
        if (direction * NEWBASE[j] < BASE[j] * direction) {
            moving(j, -direction);
        }
    }
}
void algR() {
    searchBeganMoving(0, 1);
}
int getNewBase(int index, float t, float q) {
    return (NEWBASE[index - 1] + TOP[index - 1] - BASE[index - 1] + toInt(t) - toInt(q));
}
void algG(int index) {
    int sum = 20;
    for (int i = 0; i < 4; i++) {
        sum -= (TOP[i] - BASE[i]);
        D[i] = TOP[i] - OLDTOP[i];
        INC += D[i];
    }
    if (sum > 0) {
        float a = 0.1 * sum / 4;
        float b = 0.9 * sum / INC;
        NEWBASE[0] = BASE[0];
        float t = 0, q = 0;
        for (int j = 1; j < 4; j++) {
            t = T(a, b, q, D[j - 1]);
            NEWBASE[j] = getNewBase(j, t, q);
            q = t;
        }
        --TOP[index];
        algR();
        ++TOP[index];
        CONTENTS[TOP[index]] = index + 1;
    } else {
        //Ðàáîòà íå ìîæåò áûòü ïðîäîëæåíà
        printf("Ðàáîòà íå ìîæåò áûòü ïðîäîëæåíà\n");
        return;
    }
}
void addToStack(int indexOfStack) {
    TOP[indexOfStack] += 1;
    if (TOP[indexOfStack] > BASE[indexOfStack + 1]) {
        algG(indexOfStack);
    } else {
        CONTENTS[TOP[indexOfStack]] = indexOfStack + 1;
    }
}
int main(int argc, char** argv) {
    //Óñòàíàâëèâàåì íà÷àëüíûå ïàðàìåòðû
    BASE[0] = -1;
    BASE[1] = 2;
    BASE[2] = 6;
    BASE[3] = 8;
    OLDTOP[0] = TOP[0] = 0;
    OLDTOP[1] = TOP[1] = 3;
    OLDTOP[2] = TOP[2] = 6;
    OLDTOP[3] = TOP[3] = 8;
    BASE[4] = 19;
    CONTENTS[0] = 1;
    CONTENTS[3] = 2;
    // âûïîëíÿåì àëãîðèòìû I4I3I3I3
    addToStack(3);
    addToStack(2);
    addToStack(2);
    addToStack(2);
    //Ðåçóëüòàò
    for (int i = 0; i < N; i++) {
        printf("Base[%i] = %i  Top[%i] = %i \n",i, BASE[i],i,TOP[i]);
    }
     printf("\n\nÊîíå÷íûé ðåçóëüòàò:\n");
    for (int i = 0; i < 20; i++) {
        printf("%i ", CONTENTS[i]);
    }
    printf("\n\n\n");
    return 0;
}