Cod sursa(job #359754)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 28 octombrie 2009 11:30:20
Problema Barman Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxN    1500
#define oo      2000000000
#define COST_LUAT   10
#define COST_LASAT  10
int A[maxN], B[maxN], C[maxN], N, Sol;
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);
    Sol = oo;
    copy(B + 1, B + N + 1, B + N + 1);
    for (i = 0; i < N && !(Cost = 0); ++ i) {
        for (j = 1; j <= N; ++ j)
            C[j] = (A[j] == B[i + j]) ? 0 : B[i + j];
        for (j = 1; j <= N; ++ j) {
            if (A[j] == B[i + j]) continue;
            gasit = 0;
            for (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);
    }
    printf("%d\n", Sol);
}