Cod sursa(job #1403355)

Utilizator tudor_bonifateTudor Bonifate tudor_bonifate Data 27 martie 2015 11:11:47
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#include <algorithm>
#include <climits>

#define Nmax 610

using namespace std;

int n , i , k , j , cost , sol , copie;

int A[Nmax] , v[Nmax];

bool good[Nmax];

int main()
{
    freopen("barman.in","r",stdin);
    freopen("barman.out","w",stdout);

    for (scanf("%d", &n) , i = 1; i <= n; ++i)
    {
        scanf("%d", &A[i]);
        v[i] = A[i];
    }

    sort(v + 1 , v + n + 1);

    for (sol = INT_MAX , k = 1; k <= n; ++k)   // numarul de permutari
    {
        for (copie = v[1] , i = 1; i < n; ++i)
            v[i] = v[i+1];
        v[n] = copie;

        for (i = 1; i <= n; ++i)
            good[i] = (A[i] == v[i]);   //paharul din camera i este la locul lui

        for (cost = 0 , i = 1; i <= n; ++i)
         if (A[i] != v[i])
         {
             for (j = 1; good[j] || A[i] != v[j]; ++j);

             good[j] = true;

             cost += 20 + max(i , j) - min(i , j); // numarul de pahare de pe tava nu influenteaza costul
         }

        sol = min(sol , cost);
    }

    printf("%d\n", sol);

    return 0;
}