Cod sursa(job #771542)

Utilizator darrenRares Buhai darren Data 26 iulie 2012 12:46:51
Problema Barman Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <algorithm>

using namespace std;

int N;
int A[602], B[602];
int pos[602], result = 0x3f3f3f3f;

class compare
{
	public: inline bool operator () (const int& i1, const int& i2)
	{
		if (B[i1] != B[i2])
			return B[i1] < B[i2];
		return i1 < i2;
	}
};

inline int mabs(const int& x)
{
	return (x < 0 ? -x : x);
}
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];
	
	for (int i = 1; i <= N; ++i)
	{
		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];
			
		for (int j = 1; j <= N; ++j)
			pos[j] = j;
		sort(pos + 1, pos + N + 1, compare());
		for (int j = 1; j <= N; ++j)
			B[pos[j]] = j;
		
		int resultnow = 0;
		for (int j = 1; j <= N; ++j)
			if (B[j] != j)
			{
				resultnow += 20;
				resultnow += mabs(real(j, i) - real(B[j], i));
			}
		
		result = min(result, resultnow);
	}
	
	fout << result << '\n';
	
	fin.close();
	fout.close();
}