Cod sursa(job #1229194)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 16 septembrie 2014 18:24:32
Problema Barman Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <algorithm>
using namespace std;

const int MAX_N = 602;

int N, ans = -1;
int v[MAX_N], a[MAX_N], b[MAX_N];

int main() {
	ifstream f("barman.in");
	ofstream g("barman.out");

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

	sort(a + 1, a + N + 1);
	
	for(int p = 1; p <= N; ++p) {
		for(int i = 1; i <= N; ++i)
			b[i] = v[i];
		
		int now = 0;

		for(int i = 1; i <= N; ++i) {
			if(b[i] == a[i])
				continue;

			int p1 = -1, p2 = -1;
			for(int j = i + 1; j <= N; ++j)
				if(b[j] == a[i]) {
					if(p1 == -1)
						p1 = j;
					if(b[j] == a[i] && b[i] == a[j] && p2 == -1)
						p2 = j;
				}
			if(p2 != -1)
				p1 = p2;
			now += 2 * abs(p1 - i) + 40;
			swap(b[i], b[p1]);
		}

		if(now < ans || ans == -1)
			ans = now;
		
		int temp = a[1];
		for(int i = 1; i < N; ++i)
			a[i] = a[i + 1];
		a[N] = temp;
	}

	g << ans << "\n";
	
	f.close();
	g.close();
	
	return 0;
}