Pagini recente » Istoria paginii utilizator/dorin.rotarescu | Profil exquisite | Istoria paginii utilizator/ubb_lili | Cod sursa (job #541749) | Cod sursa (job #771574)
Cod sursa(job #771574)
#include <cstring>
#include <fstream>
#include <algorithm>
using namespace std;
int N;
int A[602], B[602], C[602];
int fr[602], wh[602];
bool put[602], done[602];
int pos[602], result = 0x3f3f3f3f;
class compare
{
public: inline bool operator () (const int& i1, const int& i2)
{
if (A[i1] != A[i2])
return A[i1] < A[i2];
return i1 < i2;
}
};
inline int mabs(const int& x)
{
int aux = (x < 0 ? -x : x);
return min(aux, N - aux);
}
inline int real(const int& x, const int& y)
{
return (x + y - 1 > N ? x + y - 1 - N : x + y - 1);
}
int main()
{
ifstream fin("barman.in");
ofstream fout("barman.out");
fin >> N;
for (int i = 1; i <= N; ++i)
{
fin >> A[i];
pos[i] = i;
}
sort(pos + 1, pos + N + 1, compare());
int now = 0;
for (int i = 1; i <= N; ++i)
{
++now;
while (i < N && A[pos[i]] == A[pos[i + 1]])
{
A[pos[i]] = now;
++i;
}
A[pos[i]] = now;
}
for (int i = 1; i <= N; ++i)
++fr[A[i]];
for (int i = 1; i <= N; ++i)
fr[i] += fr[i - 1];
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= N; ++j)
wh[j] = fr[j - 1] + 1;
for (int j = i; j <= N; ++j)
B[j - i + 1] = A[j];
for (int j = 1; j < i; ++j)
B[N - i + 1 + j] = A[j];
memset(put, 0, sizeof(put));
memset(done, 0, sizeof(done));
for (int j = 1; j <= N; ++j)
if (wh[B[j]] <= j && j <= fr[B[j]])
{
B[j] = j;
put[j] = true;
done[j] = true;
}
int resultnow = 0;
for (int j = 1; j <= N; ++j)
if (!done[j])
{
while (put[wh[B[j]]])
++wh[B[j]];
++wh[B[j]];
B[j] = wh[B[j]] - 1;
put[B[j]] = true;
resultnow += 20 + mabs(real(B[j], i) - real(j, i));
}
result = min(result, resultnow);
}
fout << result << '\n';
fin.close();
fout.close();
}