// Lab3
// V2

#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <malloc.h>

int task1(int n, int **A);
void task2(int n, int **A);

int main()
{
    int n, i, j;

    printf("Array size: ");
    scanf("%d", &n);

    int **A = (int **)malloc(n * sizeof(int *));
    for (i = 0; i < n; i++)
    {
        A[i] = (int *)malloc(n * sizeof(int));
    }

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            printf("\nA[%d][%d]= ", i, j);
            scanf("%d", &A[i][j]);
        }
    }

    printf("\n=== Source array ====\n");
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            printf("%6d", A[i][j]);
        }
        printf("\n");
    }

    printf("\n=== Task 1 ====\n");
    int count;
    count = task1(n, A);
    printf("Count columns = %d\n", count);


    printf("\n=== Task 2 ====\n");
    task2(n, A);
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            printf("%6d", A[i][j]);
        }
        printf("\n");
    }

    getch();
    for (i = 0; i < n; i++)
    {
        free(A[i]);
    }
    free(A);
    return 0;
}

int task1(int n, int **A)
{
    int i, j, countColumns = 0, countZeros;

    for (i = 0; i < n; i++)
    {
        countZeros = 0;
        for (j = 0; j < n; j++)
        {
            if (A[j][i] == 0)
            {
                ++countZeros;
            }
        }
        if (countZeros == 0)
        {
            ++countColumns;
        }
    }

    return countColumns;
}

void task2(int n, int **A)
{
    int i, j, k, f1, f2;

    int *S = (int *)malloc(n * sizeof(int));

    int **B = (int **)malloc(n * sizeof(int *));

    for (i = 0; i < n; i++)
    {
        B[i] = (int *)malloc(n * sizeof(int));
    }

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            B[i][j] = A[i][j];
        }
    }

    for (i = 0; i < n; i++)
    {
        f1 = f2 = 0;
        for (j = 0; j < n - 1; j++)
        {
            if (A[j][i] <= A[j + 1][i]) ++f1;
            if (A[j][i] >= A[j + 1][i]) ++f2;
        }
        if (f1 != n - 1 && f2 != n - 1)
        {
            // линейный выбор с подсчетом
            int t;

            for (j = 0; j < n; j++)
            {
                S[j] = 0;
            }

            for (j = 0; j < n - 1; j++)
            {
                t = 0;
                for (k = j + 1; k < n; k++)
                {
                    if (A[j][i] < A[k][i]) ++S[k];
                    else ++t;
                }
                S[j] += t;
            }
            for (j = 0; j < n; j++)
            {
                A[S[j]][i] = B[j][i];
            }
        }
    }


    for (i = 0; i < n; i++)
    {
        free(B[i]);
    }
    free(B);
    free(S);
}