TopCoder 練習

OneRegister(SRM 486 Div1 Easy)

wataさんのコードを参考に，というかほぼ丸写ししています．

基本的には，(s,t)と(1,t)を算出して，辞書式順に早いものを返しているようです．
rec(s,t)が非常にすっきりしていて凄い．再帰で書くとTLEするかと思いましたが，余裕だったようです．

import java.util.*;
import java.lang.*;
import java.math.*;

public class OneRegister{
 public String getProgram(int s, int t){
  String res=rec(1,t);
  if(res!=null) res="/"+res;
  res=min(res,rec(s,t));
  if(res==null) return ":-(";
  return res;
 }
 String rec(long s,long t){
  if(s==t) return "";
  if(s>t) return null;
  String a=rec(s*2,t);
  if(a!=null) a="+"+a;
  String b=s==1?null:rec(s*s,t);
  if(b!=null) b="*"+b;
  return min(a,b);
 }
 String min(String s,String t){
  if(s==null) return t;
  if(t==null) return s;
  if(s.length()  if(s.length()>t.length()) return t;
  if(s.compareTo(t)<=0) return s;
  return t;
 }
}