Cod sursa(job #2244290)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 22 septembrie 2018 15:32:58
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#include <algorithm>
#include <iostream>
#define NMAX 600

using namespace std;

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;
}

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 );

    sort( s + 1, s + n + 1 );

    int k;
    long long minim = 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;
            }
        }
        minim = (minim < cost) ? minim : cost;

    }

    FILE *fout = fopen("barman.out", "w");
    fprintf(fout, "%lld", minim);
    fclose(fout);

    return 0;
}