Pagini recente » Cod sursa (job #812002) | Cod sursa (job #2370823) | Cod sursa (job #66919) | Cod sursa (job #2511933) | Cod sursa (job #2342846)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
char a[10005], b[10005];
int n, cnt;
ifstream fin("litere.in");
ofstream fout("litere.out");
int Int(int st, int m, int dr)
{
int i, j, k;
i = st; j = m + 1; k = 0;
while(i <= m && j <= dr)
if(a[i] <= a[j])b[++k] = a[i++];
else
{
cnt += (m - i + 1);
b[++k] = a[j++];
}
while(i <= m)
b[++k] = a[i++];
while(j <= dr)
b[++k] = a[j++];
j = 1;
for(i = st; i <= dr; i++)
a[i] = b[j++];
}
void MSort(int st, int dr)
{
if(dr - st <= 1)
{
if(a[st] > a[dr])
{
cnt++;
swap(a[st], a[dr]);
}
}
else
{
int m = (st + dr) / 2;
MSort(st, m);
MSort(m + 1, dr);
Int(st, m, dr);
}
}
int main()
{
int i;
fin >> n;
fin.get();
for(i = 1; i <= n; i++)
fin >> a[i];
MSort(1, n);
fout << cnt;
return 0;
}