Pagini recente » Cod sursa (job #1443103) | Cod sursa (job #327755) | Cod sursa (job #926159) | Cod sursa (job #283420) | Cod sursa (job #1371559)
#include <fstream>
using namespace std;
ifstream f("litere.in");
ofstream g("litere.out");
long long N,Result,Aux[10005];
char S[10005];
void Read()
{
f>>N;
int i;
for(i=1;i<=N;i++)
f>>S[i];
}
void DEI(int Left,int Right)
{
if(Right==Left)
return;
int Mid=(Left+Right)/2;
DEI(Left,Mid);
DEI(Mid+1,Right);
int i=Left,j=Mid+1,k=0,Number=0;
while(i<=Mid && j<=Right)
{
if(S[i]>S[j])
Number++,Aux[++k]=S[j++];
else
Aux[++k]=S[i++],Result+=Number;
}
if(i<=Mid)
for(;i<=Mid;i++)
Aux[++k]=S[i],Result+=Number;
if(j<=Right)
for(;j<=Right;j++)
Aux[++k]=S[j];
for(i=1;i<=k;i++)
S[i+Left-1]=Aux[i];
}
int main()
{
Read();
DEI(1,N);
g<<Result<<"\n";
int i;
/*for(i=1;i<=99999;i++)
g<<i<<" ";
g<<1<<"\n";*/
return 0;
}