Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-11-21SRM486(DIV1)

SRM486 第一問(300pt) OneRegister

|  SRM486 第一問(300pt) OneRegister - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM486 第一問(300pt) OneRegister - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10992

うーむ。

  • 1にしたいなら「/」一つでいいのか。s = tならなにもしなくていいよね。
    • 特殊なサンプルが通るようにコーナーケースを書いた。
  • 「+」と「*」の再帰で解けるかな?かな?
    • t % s > 0 のときは、一旦「/+」「2」にしてから再帰関数にぶっ込む。
    • そうじゃないときはそのままぶっ込む。

サンプル通った。

  • (s, t) = (1, 1000000000) でstack overflowした。
    • 再帰が深く入りすぎたのかな?
  • 関数引数をlongにしたら大丈夫だった。
  • 提出。

システムテスト落ちた…

  • なんで?
    • t % s = 0 だったので、そのまま再帰にぶっ込んでた
    • t % s = 0 の場合でも、最初に「/+」して 2にする場合を考慮してなかった!

汚いコードになってしまったが…まぁいい

  • 提出。通った
public class OneRegister {

	public int Goal;
	public static final String OK = ":-)";
	public static final String NG = ":-(";
	public String answer;

	public String search(long s, String now) {
		if (s > Goal) {
			return NG;
		} else if (s == Goal){
			if (answer.equals("") || now.length() < answer.length() ||
					(now.length() == answer.length() && now.compareTo(answer) < 0) ) {
				answer = now;
			}
			return OK;
		}

		String mul = search(s * s, now + "*");;
		String add = search(2 * s, now + "+");
		if (add.equals(NG) && mul.equals(NG)) {
			return NG;
		} else {
			return OK;
		}
	}

	public String getProgram(int s, int t) {
		Goal = t;
		if (s == t) {
			return "";
		}
		if (t == 1) {
			return "/";
		}

		answer = "";
		String ans = "";
		if (t % s != 0) {
			ans += "/+";
			s = 2;
			search(s, ans);
		} else if (s == 1) {
			search(2, "+");
		} else {
			search(s, ans);
			search(2, "/+");
		}

		if (answer == "") {
			return NG;
		}
		return answer;
	}
}