#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const double e = 1e-6;
int c = 0; //compares
int m = 0;

void gen1 (double * a, int n) //in right order
{
    int elem = rand();
    double k = 1000;
    int j = rand();
    for (int i = 0; i < n; i++)
    {
        a[i] = elem / k;
        if (rand() % 2)
        {
            a[i] *= -1;
        }
        k += j;
    }
}

void gen2(double * a, int n) //reversed order
{
    int elem = rand();
    double k = rand();
    int j = rand();
    for (int i = 0; i < n; i++)
    {
        a[i] = k / elem;
        if (rand() % 2)
        {
            a[i] *= -1;
        }
        k += j;
    }
}

void gen3(double * a, int n) //random
{
    int elem = rand();
    double k = 1000;
    for (int i = 0; i < n; i++)
    {
        a[i] = elem / k;
        if (rand() % 2)
        {
            a[i] *= -1;
        }
        elem = rand();
    }
}

void swap(double * b, double * c)
{
    double t = *b;
    *b = *c;
    *c = t;
}

void bubble_sort(double * a, int n)
{
    for (int i = 1; i < n; i++)
    {
        for (int j = n - 1; j >= i; j--)
        {
            c++;
            if (fabs(a[j]) > fabs(a[j - 1]) - e)
            {
                m++;
                swap(a + j, a + j - 1);
            }
        }
    }
}

void shell_sort(double * a, int n)
{
    int h = n / 2; //displacement
    int l, k;
    while (h)
    {
        for (int i = 0; i < h; i++)
        {
            l = n / h; //length of little array
            double elem;
            for(int j = 1; j < l; j++) //insert_sort for array
            {
                elem = a[i + j * h];
                for (k = j - 1; k >= 0 && (fabs(elem) >= fabs(a[i + k * h]) - e); k--)
                {
                    a[i + h + k * h] = a[i + h * k];
                    m++;
                    c++;
                }
                if (k >= 0)
                {
                    c++;
                }
                a[i + h + k * h] = elem;
                m++;
            }
        }
        h = h / 2;
    }
}

int main(void)
{
    int n;
    scanf("%d", &n);
    int type; // 1 - bubble_sort, 2 - shell_sort
    scanf("%d", &type);
    double * a = malloc(n * sizeof(double));
    srand(time(NULL));
    if (type == 1)
    {
        gen1(a, n);
        bubble_sort(a, n);
        printf("%d %d\n", c, m);
        c = m = 0;
        gen2(a, n);
        bubble_sort(a, n);
        printf("%d %d\n", c, m);
        c = m = 0;
        gen3(a, n);
        bubble_sort(a, n);
        printf("%d %d\n", c, m);
        c = m = 0;
        gen3(a, n);
        bubble_sort(a, n);
        printf("%d %d\n", c, m);
        c = m = 0;
    }
    if (type == 2)
    {
        gen1(a, n);
        shell_sort(a, n);
        printf("%d %d\n", c, m);
        c = m = 0;
        gen2(a, n);
        shell_sort(a, n);
        printf("%d %d\n", c, m);
        c = m = 0;
        gen3(a, n);
        shell_sort(a, n);
        printf("%d %d\n", c, m);
        c = m = 0;
        gen3(a, n);
        shell_sort(a, n);
        printf("%d %d\n", c, m);
        c = m = 0;
    }
    free(a);
    return 0;
}