Commits

Martinho Fernandes committed 014f3df

Solved 591: Box of Bricks

  • Participants
  • Parent commits 30b3e36

Comments (0)

Files changed (1)

+#include <algorithm>
+#include <functional>
+#include <iostream>
+#include <iterator>
+#include <numeric>
+#include <vector>
+using namespace std;
+
+template <class InputIterator, class OutputIterator>
+OutputIterator copy_n (InputIterator first, size_t n, OutputIterator result) {
+	if(n <= 0) return result;
+    *result = *first;
+    while (0 < --n) *++result = *++first;
+    return (++result);
+}
+
+class problem {
+public:
+    bool good() const {
+        return stacks.size() > 0;
+    }
+
+    int solve() {
+    	int sum = accumulate(stacks.begin(), stacks.end(), 0, plus<int>());
+    	int avg = sum / stacks.size();
+    	int result = accumulate(stacks.begin(), stacks.end(), 0, add_above_avg(avg));
+    	return result;
+    }
+
+    friend istream& operator>>(istream& is, problem& p);
+
+private:
+	struct add_above_avg {
+		add_above_avg(int avg) : avg(avg) {}
+		int avg;
+		int operator()(int acc, int v) {
+			if(v < avg) return acc;
+			return acc + (v - avg);
+		}
+	};
+
+    vector<int> stacks;
+};
+
+istream& operator>>(istream& is, problem& p) {
+    size_t size;
+    is >> size;
+    if(size == 0) {
+    	is.setstate(ios::failbit);
+    	return is;
+    }
+    vector<int> newstacks;
+    newstacks.reserve(size);
+    istream_iterator<int> in(is);
+    copy_n(in, size, back_inserter(newstacks));
+    p.stacks = newstacks;
+    return is;
+}
+
+vector<problem> read_problems(istream& is) {
+    vector<problem> problems;
+    istream_iterator<problem> in(is);
+    istream_iterator<problem> end;
+    copy(in, end, back_inserter(problems));
+    return problems;
+}
+
+int main(int argc, char **argv) {
+    vector<problem> problems(read_problems(cin));
+
+    vector<int> solutions;
+    transform(problems.begin(), problems.end(), back_inserter(solutions), mem_fun_ref(&problem::solve));
+
+    for(size_t i = 0; i < solutions.size(); ++i) {
+    	cout << "Set #" << i+1 << endl;
+    	cout << "The minimum number of moves is " << solutions[i] << "." << endl;
+    	cout << endl;
+    }
+
+    return 0;
+}