Pagini recente » Cod sursa (job #2589448) | Cod sursa (job #22636) | Cod sursa (job #619066) | Cod sursa (job #320092) | Cod sursa (job #1746977)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAXN 650
using namespace std;
int n, a[MAXN];
int goal[MAXN], ind[MAXN], viz[MAXN];
vector<int> pos[MAXN];
bool cmp(int x, int y)
{
if (a[x] != a[y]) return a[x] < a[y];
return x < y;
}
void normalizare()
{
int fi[MAXN];
for (int i = 1; i <= n; i++)
goal[i] = i;
sort(goal+1, goal+1+n, cmp);
int nr = 1;
for (int i = 1; i <= n; i++, nr++) {
while (i < n && a[goal[i]] == a[goal[i+1]])
fi[goal[i++]] = nr;
fi[goal[i]] = nr;
}
for (int i = 1; i <= n; i++)
a[i] = fi[i];
//for (int i = 1; i <= n; i++)
//printf("%d ", a[i]);
}
int dist(int i, int j)
{
return max(i-j, j-i);
}
int cupleaza()
{
int toR = 0;
for (int i = 1; i <= n; i++) pos[i].clear(), ind[i] = 0;
for (int i = 1; i <= n; i++)
if (a[i] != goal[i])
pos[goal[i]].push_back(i);
for (int i = 1; i <= n; i++)
if (a[i] != goal[i]) {
toR += 20 + dist(i, pos[a[i]][ind[a[i]]]);
ind[a[i]]++;
}
return toR;
}
void solve()
{
for (int i = 1; i <= n; i++)
goal[i] = a[i];
sort(goal+1, goal+n+1);
int best = cupleaza();
for (int i = 0; i < n; i++) {
for (int i = 1; i <= n-1; i++)
swap(goal[i], goal[i+1]);
best = min(best, cupleaza());
}
printf("%d", best);
}
int main()
{
freopen("barman.in", "r", stdin);
freopen("barman.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
normalizare();
solve();
return 0;
}