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