Cod sursa(job #3253035)

Utilizator emamsema marginean emams Data 31 octombrie 2024 23:04:13
Problema Barman Scor 0
Compilator c-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <stdio.h>
#include <stdlib.h>

#define INF 2000000000

int N;
int drinks[600];
int sorted_drinks[600];

// Funcție de comparare pentru sortare
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

// Calculul costului pentru a muta băuturile într-o ordine circulară
int calculate_min_time() {
    int min_time = INF;

    // Sortăm băuturile pentru a putea genera permutări circulare
    for (int i = 0; i < N; i++) {
        sorted_drinks[i] = drinks[i];
    }
    qsort(sorted_drinks, N, sizeof(int), compare);

    // Verificăm fiecare rotație posibilă
    for (int start = 0; start < N; start++) {
        int current_time = 0;
        int positions[600] = {0}; // pozițiile unde se găsesc paharele

        // Simulăm mutarea fiecărui pahar la poziția dorită
        for (int i = 0; i < N; i++) {
            int drink_value = sorted_drinks[(start + i) % N];
            int current_pos = -1;

            // Căutăm poziția curentă a paharului cu valoarea dorită
            for (int j = 0; j < N; j++) {
                if (drinks[j] == drink_value && positions[j] == 0) {
                    current_pos = j;
                    positions[j] = 1; // Marcare ca folosit
                    break;
                }
            }

            // Calculăm costul deplasării
            if (current_pos != -1) {
                int target_pos = (start + i) % N;
                int distance = abs(target_pos - current_pos);
                current_time += distance + 20; // 10 secunde ridicare + 10 secunde așezare
            }
        }

        // Actualizăm timpul minim necesar
        if (current_time < min_time) {
            min_time = current_time;
        }
    }

    return min_time;
}

int main() {
    FILE *fin = fopen("barman.in", "r");
    FILE *fout = fopen("barman.out", "w");

    fscanf(fin, "%d", &N);
    for (int i = 0; i < N; i++) {
        fscanf(fin, "%d", &drinks[i]);
    }

    int result = calculate_min_time();
    fprintf(fout, "%d\n", result);

    fclose(fin);
    fclose(fout);

    return 0;
}