PAT 1010 Radix
个人学习记录,代码难免不尽人意
Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.
Now for any pair of positive integers N 1and N 2, your task is to find the radix of one number while that of the other is given.
Input Specification:
Each input file contains one test case. Each case occupies a line which contains 4 positive integers:
N1 N2 tag radix
Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.
Output Specification:
For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.
Sample Input 1:
6 110 1 10
Sample Output 1:
2
Sample Input 2:
1 ab 1 2
Sample Output 2:
Impossible
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
const ll inf=(1ll << 63)-1;
int chartoint(char ch){if(ch>='0'&&ch<='9') return ch-'0';else return ch-'a'+10;
}
ll converttoten(string str,ll radix){ll num=0;for(int i=0;i<str.size();i++){num=num*radix+chartoint(str[i]);}if(num<0||num>inf) return -1;return num;
}
int cmp(string n2,ll radix,ll num1){ll num2=converttoten(n2,radix);if(num2<0) return 1;if(num1>num2) return -1;if(num1==num2) return 0;if(num1<num2) return 1;
}
ll binarysearch(string n2,ll left,ll right,ll num1){ll mid;while(left<=right){mid=(left+right)/2;int flag=cmp(n2,mid,num1);if(flag==1) right=mid-1;else if(flag==-1) left=mid+1;else return mid;}return -1;
}
int main(){int tag;ll radix;string n1,n2;cin >> n1 >>n2 >> tag >> radix;if(tag!=1){string temp=n1;n1=n2;n2=temp;}ll num1=0,num2=0;num1=converttoten(n1,radix);ll low=1;for(int i=0;i<n2.size();i++){if(chartoint(n2[i])>low) low=chartoint(n2[i]);}low++;ll upper=max(low,num1)+1;ll res=binarysearch(n2,low,upper,num1);if(res==-1) printf("Impossible\n");else printf("%lld\n",res);return 0;}
这道题很有难度,建议参考《算法笔记》。
相关文章:
PAT 1010 Radix
个人学习记录,代码难免不尽人意 Given a pair of positive integers, for example, 6 and 110, can this equation 6 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number. Now for any pair of positive integers N 1and N 2…...
ruoyi-cloud微服务新建子模块
目录 相关文章1、复制system模块2、在modules下的 pom.xml文件中添加子模块 test3、进入 test模块修改 pom.xml4、修改对应的包名、目录名和启动应用程序为test5、修改bootstrap.yml文件中的端口号和应用名称6、nacos中克隆 system-dev.yml的配置,修改名称为 test-d…...
Dijkstra(求最短路)
时间复杂是 O(n2m) ,n 表示点数,m 表示边数 模板(朴素法一般m等于n^2的时候使用) #include<bits/stdc.h> #include<algorithm> using namespace std; const int N510; int g[N][N]; //为稠密阵所以用邻接矩阵存储 int dist[N]; //用…...
React 脚手架
1.React 定义 React 脚手架(React boilerplate)是一种预先设置好的、可以快速启动 React 项目的工具。脚手架已经包含了 React、Webpack、Babel、ESLint、Jest 等一些常用的工具和库,并已经配置好了这些工具的参数,可以直接使用和…...
CTFSHOW php命令执行
目录 web29 过滤flag web30 过滤system php web31 过滤 cat|sort|shell|\. 这里有一个新姿势 可以学习一下 web32 过滤 ; . web33 web34 web35 web36 web37 data伪协议 web38 短开表达式 web39 web40 __FILE__命令的扩展 web41 web42 重定向…...
侧滑置顶,取消置顶
第一步:布局 <?xml version"1.0" encoding"utf-8"?> <com.ddmh.magic.camera.ui.widget.SwipeMenuLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:app"http://schemas.android.com/apk/res-auto"…...
Pycharm解决启动时候索引慢的问题
设置里去掉update里面的两个勾 shared indexes中,把自动下载索引改成不下载使用本地索引...
Http请求响应时间一般划分标准
HTTP请求的响应时间被认为是长或短通常取决于具体应用场景和性能需求。一般来说,以下是一些常见的对HTTP请求响应时间进行划分的标准: 即时响应:通常在毫秒级别的响应时间被认为是即时响应。这适用于对实时性要求较高的应用,如实时…...
生成测试报告,在Unittest框架中就是简单
测试套件(Test Suite)是测试用例、测试套件或两者的集合,用于组装一组要运行的测试(多个测试用例集合在一起)。 (1)创建一个测试套件: import unittest suite unittest.TestSuite…...
生成式人工智能的潜在有害影响与未来之路(一)
这是本文的第1版,反映了截至2023年5月15日,Generative AI的已记载的和预期的危害。由于Generative AI的发展、使用和危害的快速变化,我们承认这是一篇内在的动态论文,未来会发生变化。 在本文中,我们使用一种标准格式…...
lightdb23.3 表名与包名不能重复
LightDB 表名与包名不能重复 从 LightDB 23.3 版本开始表名和包名不能重复,与 oracle 一致。原先已已支持包名和schema名不能重复。 背景 在之前版本在同一schema 下可以创建相同名字的表和包。这会导致在存储过程中使用%type指定变量类型时,如果存在…...
Oracle 开发篇+Java通过HiKariCP访问Oracle数据库
标签:HikariCP、数据库连接池、JDBC连接池、释义:HikariCP 是一个高性能的 JDBC 连接池组件,号称性能最好的后起之秀,是一个基于BoneCP做了不少的改进和优化的高性能JDBC连接池。 ★ Java代码 import java.sql.Connection; impor…...
进销存管理系统(小杨国贸)springboot采购仓库财务java jsp源代码mysql
本项目为前几天收费帮学妹做的一个项目,Java EE JSP项目,在工作环境中基本使用不到,但是很多学校把这个当作编程入门的项目来做,故分享出本项目供初学者参考。 一、项目描述 进销存管理系统(小杨国贸)spri…...
指针初阶(2)
文章目录 5. 指针和数组6. 二级指针7. 指针数组 附: 5. 指针和数组 指针变量:指针变量就是指针变量,不是数组,指针变量的大小是4/8个字节,专门是用来存放地址的。 数组:数组就是数组,不是指针&a…...
基于Gradio的GPT聊天程序
网上很多别人写的,要用账号也不放心。就自己写了一个基于gradio的聊天界面,部署后可以本地运行。 特点: 可以用openai的,也可以用api2d,其他api可以自己测试一下。使用了langchain的库 可以更改模型,会的…...
包管理工具详解npm 、 yarn 、 cnpm 、 npx 、 pnpm(2023)
1、包管理工具npm (1)包管理工具npm: Node Package Manager,也就是Node包管理器;但是目前已经不仅仅是Node包管理器了,在前端项目中我们也在使用它来管理依赖的包;比如vue、vue-router、vuex、…...
Terraform 系列-批量创建资源时如何根据某个字段判断是否创建
系列文章 Terraform 系列文章Grafana 系列文章 概述 前文 Grafana 系列 - Grafana Terraform Provider 基础 介绍了使用 Grafana Terraform Provider 创建 Datasource. 这几天碰到这么一个现实需求: 使用 Terraform 批量创建日志数据源时, 有的数据源类型是 El…...
Android侧滑栏(一)可缩放可一起移动的侧滑栏
在实际的各类App开发中,经常会需要做一个左侧的侧滑栏,类似于QQ这种。 今天这篇文章总结下自己在开发中遇到的这类可以跟随移动且可以缩放的侧滑栏。 一、实现原理 使用 HorizontalScrollView 实现一个水平方向的可滑动的View,左布局为侧滑…...
简单程度与自负是否相关?探索STM32的学习价值
事实上,无论STM32是否简单并不重要,更重要的是我们能通过学习STM32获得什么。通过STM32,我们可以学习到许多知识:如果我们制作一个键盘或鼠标,我们可以学习USB协议。如果我们制作一个联网设备,我们需要学习…...
第二章:CSS基础进阶-part3:弹性例子布局
文章目录 Flex盒模型二、常见属性2.1 flex属性2.2 justify-content2.3 flex-wrap2.4 flex-flow2.5 align-items2.6 父容器-align-content Flex盒模型 1、普通盒模型 2、弹性盒布局 使用弹性盒布局能让容器的宽度跟随浏览器窗口的变化而变换 二、常见属性 2.1 flex属性 2.2 …...
EvaDB:用SQL桥接数据库与AI模型,构建声明式数据处理流水线
1. 项目概述:当数据库遇上AI,EvaDB想解决什么?如果你最近在关注AI应用开发,尤其是想让大语言模型(LLM)或者计算机视觉模型(CV Model)直接处理你的业务数据,那你大概率会遇…...
量子启发KAN-LSTM:时序建模新架构解析
1. 量子启发的KAN-LSTM架构解析在时序建模领域,传统LSTM网络虽然表现出色,但其参数冗余和表达能力受限的问题一直困扰着从业者。我们团队提出的QKAN-LSTM架构,通过量子力学原理与传统深度学习的创新融合,为解决这些问题提供了全新…...
词级神经语言模型开发实战:从原理到应用
1. 词级神经语言模型开发指南在自然语言处理领域,词级神经语言模型是构建智能文本系统的基石。这类模型通过分析大量文本数据,学习词语之间的概率分布关系,不仅能预测下一个可能出现的单词,还能生成连贯的新文本。我在实际项目中多…...
# 2026年SaaS小程序制作平台对比:乔拓云、有赞、微盟
2026年SaaS小程序制作平台对比:乔拓云、有赞、微盟 SaaS小程序制作平台对比:乔拓云、有赞、微盟的深度剖析 在数字化转型浪潮中,微信小程序已成为企业触达用户、拓展线上业务的核心载体。面对市场上琳琅满目的SaaS小程序制作平台,…...
成品出库系统+ 称重检测:装车重量与订单比对,杜绝 “数量不符” 争议
“客户反馈收到的成品少了 2 箱,仓库却称已按订单发货”“装车时未核对重量,实际数量与订单不符,到货后双方各执一词”“人工清点成品数量耗时久,还易因计数错误导致错发漏发”—— 成品出库环节的 “数量争议”,不仅会…...
源代码论文分享|这份欢迪迈手机商城设计与开发系统资料,真的挺适合拿来学习和参考!
做课程设计或者毕业设计的时候,很多人真正缺的不是“资料”,而是一份能看、能学、能改、还能帮自己理清思路的完整项目。尤其是做商城系统这种题目,网上看起来资源很多,但真正靠谱的,往往不是只有页面截图,…...
超详细 Kubectl 完整命令手册(生产级、全分类、带参数解释+实操示例)
超详细 Kubectl 完整命令手册 (生产级、全分类、带参数解释 实操示例) 一、基础语法 & 全局通用参数 1. 标准语法 kubectl 【子命令】【资源类型】【资源名称】【可选参数】2. 全局必用通用参数参数作用-n, --namespace指定命名空间-A, --all-names…...
从PLC抓包到JSON Schema自动生成:VSCode 2026工业协议插件的7大不可替代能力(附Gitee私有仓迁移教程)
更多请点击: https://intelliparadigm.com 第一章:从PLC抓包到JSON Schema自动生成:VSCode 2026工业协议插件的演进逻辑 工业现场协议解析长期面临“协议黑盒化”困境:Modbus TCP、S7Comm、EtherNet/IP 等流量虽可捕获࿰…...
超越SIFT和ORB:如何用HPatches数据集公平评测你的新局部描述子算法?
超越SIFT和ORB:如何用HPatches数据集公平评测你的新局部描述子算法? 在计算机视觉领域,局部描述子算法一直是特征匹配、图像拼接和三维重建等任务的核心技术。从经典的SIFT、ORB到近年兴起的深度学习描述子,算法的演进从未停止。但…...
