AcWing——砝码称重

简介: AcWing——砝码称重

4942. 砝码称重 - AcWing题库

1、题目

给定一个天平和 101 个砝码。


101 个砝码的重量依次为 n⁰,n¹,n²,…,n¹⁰⁰ 克,其中 n 是一个不小于 2 的整数。


请你判断,我们能否利用给定天平和砝码对重量为 m 克的物品进行称重。


注意,天平的两端都可以放入砝码。


具体来说,你的任务是判断是否可以在天平的左盘放入重量为 m克的物品以及一些砝码(也可以不放砝码),并在天平的右盘放入一些砝码,从而使得天平的两端可以保持平衡。


不要求用到所有砝码,挑选合适的砝码使用即可。


例如,如果 n=3,m=7,则我们可以在天平的左盘放入重量为 7 克的物品以及重量为 3 克的砝码,并在天平的右盘放入重量为 1,9克的砝码,这样可以使得天平两端保持平衡。


输入格式


共一行,包含两个整数 n,m。


输出格式


如果可以对重量为 m 克的物品进行称重,则输出 YES,否则输出 NO。


数据范围


前 5 个测试点满足 2≤n≤100,1≤m≤100。

所有测试点满足 2≤n≤10⁹,1≤m≤10⁹。


输入样例1:

3 7

输出样例1:

YES

输入样例2:

100 99

输出样例2:

YES

题目解读

题目会给两个数,n和m,要求我们可以使用 101 个砝码(101 个砝码的重量依次 为 n⁰,n¹,n²,…,n¹⁰⁰ 克,其中 n 是一个不小于 2 的整数)。是否可以在天平的左盘放入重量为 m克的物品以及一些砝码(也可以不放砝码),并在天平的右盘放入一些砝码,从而使得天平的两端可以保持平衡。

这可以转化成m是否可以由n进制表示出来,但是n进制上面的数只能是0(不放),1(放在物品对面),-1(放在物品这边),所以我们只需要求n进制的m每一位上面是否是0,1,-1,如果不是则说明无法对重量为 m克的物品进行称重,输出NO。

此时有小伙伴就发现了

m, n都是正数啊,两个取余不可能得到-1这个结果,那我们应该怎么办?

我们把判断 -1 换成判断 n-1

为什么可以这样换?Java中余数可以是负数,在数学中余数不能是负数

举个例子:-9%10 = -9(Java表示),-9%10 = -1* 10 + 1(数学表示);

发现什么没,左边的 -9 和右边的 10 - 9 = 1 是一样的;

所以我们可以把判断-1换成判断n-1

10 9

9= -1 * 10⁰ + 1*10¹

3、代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        while (m!=0){
            int i=m%n;
            if (i!=0&&i!=1&&i!=n-1){
                System.out.println("NO");
                return;
            }
            if (i > 1)//i=n-1 转换回 n=-1
                i = -1;
            m = (m - i) / n;
        }
        System.out.println("YES");
    }
}


目录
相关文章
|
8月前
|
人工智能 缓存 Cloud Native
解锁 DeepSeek 安全接入、稳定运行新路径
聚焦于企业部署 DeepSeek 的应用需求,本文介绍了模型权重下载及多种部署方案,还阐述了大模型应用落地的常见需求,帮助用户逐步提升模型应用效果。
1100 254
Manacher(马拉车)算法详解
该文章详细解释了Manacher算法,这是一种高效找出给定字符串最长回文子串的算法,通过在字符串中插入特殊字符构建新的字符串,并利用中心扩展策略来找出最长回文序列,时间复杂度为O(N),空间复杂度为O(N)。
|
8月前
|
算法 定位技术 vr&ar
基于WebGIS技术的校园地图导航系统解决方案
本文提出了一套基于WebGIS技术的校园地图导航系统构建与优化方案,通过校园三维地图、路线导航、特色路线、位置分享等核心功能机框架设计,旨在为用户提供高效、智能、个性化的导航体验。
419 0
基于WebGIS技术的校园地图导航系统解决方案
|
10月前
|
人工智能 数据可视化 JavaScript
NodeTool:AI 工作流可视化构建器,通过拖放节点设计复杂的工作流,集成 OpenAI 等多个平台
NodeTool 是一个开源的 AI 工作流可视化构建器,通过拖放节点的方式设计复杂的工作流,无需编码即可快速原型设计和测试。它支持本地 GPU 运行 AI 模型,并与 Hugging Face、OpenAI 等平台集成,提供模型访问能力。
394 14
NodeTool:AI 工作流可视化构建器,通过拖放节点设计复杂的工作流,集成 OpenAI 等多个平台
|
关系型数据库 数据库 PostgreSQL
pg下delete数据后。除了使用VACUUM FULL TABLE 才能释放磁盘空间外的方法。
【8月更文挑战第12天】pg下delete数据后。除了使用VACUUM FULL TABLE 才能释放磁盘空间外的方法。
726 1
|
存储 设计模式 安全
探索设计模式的魅力:备忘录模式揭秘-实现时光回溯、一键还原、后悔药、历史的守护者和穿越时空隧道
备忘录模式是一种行为设计模式,允许在不破坏对象封装性的情况下保存和恢复对象的内部状态。该模式通过创建备忘录对象来存储发起人的状态信息,发起人可根据需要创建和恢复备忘录。管理者则负责保存和管理备忘录,但无法访问其内容。备忘录模式简化了状态管理,支持撤销操作和历史记录功能,提高了系统的灵活性和可用性。在实际应用中,备忘录模式常用于文本编辑器、游戏和数据库事务处理等场景,确保对象状态的安全恢复和有效管理。通过备忘录模式,开发人员可以更好地控制对象状态的变化,提升软件系统的健壮性和用户体验。
319 1
探索设计模式的魅力:备忘录模式揭秘-实现时光回溯、一键还原、后悔药、历史的守护者和穿越时空隧道
|
Java Spring
sprinboot+人大金仓配置
sprinboot+人大金仓配置
1006 0
详解CAN总线:CAN总线报文格式—数据帧
CAN总线上传输的信息称为报文,当总线空闲时任何连接的单元都可以开始发送新的报文。
详解CAN总线:CAN总线报文格式—数据帧
|
前端开发 JavaScript Java
基于springboot+vue的江西旅游网(前后端分离)
本系统为原创项目,以江西旅游为主题,采用前后端分离,创作于2022年4月,项目代码工整,结构清晰,适合选题:旅游、旅游攻略、**旅游网、前后端分离类其他旅游系统等。系统采用springboot+vue整合开发,前端主要使用了element-ui框架、项目后端主要使用了springboot,数据层采用mybatis。
基于springboot+vue的江西旅游网(前后端分离)
|
分布式计算 资源调度 Ubuntu
Hadoop完全分布式环境搭建(三节点)
基于Ubuntu 16.04 搭建 Hadoop-2.7.2大数据平台
1078 2
Hadoop完全分布式环境搭建(三节点)

热门文章

最新文章