Cod sursa(job #2764765)

Utilizator DragosC1Dragos DragosC1 Data 22 iulie 2021 14:45:02
Problema Barman Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;

int n;
int a[1201];
int b[601];
int sortat[601];

int Min = 2e9;

void read() {
    int i;
    ifstream f("barman.in");
    f >> n;
    for (i = 1; i <= n; i++)
        f >> a[i];
    f.close();
}

void solve() {
    int i, l, j, k, dist, nr, minim, ind;
    for (i = n + 1; i <= 2 * n; i++)
        a[i] = a[i - n];

    for (i = 1; i <= n; i++)
        sortat[i] = a[i];
    
    sort(sortat + 1, sortat + n + 1);

    for (i = n; i < 2 * n; i++) {
        l = 0, dist = 0, nr = 0;
        for (j = i - n + 1; j <= i; j++)  
            b[++l] = a[j];
        for (j = 1; j <= l; j++)
            if (b[j] != sortat[j]) {
                nr++;
                minim = 1e9;
                for (k = j + 1; k <= l; k++)
                    if (b[k] == sortat[j]) {
                        if (min(k - j + 1, n - (k - j + 1) + 1) < minim) {
                            minim = min(k - j + 1, n - (k - j + 1) + 1);
                            ind = k;
                        }
                    }
                dist += minim;
                swap(b[j], b[ind]);
            }
        if (nr * 40 + 2 * dist < Min)
            Min = nr * 40 + 2 * dist;
    }
}

void output() {
    ofstream g("barman.out");
    g << Min;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}