srm 620 div2

/**
 * User: Free
 * Date: 14-5-11
 * Time:   12:52
 */
public class PairGameEasy
{
  public  String able(int a, int b, int c, int d)
    {
        String Y = "Able to generate";
        String N = "Not able to generate";
        while(a!=c || b!=d){
            if(c<a || d<b){
                return  N;
            }
            if(c>d){
                c = c-d;
            }
            else if(d>c){
                d = d-c;
            }else{
                return N;
            }
        }
        if(a==c && b==d )        return Y;
        else return N;
    }
    public static void main(String args[]){
        PairGameEasy pairGameEasy = new PairGameEasy();
        System.out.println(pairGameEasy.able(1,2,3,8));
        System.out.println(pairGameEasy.able(1,2,2,1));
        System.out.println(pairGameEasy.able(2,2,2,999));

    }


}

 
topcoder 상 3 가지 해결
(1) 귀속

    public  String able(int a, int b, int c, int d)
    {
        String Y = "Able to generate";
        String N = "Not able to generate";
        {
        if(a>c || b>d)return N;
        if(able(a+b,b,c,d).equals(N))
            return able(a,a+b,c,d);
        else
            return Y;
    }

 
 
（2）DP
 

    public  String able(int a, int b, int c, int d)
    {
        String Y = "Able to generate";
        String N = "Not able to generate";
        int dp[][] =new int[2000][2000];
        dp[a][b]=1;
        for(int i=a;i<=c;i++){
                     

            for(int j=b;j<=d;j++) {
                   if(dp[i][j]==1){
                       dp[i+j][j]=1;
                       dp[i][i+j]=1;
                   }
            }
        }
        if(dp[c][d]==1){
            return Y;
        }
            
        return N;

    }

 
 
이 dp 방법 은 생각 이 좋 습 니 다. 비록 이 프로그램 에서 효율 이 낮 고 알고리즘 이 좋 지 않 지만 사상 이 좋 습 니 다.
 
(3) 저 는 생각 을 줄 이 는 것 을 사 용 했 습 니 다. 알고리즘 의 복잡 도가 가장 적 고 gcd 사고방식 으로 계 산 했 습 니 다.맨 앞 에 붙 인 거.