SRM 486 div1 easy: OneRegister

問題

TopCoder Statistics - Problem Statement

解法

s から t を考えるといろいろ可能性があって面倒ですが, t から s を考えれば,
・t が平方数 -> s は t の平方根
・t が偶数 -> s は t の半分
とほとんど場合分けがなくなり, また, t の遷移回数は 2^30 ≒ 10^9 より, たかだか 30 回程度です。30 回すべての場合で 平方根, 半分の両方の場合分けが生じることはありえないので, 基本的にこれで解けます。

初手で / を使って 1 にすることで s -> t に遷移できる可能性があることに注意です(サンプルにあるから気づくと思いますが)。

const int INF = 1e9;
string ans;
map<int, int> mp;

void dfs(int t, int s, string now) {
    if (t == s) {
        reverse(now.begin(), now.end());
        if (ans == "z" || ans.size() > now.size() || (ans.size() == now.size() && ans > now)) ans = now;
        return;
    }
    if (t == 1) {
        now += '/';
        reverse(now.begin(), now.end());
        if (ans == "z" || ans.size() > now.size() || (ans.size() == now.size() && ans > now)) ans = now;
        return;
    }
    if (mp.find(t) != mp.end()) {
        now += '*';
        dfs(mp[t], s, now);
        now.pop_back();
    }
    if (t%2 == 0) {
        now += '+';
        dfs(t/2, s, now);
        now.pop_back();
    }
}

class OneRegister {
public:
    string getProgram(int s, int t) {
        ans = "z";
        mp.clear();
        for (int i = 2; i*i <= INF; i++) mp[i*i] = i;
        dfs(t, s, "");
        if (ans == "z") ans = ":-(";
        return ans;
    }
};