Cod sursa(job #2244281)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 22 septembrie 2018 15:28:09
Problema Barman Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <stdio.h>
#define NMAX 600

int v[1 + NMAX];
int s[1 + NMAX];
int ok[1 + NMAX];
int n;

long long INF = 1LL << 60;

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;
    long long 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, "%lld", min);
    fclose(fout);

    return 0;
}