51nod 1449 砝碼稱重，貪心

1449 砝碼稱重

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1449 題目來源：  CodeForces 基準時間限制：1 秒 空間限制：131072 KB 分值: 40  難度：4級算法題

現在有好多種砝碼，他們的重量是  w0,w1,w2,... w0,w1,w2,...  每種各一個。問用這些砝碼能不能表示一個重量為m的東西。

樣例解釋：可以将重物和3放到一個托盤中，9和1放到另外一個托盤中。

Input

單組測試資料。 

第一行有兩個整數w,m (2 ≤ w ≤ 10^9, 1 ≤ m ≤ 10^9)。

Output

如果能，輸出YES，否則輸出NO。

Sample Input

3 7      

Sample Output

YES      

分析：

根據題意，不妨我們假設w=10，那麼砝碼有：

         1；10；100；1000；10000；...........

有這樣的規律：

上面那些砝碼，隻能組成 10010這樣隻有1和0的數字。

如：10010=10000+10；

不妨假設天平左邊放砝碼，是以左邊隻能是 隻含0和1的數字

是以需要把右邊也湊出這種形式

那麼m在什麼情況下可以稱出來呢？

如果m也是隻含有1和0的數字，那不用判斷了，肯定能稱出來；

否則，可以利用砝碼增加m的重量。使得m加上一些砝碼==另一些砝碼

比如m=9，可以加一個1的砝碼，m=m+1=10, 10就可以稱出來了。

如果m=8，隻有一個1的砝碼，湊不到10，是以m=8湊不出來。

同理m=7,6,5，....3,2，都湊不出來。

也就是說，m能成功的情況隻有兩種

1、m隻含有0和1

2、m加上某些砝碼後，變成情況1。

對于情況2，我們應該從m的最低位開始考慮，不妨設m=889，

最低位是9，加上1，就可以使最低位變成0。這步之後m = 889+1 =890

然後第二位是9，同上一步，加上1，      這步之後m = 890+10 = 900

然後第三位是9，同上一步，加上1，       m = 900+100 = 1000

ok，這個m在加上1,10,100三個砝碼之後，重量是1000，是可以稱出來的

舉個反例，如m=79

最低位是9，加上1，可以使這一位變成0,。這步之後 m = 79+1 = 80

第二位是8，沒有砝碼能把8湊到1或0。

是以m=79是稱不出來的。

綜上，我們就按w=10來考慮這個問題，完全可以。

把w推廣到任意數，其實就可以看做把10進制數 轉化 成其他進制 

計算方式與w=10十進制時相同

#include<stdio.h>  
#include<math.h>  
int main()  
{  
    int w,m;  
    scanf("%d%d",&w,&m);
    while(m)  
    {  
        int t=m%w;
        if(t==1||t==0);  //砝碼邊可以放一個砝碼,無需操作 
        else if(w%(t+1)==0)  //t加上1就可以進位了
            m++;     //物邊可以加一個w的r次方平衡一下 ，但低位都沒了，m加1即可
        else    //失敗  
        {  
            puts("NO");
            return 0;
        } 
        m=m/w;  
    }
    puts("YES");  
    return 0;  
}