Cerința

Să se scrie funcția cu următorul antet:

void Insert(int a[], int &n)

Funcția primește ca parametri un vector a de numere naturale și n – numărul elementelor vectorului. Să se insereze după fiecare număr impar dublul său.

Restricții și precizări

• după inserarea de elemente, este garantat că n va avea lungimea cel mult 800.000
• inițial vectorul are cel puțin un element
• 0 ≤ a[i] ≤ 1.000.000, pentru orice i=0,n-1.
• vectorul este indexat de la 0 la n-1
• este garantat că vectorul a va putea memora în final toate elementele inițiale și cele inserate

Exemplu

Dacă n = 5 și a = (22,5,7,8,11), atunci Insert(a, n) trebuie să obțină n = 8 și a = (22,5,10,7,14,8,11,22)

Important

Soluţia propusă va conţine definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

void Insert(int a[], int &n){
    int cnt = 0;
    for(int i = 0; i < n; ++i)
        if(a[i] % 2 == 1)
            cnt++;

    for(int i = n + cnt - 1, j = n - 1; i >= 0, j >= 0; --i, --j){
        if(a[j] % 2 == 1){
            a[i] = a[j] * 2;
            a[i-1] = a[j];
            i--;
        }
        else
            a[i] = a[j];
    }
    /*
        5
        1 2 3 4 5
        cnt = 3;
        i = 8, j = 5;
        daca a[j] este impar -> 5 10 i--;
        i--, j--;
        i = 6, j = 4;
        daca a[j] este par -> il pun pe 4 normal in sir, la pozitia i = 6;
        i--, j--;
        i = 5, j = 3;
        daca a[j] este impar -> 3 6 i--;
        i--, j--; 1 2 3 3 6 4 5 10
        i = 3, j = 2;
        daca a[j] este par -> il pun pe 2 normal in sir, la pozitia i = 3;
        i--, j--;
        i = 2, j = 1;
        daca a[j] este impar -> 1 2 i--;
        i--, j--;
        i = j = 0;
        1 2 2 3 6 4 5 10
    */

    n += cnt;

}