Cod sursa(job #359781)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 28 octombrie 2009 12:06:58
Problema Barman Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <stdio.h>
#include <algorithm>
#include <limits.h>
using namespace std;
#define maxN    1500
#define COST_LUAT   10
#define COST_LASAT  10
int A[maxN], B[maxN], C[maxN], N, Sol;
void perm () {
    B[N + 1] = B[1];
    for (int i = 1; i <= N; ++ i)
        B[i] = B[i + 1];
}
int main () {
    int i, Cost, j, k, gasit;
    freopen("barman.in", "r", stdin);
    freopen("barman.out", "w", stdout);
    scanf("%d", &N);
    for (i = 1; i <= N; ++ i) {
        scanf("%d", &A[i]);
        B[i] = A[i];
    }
    sort(B + 1, B + N + 1);
    for (Sol = INT_MAX, i = 0; i < N && !(Cost = 0); ++ i) {
        for (j = 1; j <= N; ++ j)
            C[j] = (A[j] == B[j]) ? 0 : B[j];
        for (j = 1; j <= N; ++ j) {
            if (A[j] == B[j]) continue;
            for (gasit = 0, k = j + 1; k <= N && ! gasit; ++ k) {
                if (A[j] == C[k]) continue;
                Cost += COST_LUAT + COST_LASAT + k - j;
                gasit = 1; C[k] = 0;
            }
            for (k = j - 1; k && ! gasit; -- k) {
                if (A[j] == C[k]) continue;
                Cost += COST_LUAT + COST_LASAT + j - k;
                gasit = 1; C[k] = 0;
            }
        }
        Sol = min(Sol, Cost);
        perm();
    }
    printf("%d\n", Sol);
}