TopCoder 練習

OneRegister(SRM 486 Div1 Easy)

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

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4.   
5. public class OneRegister{  
6.  public String getProgram(int s, int t){  
7.   String res=rec(1,t);  
8.   if(res!=null) res="/"+res;  
9.   res=min(res,rec(s,t));  
10.   if(res==null) return ":-(";  
11.   return res;  
12.  }  
13.  String rec(long s,long t){  
14.   if(s==t) return "";  
15.   if(s>t) return null;  
16.   String a=rec(s*2,t);  
17.   if(a!=null) a="+"+a;  
18.   String b=s==1?null:rec(s*s,t);  
19.   if(b!=null) b="*"+b;  
20.   return min(a,b);  
21.  }  
22.  String min(String s,String t){  
23.   if(s==null) return t;  
24.   if(t==null) return s;  
25.   if(s.length()<t.length()) return="" s;<br="">  if(s.length()>t.length()) return t;  
26.   if(s.compareTo(t)<=0) return s;  
27.   return t;  
28.  }  
29. }</t.length())>  

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;
 }
}