Cod sursa(job #3176156)

Utilizator anast56Anastasia Rosan anast56 Data 26 noiembrie 2023 19:23:38
Problema Litere Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("litere.in");
ofstream fout ("litere.out");

char c, x[10001];

void trans (int ind)
{
    char aux[10001];
    strcpy (aux, x + ind);
    strcpy (x + ind + 1, aux);
    x[ind] = c;
}

int main()
{
    int n, cnt = 0;

    fin >> n;

    for (int i = 1; i <= n; i ++)
    {
        fin >> c;
        int ind;

        if (i == 1) x[0] = c;
        else
        {
            int st = 0, dr = strlen(x) - 1, mij;
            ind = 0;

            while (st <= dr)
            {
                mij = (st + dr) / 2;
                if (x[mij] <= c) ind = mij, st = mij + 1;
                else dr = mij - 1;
            }
            ind ++;
            cnt = cnt + strlen(x) - ind;
            trans(ind);
        }
    }

    fout << cnt;

    return 0;
}