1449 砝碼稱重 題目來源: CodeForces 基準時間限制:1 秒 空間限制:131072 KB 分值: 40 難度:4級算法題
現在有好多種砝碼,他們的重量是 w0,w1,w2,... 每種各一個。問用這些砝碼能不能表示一個重量為m的東西。
樣例解釋:可以将重物和3放到一個托盤中,9和1放到另外一個托盤中。
Input
單組測試資料。
第一行有兩個整數w,m (2 ≤ w ≤ 10^9, 1 ≤ m ≤ 10^9)。
Output
如果能,輸出YES,否則輸出NO。
Input示例
3 7
Output示例
YES
思路:
1、首先我們考慮将m轉化為w進制數。
2、對于砝碼,每個數值轉化成w進制都是:1 10 100 1000 10000........................因為保證了每個砝碼隻有一個,那麼對應我們w這個數.轉化成w進制之後,對應每一位上邊的數字有三種情況:(假設物品放在左側)
①1,對應在天平右側放置一個對應重量的砝碼。
②0,對應在左右天平都不會出現在這樣重量的砝碼。
③其他數字,那麼很顯然,這個數字是通過減法得來的,也就是說有一些砝碼在左側天平。
那麼不難想到,我們将m轉化為w進制之後,如果遇到了除了0和1的情況,那麼我們肯定想補1,看看物品和左側砝碼的值的和是不是一個隻包含0和1的進制數。
那麼我們倒序查找除了1和0的數字,對應将其補上一個1,并且進位。
補完1之後如果發現還有除了0和1的數值,那麼對應就是NO的情況。相反,就是YES的情況。
Ac代碼:
#include<stdio.h>
#include<string.h>
#include<map>
#include<algorithm>
using namespace std;
int a[10000];
int main()
{
int w,m;
while(~scanf("%d%d",&w,&m))
{
memset(a,0,sizeof(a));
if(w==2)
{
printf("YES\n");
continue;
}
int cont=1;
while(m)
{
a[cont++]=m%w;
m/=w;
}
reverse(a+1,a+cont+1);
for(int i=cont;i>=1;i--)
{
if(a[i]==0||a[i]==1)continue;
else
{
a[i]+=1;
if(a[i]>=w)
{
a[i]=a[i]%w;
a[i-1]++;
}
for(int j=cont-1;j>=0;j--)
{
if(a[i]>=w)
{
a[i]=a[i]%w;
a[i-1]++;
}
}
}
}
int flag=0;
for(int i=0;i<=cont;i++)
{
if(a[i]==0||a[i]==1)continue;
else flag=1;
}
if(flag==0)printf("YES\n");
else printf("NO\n");
}
}