Pagini recente » Cod sursa (job #883318) | Cod sursa (job #569892) | Cod sursa (job #1811256) | Cod sursa (job #584544) | Cod sursa (job #347373)
Cod sursa(job #347373)
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAX_N 610
#define inf 2147000000
int n, add, sol, val;
int A[MAX_N], B[MAX_N], ind[MAX_N], nr[MAX_N], loc[MAX_N];
int poz[MAX_N], el[MAX_N];
void cit() {
freopen("barman.in", "r", stdin);
freopen("barman.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
B[i] = A[i]; loc[i] = i;
}
sort(B + 1, B + n + 1);
}
void perm() {
int aux = A[1];
for (int i = 1; i < n; i++)
A[i] = A[i + 1];
A[n] = aux;
aux = loc[1];
for (int i = 1; i < n; i++)
loc[i] = loc[i + 1];
loc[n] = aux;
}
void solve() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (A[j] == B[i])
nr[i]++;
sol = inf;
for (int k = 1; k <= n; k++) {
int last = 1;
val = 0;
for (int i = 1; i <= n; i++)
if (B[i] != B[i - 1]) {
//voi pune cele nr[t] elemente pe pozitiile last..last + nr[i] - 1
poz[0] = el[0] = 0;
for (int j = last; j <= last + nr[i] - 1; j++)
if (A[j] != B[i])
poz[++poz[0]] = j;
for (int j = 1; j <= n; j++)
if (A[j] == B[i] && (j < last || last + nr[i] - 1 < j))
el[++el[0]] = j;
last = last + nr[i];
add = inf;
for (int j = 0; j <= el[0]; j++) {
int aux = 0, x = 0;
x = poz[0];
for (int p = 1; p <= j; p++) {
aux += abs(loc[el[p]] - loc[poz[x]]) + 20;
x--;
}
x = 1;
for (int p = j + 1; p <= el[0]; p++) {
aux += abs(loc[el[p]] - loc[poz[x]]) + 20;
x++;
}
if (aux < add) add = aux;
}
val += add;
}
if (val < sol) sol = val;
perm();
}
printf("%d\n", sol);
}
int main() {
cit();
solve();
return 0;
}