#include <iostream>
#include <cstdlib>

using namespace std;

/// Tema 1

void Afisare(int n, int *v) {
    for(int i = 0; i < n; i++)
        cout << v[i] << " ";
    cout << "\n";
}

void Interschimbare(int n, int *v) {
    int i, j;
    for(i = 0; i < n-1; i++){
        for(j = i+1; j < n; j++)
            if(v[i] > v[j])
                swap(v[i], v[j]);
        Afisare(n, v);
    }
}

void BubbleSort(int n, int *v) {
    int i, sch, n2;
    n2 = n;
    do {
        sch = 0;
        for(i = 0; i < n-1; i++) {
            if(v[i] > v[i+1]) {
                swap(v[i], v[i+1]);
                sch = i+1;
            }
        }
        n = sch;
        Afisare(n2, v);
    } while(n > 1);
}

void InsertionSort(int n, int *v) {
    int i, j, aux;
    for(int i = 1; i < n; i++) {
        aux = v[i];
        j = i;
        while(j > 0 && v[j-1] > aux) {
            v[j] = v[j-1];
            j--;
        }
        v[j] = aux;
        Afisare(n, v);
    }
}

void SelectionSort(int n, int *v) {
    int i, j, p;
    for(i = 0; i < n; i++) {
        p = i;
        for(j = i; j < n; j++) {
            if(v[j] < v[p])
                p = j;
        }
        if(i != p) swap(v[i], v[p]);
        Afisare(n, v);
    }
}

int CautareSecv(int n, int *v, int x) {
    int i;
    for(i = 0; i < n; i++)
        if(v[i] == x) return i;
    return -1;
}

int CautareBinara(int st, int dr, int n, int *v, int x) {
    ///int m = st + (dr - st) / 2;
    int m = (st + dr) / 2;

    if(v[m] == x) return m;
    if((st >= dr) && (v[m] != x)) return -1;

    if(v[m] > x)       return CautareBinara(st, m-1, n, v, x);
    else if(v[m] < x)  return CautareBinara(m+1, dr, n, v, x);
}

/// Tema 2

/// Ex. 2
void EliminareK(int &n, int *v, int k) {
    int i, j;
    for(i = 0; i < n; i++) {
        if(v[i] == k) {
            for(j = i; j < n-1; j++)
                v[j] = v[j + 1];
            n--;
            return;
        }
    }
}

void EliminareKFull(int &n, int *v, int k) {
    int i, j;
    for(i = 0; i < n; i++) {
        if(v[i] == k) {
            for(j = i; j < n-1; j++)
                v[j] = v[j + 1];
            n--;
            i--;
        }
    }
}

/// Ex. 3
void InsertieK(int &n, int *v, int k, int t) {
    int i, j;
    //int n2 = n;
    for(i = 0; i < n; i++) {
        if(v[i] == k) {
            for(j = n - 1; j > i; j--)
                v[j + 1] = v[j];
            n = n + 1;
            v[i + 1] = t;
            return;
        }
    }
}

void InsertieVector(int &n, int *v, int n_t, int *t, int k) {
    int i, j, l;
    int n2 = n;
    for(i = 0; i < n2; i++) {
        if(v[i] == k) {
            for(j = n2; j > i; j--)
                v[j + n_t] = v[j];
            n = n2 + n_t;

            for(l = 1; l <= n_t; l++)
                v[i + l] = t[l - 1];

            return;
        }
    }
}

/// Ex. 4
int GasireElement(int n, int *v) {
    int i, mx, mn;
    int ap[1000] = {0};

    mx = mn = v[0];
    for(i = 0; i < n; i++) {
        ap[v[i]]++;
        if(mx < v[i]) mx = v[i];
        if(mn > v[i]) mn = v[i];
    }

    for(i = mn; i <= mx; i++)
        if(ap[i] == 1)
            return i;
    return -1;
}

/// Ex. 5
/// a
int PolinomA(int n, int *a, int t) {
    int i;
    int res = a[0];
    int prod = t;
    for(i = 1; i <= n; i++) {
        res += a[i] * prod;
        prod *= t;
    }

    return res;
}

void PolinomB(int n, int *a, int m, int *b, int &n_c, int *c) {
    int i;
    n_c = max(n, m);
    for(i = 0; i < n_c; i++) {
        if(i <= n) c[i] += a[i];
        if(i <= m) c[i] += b[i];
    }
}

int main() {
    int n = 11;
    int v[100] = {7, 3, 5, 1, 2, 3, 9, 10, 4, 6, 8};

    Afisare(n, v);
    cout << "\n";

    /*
    Interschimbare(n, v);
    InsertionSort(n, v);
    BubbleSort(n, v);
    SelectionSort(n, v);

    cout << CautareBinara(0, n-1, n, v, 5);
    cout << "\n";

    EliminareK(n, v, 3);
    EliminareKFull(n, v, 3);

    InsertieK(n, v, 3, 11);

    int n_t = 4;
    int t[4] = {7, 0, 0, 7};
    InsertieVector(n, v, n_t, t, 3);
    */

    Afisare(n, v);
    cout << "\n";


    return 0;
}