1. Martinho Fernandes
  2. uva

Commits

Martinho Fernandes  committed fc40a35

Solved 102 : Ecological Bin Packing

  • Participants
  • Parent commits 0ed3e84
  • Branches default

Comments (0)

Files changed (7)

File 100.cpp

View file
 
 class cache {
 public:
-	static const size_t max_cache_size = 1000000;
-	cache() : store(max_cache_size) {
-		store[0] = 1;
-	}
+    static const size_t max_cache_size = 1000000;
+    cache() : store(max_cache_size) {
+        store[0] = 1;
+    }
 
-	bool has(unsigned n) const {
-		if(n > max_cache_size) return false;
-		return store[n-1] != 0;
-	}
-	int get(unsigned n) const {
-		return store[n-1];
-	}
-	void put(unsigned n, unsigned v) {
-		if(n > max_cache_size) return;
-		store[n-1] = v;
-	}
+    bool has(unsigned n) const {
+        if(n > max_cache_size) return false;
+        return store[n-1] != 0;
+    }
+    int get(unsigned n) const {
+        return store[n-1];
+    }
+    void put(unsigned n, unsigned v) {
+        if(n > max_cache_size) return;
+        store[n-1] = v;
+    }
 
 private:
-	vector<int> store;
+    vector<int> store;
 };
 
 struct solution {
-	unsigned i, j, max;
+    unsigned i, j, max;
 };
 ostream& operator<<(ostream& os, const solution& s) {
-	return os << s.i << ' ' << s.j << ' ' << s.max;
+    return os << s.i << ' ' << s.j << ' ' << s.max;
 }
 
 class problem {
 public:
-	solution solve(cache& c) {
-		unsigned longest = 0;
-		unsigned lo = min(i,j);
-		unsigned hi = max(i,j);
-		for(unsigned n = lo; n <= hi; ++n) {
-			unsigned len = iterate(n, c);
-			if(len > longest) longest = len;
-		}
-		solution s = { i, j, longest };
-		return s;
-	}
+    solution solve(cache& c) {
+        unsigned longest = 0;
+        unsigned lo = min(i,j);
+        unsigned hi = max(i,j);
+        for(unsigned n = lo; n <= hi; ++n) {
+            unsigned len = iterate(n, c);
+            if(len > longest) longest = len;
+        }
+        solution s = { i, j, longest };
+        return s;
+    }
 
-	friend istream& operator>>(istream& is, problem& p);
+    friend istream& operator>>(istream& is, problem& p);
 
 private:
-	unsigned iterate(unsigned n, cache& c) const {
-		if(c.has(n)) return c.get(n);
+    unsigned iterate(unsigned n, cache& c) const {
+        if(c.has(n)) return c.get(n);
 
-		stack<unsigned> cycle;
-		while(!c.has(n)) {
-			cycle.push(n);
-			if(n & 0x1) n = 3*n+1;
-			else n = n/2;
-		}
+        stack<unsigned> cycle;
+        while(!c.has(n)) {
+            cycle.push(n);
+            if(n & 0x1) n = 3*n+1;
+            else n = n/2;
+        }
 
-		unsigned len = c.get(n);
-		while(!cycle.empty()) {
-			unsigned x = cycle.top();
-			cycle.pop();
-			++len;
-			c.put(x, len);
-		}
+        unsigned len = c.get(n);
+        while(!cycle.empty()) {
+            unsigned x = cycle.top();
+            cycle.pop();
+            ++len;
+            c.put(x, len);
+        }
 
-		return len;
-	}
+        return len;
+    }
 
-	unsigned i, j;
+    unsigned i, j;
 };
 
 istream& operator>>(istream& is, problem& p) {
-	return is >> p.i >> p.j;
+    return is >> p.i >> p.j;
 }
 int main() {
     istream_iterator<problem> end;

File 101.cpp

View file
 
 class world {
 public:
-	world(int n) : piles(n), pos(n) {
-		for(int i = 0; i < n; ++i) {
-			piles[i].push_back(i);
-			pos[i] = i;
-		}
-	}
+    world(int n) : piles(n), pos(n) {
+        for(int i = 0; i < n; ++i) {
+            piles[i].push_back(i);
+            pos[i] = i;
+        }
+    }
 
-	void move_onto(int src, int dst) {
-		if(pos[src] == pos[dst]) return;
+    void move_onto(int src, int dst) {
+        if(pos[src] == pos[dst]) return;
 
-		list<int>& dstp = piles[pos[dst]];
-		list<int>::iterator dstn = find(dstp.begin(), dstp.end(), dst);
-		restore(dstn, dstp);
-		move_over(src, dst);
-	}
-	void move_over(int src, int dst) {
-		if(pos[src] == pos[dst]) return;
+        list<int>& dstp = piles[pos[dst]];
+        list<int>::iterator dstn = find(dstp.begin(), dstp.end(), dst);
+        restore(dstn, dstp);
+        move_over(src, dst);
+    }
+    void move_over(int src, int dst) {
+        if(pos[src] == pos[dst]) return;
 
-		list<int>& srcp = piles[pos[src]];
-		list<int>::iterator srcn = find(srcp.begin(), srcp.end(), src);
-		restore(srcn, srcp);
-		pile_over(src, dst);
-	}
-	void pile_onto(int src, int dst) {
-		if(pos[src] == pos[dst]) return;
+        list<int>& srcp = piles[pos[src]];
+        list<int>::iterator srcn = find(srcp.begin(), srcp.end(), src);
+        restore(srcn, srcp);
+        pile_over(src, dst);
+    }
+    void pile_onto(int src, int dst) {
+        if(pos[src] == pos[dst]) return;
 
-		list<int>& dstp = piles[pos[dst]];
-		list<int>::iterator dstn = find(dstp.begin(), dstp.end(), dst);
-		restore(dstn, dstp);
-		pile_over(src, dst);
-	}
-	void pile_over(int src, int dst) {
-		if(pos[src] == pos[dst]) return;
+        list<int>& dstp = piles[pos[dst]];
+        list<int>::iterator dstn = find(dstp.begin(), dstp.end(), dst);
+        restore(dstn, dstp);
+        pile_over(src, dst);
+    }
+    void pile_over(int src, int dst) {
+        if(pos[src] == pos[dst]) return;
 
-		list<int>& srcp = piles[pos[src]];
-		list<int>& dstp = piles[pos[dst]];
-		list<int>::iterator srcn = find(srcp.begin(), srcp.end(), src);
-		for(list<int>::iterator it = srcn; it != srcp.end(); ++it) {
-			pos[*it] = pos[dst];
-		}
-		dstp.splice(dstp.end(), srcp, srcn, srcp.end());
-	}
+        list<int>& srcp = piles[pos[src]];
+        list<int>& dstp = piles[pos[dst]];
+        list<int>::iterator srcn = find(srcp.begin(), srcp.end(), src);
+        for(list<int>::iterator it = srcn; it != srcp.end(); ++it) {
+            pos[*it] = pos[dst];
+        }
+        dstp.splice(dstp.end(), srcp, srcn, srcp.end());
+    }
 
-	friend ostream& operator<<(ostream& os, const world& w);
+    friend ostream& operator<<(ostream& os, const world& w);
 
 private:
-	vector<list<int> > piles;
-	vector<int> pos;
+    vector<list<int> > piles;
+    vector<int> pos;
 
-	void restore(list<int>::iterator first, list<int>& l) {
-		list<int> moved;
-		moved.splice(moved.end(), l, ++first, l.end());
-		for(list<int>::iterator it = moved.begin(); it != moved.end();) {
-			pos[*it] = *it;
-			list<int>::iterator it2 = it;
-			++it;
-			piles[*it2].splice(piles[*it2].begin(), moved, it2);
-		}
-	}
+    void restore(list<int>::iterator first, list<int>& l) {
+        list<int> moved;
+        moved.splice(moved.end(), l, ++first, l.end());
+        for(list<int>::iterator it = moved.begin(); it != moved.end();) {
+            pos[*it] = *it;
+            list<int>::iterator it2 = it;
+            ++it;
+            piles[*it2].splice(piles[*it2].begin(), moved, it2);
+        }
+    }
 };
 
 ostream& operator<<(ostream& os, const world& w) {
-	for(int i = 0; i < w.piles.size(); ++i) {
-		os << i << ":";
-		for(list<int>::const_iterator it = w.piles[i].begin(); it != w.piles[i].end(); ++it) {
-			os << " " << *it;
-		}
-		os << endl;
-	}
+    for(int i = 0; i < w.piles.size(); ++i) {
+        os << i << ":";
+        for(list<int>::const_iterator it = w.piles[i].begin(); it != w.piles[i].end(); ++it) {
+            os << " " << *it;
+        }
+        os << endl;
+    }
 }
 
 class command {
 public:
-	typedef void (world::*action)(int, int);
+    typedef void (world::*action)(int, int);
 
-	void run(world& w) {
-		(w.*cmd)(src, dst);
-	}
+    void run(world& w) {
+        (w.*cmd)(src, dst);
+    }
 
-	friend istream& operator>>(istream& is, command& c);
+    friend istream& operator>>(istream& is, command& c);
 
 private:
-	action cmd;
-	int src, dst;
+    action cmd;
+    int src, dst;
 };
 
 istream& operator>>(istream& is, command& c) {
-	string k;
-	is >> k;
-	if(k == "quit") {
-		is.setstate(ios::failbit);
-		return is;
-	}
-	cin >> c.src;
-	string m;
-	cin >> m;
-	cin >> c.dst;
-	if(k == "move") {
-		if(m == "onto") c.cmd = &world::move_onto;
-		if(m == "over") c.cmd = &world::move_over;
-	} else if(k == "pile") {
-		if(m == "onto") c.cmd = &world::pile_onto;
-		if(m == "over") c.cmd = &world::pile_over;
-	}
-	return is;
+    string k;
+    is >> k;
+    if(k == "quit") {
+        is.setstate(ios::failbit);
+        return is;
+    }
+    cin >> c.src;
+    string m;
+    cin >> m;
+    cin >> c.dst;
+    if(k == "move") {
+        if(m == "onto") c.cmd = &world::move_onto;
+        if(m == "over") c.cmd = &world::move_over;
+    } else if(k == "pile") {
+        if(m == "onto") c.cmd = &world::pile_onto;
+        if(m == "over") c.cmd = &world::pile_over;
+    }
+    return is;
 }
 
 class problem {
 public:
-	problem(int nblocks) : nblocks(nblocks) {}
+    problem(int nblocks) : nblocks(nblocks) {}
 
-	void add_command(command c) {
-		commands.push_back(c);
-	}
+    void add_command(command c) {
+        commands.push_back(c);
+    }
 
-	world solve() {
-		world w(nblocks);
+    world solve() {
+        world w(nblocks);
 
-		for_each(commands.begin(), commands.end(), bind2nd(mem_fun_ref(&command::run), w));
+        for_each(commands.begin(), commands.end(), bind2nd(mem_fun_ref(&command::run), w));
 
-		return w;
-	}
+        return w;
+    }
 
 private:
-	int nblocks;
-	vector<command> commands;
+    int nblocks;
+    vector<command> commands;
 };
 
 int main() {
-	int n;
-	cin >> n;
-	problem p(n);
-	command c;
-	while(cin >> c) {
-		p.add_command(c);
-	}
+    int n;
+    cin >> n;
+    problem p(n);
+    command c;
+    while(cin >> c) {
+        p.add_command(c);
+    }
 
-	world w = p.solve();
+    world w = p.solve();
 
-	cout << w;
+    cout << w;
 
-	return 0;
+    return 0;
 }

File 102.cpp

View file
+/*
+ * 102: Ecological Bin Packing
+ * http://uva.onlinejudge.org/external/1/102.pdf
+ */
+
+#include <algorithm>
+#include <functional>
+#include <iostream>
+#include <iterator>
+#include <numeric>
+#include <vector>
+#include <utility>
+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 bin {
+public:
+    bin() : bottles(3) {}
+
+    int moves_for(char kind) {
+        return accumulate(bottles.begin(), bottles.end(), 0) - bottles[index(kind)];
+    }
+
+    friend istream& operator>>(istream& is, bin& b);
+
+private:
+    int index(char kind) {
+        switch(kind) {
+        case 'B': return 0;
+        case 'G': return 1;
+        case 'C': return 2;
+        }
+    }
+    vector<int> bottles;
+};
+
+istream& operator>>(istream& is, bin& b) {
+    copy_n(istream_iterator<int>(is), 3, b.bottles.begin());
+    return is;
+}
+
+class problem {
+public:
+    problem() : bins(3) {}
+    pair<string,int> solve() {
+        static string orders[] = { "BCG", "BGC", "CBG", "CGB", "GBC", "GCB" };
+        vector<int> counts(6);
+        transform(orders, orders+6, counts.begin(), bind1st(mem_fun(&problem::evaluate),this));
+        int index = min_element(counts.begin(), counts.end()) - counts.begin();
+        return make_pair(orders[index], counts[index]);
+    }
+
+    friend istream& operator>>(istream& is, problem& p);
+
+private:
+    int evaluate(string order) {
+        int total = 0;
+        for(int i = 0; i < 3; ++i) {
+            total += bins[i].moves_for(order[i]);
+        }
+        return total;
+    }
+
+    vector<bin> bins;
+};
+
+istream& operator>>(istream& is, problem& p) {
+    copy_n(istream_iterator<bin>(is), 3, p.bins.begin());
+    return is;
+}
+
+struct format_output {
+    format_output(ostream& os) : os(os) {}
+    ostream& os;
+    void operator()(pair<string, int> solution) {
+        cout << solution.first << " " << solution.second << endl;
+    }
+};
+#include <sstream>
+int main() {
+    istream_iterator<problem> end;
+    vector<problem> problems;
+    copy(istream_iterator<problem>(cin), end, back_inserter(problems));
+
+    vector<pair<string, int> > solutions;
+    transform(problems.begin(), problems.end(), back_inserter(solutions), mem_fun_ref(&problem::solve));
+
+    for_each(solutions.begin(), solutions.end(), format_output(cout));
+
+    return 0;
+}

File 591.cpp

View file
 
 template <class InputIterator, class OutputIterator>
 OutputIterator copy_n (InputIterator first, size_t n, OutputIterator result) {
-	if(n <= 0) return 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;
+        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);
-		}
-	};
+    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;
 };
     size_t size;
     is >> size;
     if(size == 0) {
-    	is.setstate(ios::failbit);
-    	return is;
+        is.setstate(ios::failbit);
+        return is;
     }
     vector<int> newstacks;
     newstacks.reserve(size);
 }
 
 struct format_output {
-	format_output(ostream& os) : os(os), i() {}
-	ostream& os;
-	int i;
-	void operator()(int moves) {
-    	cout << "Set #" << ++i << endl;
-    	cout << "The minimum number of moves is " << moves << "." << endl;
-    	cout << endl;
-	}
+    format_output(ostream& os) : os(os), i() {}
+    ostream& os;
+    int i;
+    void operator()(int moves) {
+        cout << "Set #" << ++i << endl;
+        cout << "The minimum number of moves is " << moves << "." << endl;
+        cout << endl;
+    }
 };
 
 int main() {

File Makefile

View file
 all : $(ALL_TARGETS)
 
 clean :
-	$(RM) *.o *~
-  
-clobber : clean
-	$(RM) $(ALL_TARGETS)
+	$(RM) *~ $(ALL_TARGETS)
 
 debug-%:
 	$(CXX) -g $(patsubst debug-%,%.cpp,$@) -o $(patsubst debug-%,%,$@)

File test/102.example.in

View file
+1 2 3 4 5 6 7 8 9
+5 10 5 20 10 5 10 20 10

File test/102.example.out

View file
+BCG 30
+CBG 50