Cod sursa(job #3357157)

Utilizator parus_majorParus Major parus_major Data 6 iunie 2026 17:56:05
Problema Barman Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    ifstream fin("barman.in");
    ofstream fout("barman.out");

    int N;
    if (!(fin >> N)) return 0;

    vector<int> v(N + 1);
    vector<int> sortat(2 * N + 1); // Îl dimensionăm dublu pentru circularitate simplă

    for (int i = 1; i <= N; ++i) {
        fin >> v[i];
        sortat[i] = v[i];
    }

    // Sortăm elementele pentru a avea ordinea crescătoare de bază
    sort(sortat.begin() + 1, sortat.begin() + N + 1);

    // Dublăm vectorul sortat pentru a simula rotația circulară fără operatorul %
    for (int i = 1; i <= N; ++i) {
        sortat[N + i] = sortat[i];
    }

    const int INF = 1e9; // O valoare suficient de mare pentru minimizare
    int min_timp_total = INF;

    // Testăm toate cele N configurații țintă posibile (fiecare rotație)
    for (int start = 1; start <= N; ++start) {
        // used[j] va fi 1 dacă poziția j din fereastra curentă a fost deja ocupată
        vector<int> used(N + 1, 0);

        // PASUL 1: Tratăm cazul particular (elementele deja așezate corect)
        // Dacă paharul de pe poziția i corespunde deja ca valoare cu ținta, îl lăsăm pe loc
        for (int i = 1; i <= N; ++i) {
            if (v[i] == sortat[start + i - 1]) {
                used[i] = 1; // Blocăm poziția din țintă, nu o va folosi nimeni altcineva
            }
        }

        int timp_curent = 0;

        // PASUL 2: Potrivim Greedy restul paharelor
        for (int i = 1; i <= N; ++i) {
            // Dacă elementul actual este deja la locul lui, trecem mai departe
            if (v[i] == sortat[start + i - 1]) {
                continue;
            }

            // Căutăm prima poziție liberă j în configurația țintă care are aceeași valoare
            for (int j = 1; j <= N; ++j) {
                if (used[j] == 0 && v[i] == sortat[start + j - 1]) {
                    used[j] = 1; // Rezervăm această destinație

                    // Adăugăm costul: 20s (luat + pus jos) + distanța liniară parcursă
                    timp_curent += abs(i - j) + 20;
                    break; // Am găsit destinația pentru paharul i, trecem la paharul i + 1
                }
            }
        }

        // Reținem costul minim dintre toate rotațiile
        min_timp_total = min(min_timp_total, timp_curent);
    }

    fout << min_timp_total << "\n";

    fin.close();
    fout.close();
    return 0;
}