102 – Ecological Bin Packing

102 – Ecological Bin Packing (pdf)

http://github.com/cirocavani/uva.onlinejudge.org-cxx/tree/master/102

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

struct N;
typedef std::vector<std::mem_fun_t<int, N> > F;

struct N
{

  int b, g, c;

  N(int _b = 0, int _g = 0, int _c = 0) : b(_b), g(_g), c(_c) { }

  friend std::istream& operator>>(std::istream& in, N& n)
  {
    return in >> n.b >> n.g >> n.c;
  }

  int value_b() { return b; }

  int value_g() { return g; }

  int value_c() { return c; }

};

struct W
{

  N n1, n2, n3;

  int m;

  std::string t;

  W() : m(0) { }

  friend std::istream& operator>>(std::istream& in, W& w)
  {
    return in >> w.n1 >> w.n2 >> w.n3 >> std::ws;
  }

  friend std::ostream& operator<<(std::ostream& out, const W& w)
  {
    return out << w.t << " " << w.m << std::endl;
  }

  std::string str(std::vector<std::string>& s, std::vector<std::size_t>& i)
  {
    std::string out;
    for (std::vector<std::size_t>::iterator p = i.begin(); p != i.end(); ++p)
      out += s[*p];
    return out;
  }

  W& min()
  {
    std::vector<N*> v;
    v.push_back(&n1);
    v.push_back(&n2);
    v.push_back(&n3);

    F f;
    f.push_back(std::mem_fun(&N::value_b));
    f.push_back(std::mem_fun(&N::value_g));
    f.push_back(std::mem_fun(&N::value_c));

    std::vector<std::string> s(f.size());
    s[0] = "B";
    s[1] = "G";
    s[2] = "C";

    std::vector<std::size_t> fi(f.size());
    for (std::size_t i = 0; i < fi.size(); ++i)
      fi[i] = i;

    m = 0;
    t = "";

    do
      {
	int n = 0;
	for (std::size_t i = 0; i < fi.size(); ++i)
	  for (std::size_t j = 0; j < v.size(); ++j)
	    n += i == j ? 0 : f[fi[i]](v[j]);

	if (m == 0 || m > n || (m == n && t > str(s, fi)))
	  {
	    m = n;
	    t = str(s, fi);
	  }
      }
    while (std::next_permutation(fi.begin(), fi.end()));

    return *this;
  }

};

void evaluate(W* w)
{
  std::cout << w->min();
}

int main()
{
  std::vector<W*> v;

  while (std::cin.good())
    {
      W* w = new W();
      std::cin >> *w;
      v.push_back(w);
    }

  std::for_each(v.begin(), v.end(), evaluate);

  return 0;
}

101 – The Blocks Problem

101 – The Blocks Problem (pdf)

http://github.com/cirocavani/uva.onlinejudge.org-cxx/tree/master/101

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <exception>

struct N;
typedef std::vector<N> U;
typedef std::vector<U> V;

struct N
{

  int i, x, y;

  N(int _i = -1) : i(_i), x(_i), y(0) { }

  friend std::ostream& operator<<(std::ostream& out, const N& n)
  {
    return out << n.i;
  }

};

struct W
{

  U u;

  V v;

  W(int n) : u(n), v(n)
  {
    for (int i = 0; i < n; ++i)
      {
	N o(i);
	u[i] = o;
	v[i].push_back(o);
      }
  }

  friend std::ostream& operator<<(std::ostream& out, const W& w)
  {
    for (std::size_t i = 0; i < w.v.size(); ++i)
      {
	out << i << ":";
	const U& k = w.v[i];
	for (std::size_t j = 0; j < k.size(); ++j)
	  out << " " << k[j];
	out << std::endl;
      }
    return out;
  }

  void moveonto(int i, int j)
  {
    try
      {
	assertNotEqual(i, j);

	const N& ni = u[i];
	const N& nj = u[j];
	assertNotEqual(ni.x, nj.x);

	const N& nix = u[ni.x];
	const N& njx = u[nj.x];
	assertNotOver(nix, ni);
	assertNotOver(njx, ni);
	assertNotOver(nix, nj);
	assertNotOver(njx, nj);

	moveback(ni.x, ni.y);
	moveback(nj.x, nj.y);
	move(ni.i, nj.x);
      }
    catch (std::exception& e)
      {
	// no-op
      }
  }

  void moveover(int i, int j)
  {
    try
      {
	assertNotEqual(i, j);

	const N& ni = u[i];
	const N& nj = u[j];
	assertNotEqual(ni.x, nj.x);

	const N& nix = u[ni.x];
	assertNotOver(nix, ni);

	moveback(ni.x, ni.y);
	move(ni.i, nj.x);
      }
    catch (std::exception& e)
      {
	// no-op
      }
  }

  void pileonto(int i, int j)
  {
    try
      {
	assertNotEqual(i, j);

	const N& ni = u[i];
	const N& nj = u[j];
	assertNotEqual(ni.x, nj.x);

	const N& njx = u[nj.x];
	assertNotOver(njx, nj);

	moveback(nj.x, nj.y);
	movepile(ni.i, nj.x);
      }
    catch (std::exception& e)
      {
	// no-op
      }
  }

  void pileover(int i, int j)
  {
    try
      {
	assertNotEqual(i, j);

	const N& ni = u[i];
	const N& nj = u[j];
	assertNotEqual(ni.x, nj.x);

	movepile(ni.i, nj.x);
      }
    catch (std::exception& e)
      {
	// no-op
      }
  }

private:

  void assertNotEqual(int i, int j)
  {
    if (i == j) throw std::exception();
  }

  void assertNotOver(const N& nx, const N& n)
  {
    if (nx.x == n.x && nx.y > n.y) throw std::exception();
  }

  void moveback(int x, std::size_t y)
  {
    U& k = v[x];
    while (k.size() > y + 1)
      {
	int i = k.back().i;
	k.pop_back();
	put(u[i], i);
      }
  }

  void move(int i, int x)
  {
    N& n = u[i];
    U& k = v[n.x];
    k.erase(k.begin() + n.y);
    put(n, x);
  }

  void movepile(int i, int x)
  {
    N& n = u[i];
    U& k = v[n.x];
    for (U::iterator p = k.begin() + n.y; p != k.end(); p = k.erase(p))
      put(u[p->i], x);
  }

  void put(N& n, int x)
  {
    U& m = v[x];
    n.x = x;
    n.y = m.size();
    m.push_back(n);
  }

};

struct M
{

  std::string m1, m2;

  int i, j;

};

int main()
{
  int n;

  std::cin >> n;

  W w(n);

  std::vector<M> v;

  while (true)
    {
      std::string m0;
      std::cin >> m0;

      if (m0 == "quit")
	break;

      M m;
      m.m1 = m0;
      std::cin >> m.i >> m.m2 >> m.j >> std::ws;

      v.push_back(m);
    }

  for (std::vector<M>::iterator p = v.begin(); p != v.end(); ++p)
    {
      if (p->m1 == "move" && p->m2 == "onto")
	w.moveonto(p->i, p->j);
      else if (p->m1 == "move" && p->m2 == "over")
	w.moveover(p->i, p->j);
      else if (p->m1 == "pile" && p->m2 == "onto")
	w.pileonto(p->i, p->j);
      else if (p->m1 == "pile" && p->m2 == "over")
	w.pileover(p->i, p->j);
    }

  std::cout << w;

  return 0;
}

100 – The 3n + 1 problem

100 – The 3n + 1 problem (pdf)

http://github.com/cirocavani/uva.onlinejudge.org-cxx/tree/master/100

#include <iostream>
#include <vector>
#include <algorithm>

struct N
{

  int s, e, m;

  N() : s(1), e(1), m (1) { }

  friend std::istream& operator>>(std::istream& in, N& n)
  {
    return in >> n.s >> n.e >> std::ws;
  }

  friend std::ostream& operator<<(std::ostream& out, const N& n)
  {
    return out << n.s << " " << n.e << " " << n.m << std::endl;
  }

  int count(int n)
  {
    if (n == 1)
      return 1;

    int count = 2; // 1 and n
    while ((n = n % 2 == 0 ? n / 2 : 3 * n + 1) != 1)
      ++count;

    return count;
  }

  N& max()
  {
    m = 0;
    const int _s = std::min(s, e);
    const int _e = std::max(s, e);
    for (int i = _s; i <= _e; ++i)
      m = std::max(m, count(i));
    return *this;
  }

};

void evaluate(N& n)
{
  std::cout << n.max();
}

int main()
{
  std::vector<N> v;

  while (std::cin.good())
    {
      N n;
      std::cin >> n;
      v.push_back(n);
    }

  std::for_each(v.begin(), v.end(), evaluate);

  return 0;
}