SRM486 Div1 Easy

300
+と*しか使う必要がない。
1とsからBFS

mapを避けて配列を使う癖があることを発見した。UVaならそれで良かったんだけど・・・。

string bfs(int s, int t)
{
  map<int, int> prev;
  map<int, char> path;

  queue<int> q;
  for (q.push(s); q.size(); q.pop()) {
    int n = q.front();
    if ((lli)n * (lli)n <= (lli)t && prev.count(n * n) == 0) {
      prev[n * n] = n;
      path[n * n] = '*';
      q.push(n * n);
    }
    if (2 * n <= t && prev.count(n + n) == 0) {
      prev[n + n] = n;
      path[n + n] = '+';
      q.push(n + n);
    }
  }

  if (prev.count(t) == 0) return string(1000, '@');
  string ret;
  for (int i = t; i != s; i = prev[i]) {
    ret += path[i];
  }
  reverse(ret.begin(), ret.end());
  return ret;
}

class OneRegister {
public:
  string getProgram(int s, int t)
  {
    if (s == t) return "";
    string a = bfs(s, t);
    string b = "/" + bfs(1, t);
    if (a[1] == '@' && b[1] == '@') return ":-(";
    if (a.size() == b.size()) return min(a, b);
    return a.size() < b.size() ? a : b;
  }

};