Cod sursa(job #3920)

Utilizator fluffyDan-Leonard Crestez fluffy Data 29 decembrie 2006 16:53:45
Problema Barman Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef int (*qcmp)(const void *, const void *);

#define MAX_N (1 << 10)
#define MOVE_COST 1
#define PICKUP_COST 10
#define PUTDOWN_COST 10

int n, v[MAX_N];
int vsort[MAX_N];

void read(void)
{
    int i;
    scanf("%d", &n);
    for (i = 0; i < MAX_N; ++i) {
        scanf("%d", v + i);
    }
}

int qcmp_int(const int *a, const int *b)
{
    return *a - *b;
}

void process(void)
{
    int i, j, sn;
    memcpy(vsort, v, n * sizeof(int));
    qsort(vsort, n, sizeof(int), (qcmp)qcmp_int);
    for (i = sn = 1; i < n; ++i) {
        if (vsort[i] != vsort[sn - 1]) {
            vsort[sn++] = vsort[i];
        }
    }
    for (i = 0; i < n; ++i) {
        for (j = 0; j < sn; ++j) {
            if (vsort[j] == v[i]) {
                v[i] = j;
                break;
            }
        }
    }
    memcpy(vsort, v, n * sizeof(int));
    qsort(vsort, n, sizeof(int), (qcmp)qcmp_int);
}

int solve(void)
{
    int t, skip[MAX_N], cost, mcost;
    mcost = 0xFFFFFFF;
    for (t = 0; t < n; ++t) {
        cost = 0;
        for (i = 0; i < n; ++i) {
            if (!(skip[i] = (v[i] == v[(t + i) % n]))) {
                cost += PICKUP_COST + PUTDOWN_COST;
            }
        }
        if (cost < mcost) {
            mcost = cost;
        }
    }
    return mcost;
}

int main(void)
{
    freopen("barman.in", "rt", stdin);
    freopen("barman.out", "wt", stdout);
    read();
    process();
    printf("%d", solve());
    return 0;
}