Pagini recente » Cod sursa (job #100763) | Cod sursa (job #764031) | Cod sursa (job #91120) | Cod sursa (job #818677) | Cod sursa (job #347347)
Cod sursa(job #347347)
#include <stdio.h>
#include <algorithm>
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];
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];
}
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;
}
inline int road_st(int p, int q) {
if (q < p) return p - q;
else return p + n - q;
}
inline int road_dr(int p, int q) {
if (q > p) return q - p;
else return n - p + q;
}
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[t] - 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 += road_st(el[p], poz[x]) + 20;
x--;
}
x = 1;
for (int p = j + 1; p <= el[0]; p++) {
aux += road_dr(el[p], 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;
}