Cod sursa(job #2652741)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 25 septembrie 2020 16:59:07
Problema Barman Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <bits/stdc++.h>
#define NMAX 606
using namespace std;

int n, v[NMAX], v2[NMAX];

vector<pair<int,int> > fr;

int cost(int a, int b){
    return min(abs(a-b), min(a,b) + n - max(a,b));
}

int _try(int from, int val, int st){
    int ans = cost(st, from);
    st = (st + 1) % n;
    for (int i=(from+1) % n; i != from; i = (i + 1) % n){
        if (v[i] == val){
            ans += cost(i, st);
            st = (st + 1) % n;
        }
    }
    return ans;
}

int place(int val, int pos){
    int ans = 1e9;
    for (int i=0;i<n;i++){
        if (v[i] == val){
            ans = min(ans, _try(i, val, pos));
        }
    }
    return ans;
}

int solve(int st){
    int ans = 0, pos = st;
    for (auto it : fr){
        int j = pos;
        while (j != (pos + it.first) % n){
            if (v[j] != it.second)
                ans += 20;
            j = (j + 1) % n;
        }
        pos = j;
    }
    for (auto it : fr){
        ans += place(it.second, st);
        st = (st + it.first) % n;
    }
    return ans;
}

int main()
{
    freopen("barman.in","r",stdin);
    freopen("barman.out","w",stdout);

    cin >> n;
    for (int i=1;i<=n;i++) cin >> v[i-1], v2[i] = v[i-1];
    sort(v2+1,v2+n+1);

    int cnt = 1;
    for (int i=1;i<=n;i++){
        if (v2[i] == v2[i-1]) cnt++;
        else{
            if (i != 1){
                fr.push_back({cnt, v2[i-1]});
                cnt = 1;
            }
        }
    }
    fr.push_back({cnt, v2[n]});

    int ans = 1e9;
    for (int i=0;i<n;i++){
        ans = min(ans, solve(i));
    }

    cout << ans << '\n';

    return 0;
}