Saturday, June 6, 2015

UVa 120 - Stacks of Flapjacks

// UVa 120 - Stacks of Flapjacks

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> flips;
int a[30], b[30], o[30], n;

void flip(int f) {
	flips.push_back(n - f);
	int i = 0;
	int j = f;
	while (i < j) {
		int k = a[i];
		a[i] = a[j];
		a[j] = k;
		i++;
		j--;
	}
}

int main() {
	string line;
	while (getline(cin, line)) {
		istringstream strm(line);
		int v;
		n = 0;
		while (strm >> v) {
			o[n] = v;
			a[n] = v;
			b[n] = v;
			n++;
		}
		flips.clear();
		sort(b, b + n);
		// flip flip flip
		for (int i = n - 1; i > 0; i--) {
			int j = 0;
			while (a[j] != b[i])
				j++;
			if (j != i) {
				if (j != 0)
					flip(j);
				flip(i);
			}
		}
		// output
		cout << o[0];
		for (int i = 1; i < n; i++)
			cout << " " << o[i];
		cout << endl;
		for (int i = 0; i < flips.size(); i++)
			cout << flips[i] << " ";
		cout << 0 << endl;
	}

	return 0;
}

No comments:

Post a Comment