Pagini recente » Cod sursa (job #515033) | Cod sursa (job #2259888) | Cod sursa (job #396232) | Cod sursa (job #279637) | Cod sursa (job #463674)
Cod sursa(job #463674)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
struct M
{
int v, i;
bool operator < (M const & o) { return ((v<o.v) || ((v==o.v) && (i<o.i))); }
};
int const maxn = 600; typedef int V[maxn]; typedef M W[maxn]; W a; V x, z, d;
int main()
{
ifstream is("barman.in"); int n, i, k, f, g, s, l, r, m, j, q, e, y; is >> n;
for (i=0; n>i; ++i) { is >> a[i].v; a[i].i=i; }
make_heap(&a[0], &a[n]); sort_heap(&a[0], &a[n]);
for (x[0]=i=k=0; n>i; ++i)
{ if ((0<i) && (a[i-1].v!=a[i].v)) { z[k]=i-1; ++k; x[k]=i; } }
z[k]=n-1; ++k; f = maxn * (1+maxn);
for (s=0; n>s; ++s)
{
for(i=g=0; k>i; ++i)
{
l = ((s+x[i])%n); r = ((s+z[i])%n); m=z[i]-x[i];
for ( j=0; m>=j; ++j) { d[(l+j)%n]=0; }
for ( j=0; m>=j; ++j) { d[a[x[i]+j].i]=1; }
q=(l<=r) ? l : 0;
for (j=0; m>=j; ++j)
{ e = a[x[i]+j].i;
if ( ((l<=r) && ((l>e)||(r<e))) || ((l>r) && ((r<e)&&(e<l))) )
{
while (1 == d[q]) {q = (q==r)?l:(1+q); }
y = (e-q); g += (20+((0<y)?y:(-y)));
q = (q==r)?l:(1+q);
}
}
}
if (f>g) { f=g; }
}
ofstream os("barman.out"); os<<f<<endl; return 0;
}