Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-11-01

SRM486 Easy OneRegister

16:08 | SRM486 Easy OneRegister - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM486 Easy OneRegister - chokudaiの日記 SRM486 Easy OneRegister - chokudaiの日記 のブックマークコメント

問題

数字s,tが与えられる

最初にa=sとし、a=a+a a=a-a a=a*a a=a/aの4つの操作が可能とする

最小操作数で終わらす時、辞書順最小のものを出力せよ 出来ない場合は:-(を返せ

方針

幅優先探索+メモ化でおしまい

s and t will be between 1 and 1000000000 (10^9), inclusive.とか書いてあるからオーダーが微妙そうに見えなくもないけど、2倍or2乗の操作だけでそんなたくさんの数字が作れるとも思えないことを考えると、

ソースコード

public class OneRegister {
    Dictionary<int, String> dic;
    
    public string getProgram(int s, int t)
    {
        dic = new Dictionary<int, string>();
        dic[s] = "";
        Queue<int> q = new Queue<int>();
        q.Enqueue(s);
        while (q.Count != 0)
        {
            int a = q.Dequeue();
            if(a==t) return dic[t];
            long next;
            next = (long)a * a;
            if (next <= t && !dic.ContainsKey((int)next)) { dic[(int)next] = dic[a] + "*"; q.Enqueue((int)next); }
            next = a * 2;
            if (next <= t && !dic.ContainsKey((int)next)) { dic[(int)next] = dic[a] + "+"; q.Enqueue((int)next); }
            next = 1;
            if (next <= t && !dic.ContainsKey((int)next)) { dic[(int)next] = dic[a] + "/"; q.Enqueue((int)next); }
        }
        return ":-(";
    }
}

TachikawaTachikawa2010/11/12 21:42今回の問題では必要ないですが、*,+ それぞれの条件に 「t % next == 0」を加えれば更に早くなりそうですね。

 |