Pagini recente » Cod sursa (job #618953) | Cod sursa (job #2339144) | Cod sursa (job #2606661) | Cod sursa (job #2611951) | Cod sursa (job #2244280)
#include <stdio.h>
#define NMAX 600
#define INF 1 << 30
int v[1 + NMAX];
int s[1 + NMAX];
int ok[1 + NMAX];
int n;
int ab( int x ) {
if ( x < 0 )
x = -x;
return x;
}
void qsort ( int st, int dr, int *arr ) {
int b = st, e = dr;
int mid = arr[( st + dr ) / 2];
while ( b <= e ) {
while ( arr[b] < mid )
++b;
while ( arr[e] > mid )
--e;
if ( b <= e ) {
int tmp;
tmp = arr[b];
arr[b] = arr[e];
arr[e] = tmp;
++b;
--e;
}
}
if ( b < dr )
qsort( b , dr, arr );
if ( e > st )
qsort( st, e, arr );
}
int main() {
int i;
FILE *fin = fopen( "barman.in", "r" );
fscanf( fin, "%d", &n );
for ( i = 1; i <= n; ++i ) {
fscanf( fin, "%d", &v[i] );
s[i] = v[i];
}
fclose( fin );
qsort( 1, n, s );
int k;
int min = INF;
for ( k = 1; k <= n; ++k ) {
int tmp = s[1];
for (i = 1; i < n; ++i)
s[i] = s[i + 1];
s[n] = tmp;
for (i = 1; i <= n; ++i)
ok[i] = s[i] == v[i];
int cost = 0;
for (i = 1; i <= n; ++i) {
if (v[i] != s[i]) {
int j = 1;
while (!ok[j] && v[i] != s[j])
++j;
ok[j] = 1;
cost = cost + ab(i - j) + 20;
}
}
min = (min < cost) ? min : cost;
}
FILE *fout = fopen("barman.out", "w");
fprintf(fout, "%d", min);
fclose(fout);
return 0;
}