当前位置: 首页 > news >正文

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

个人学习记录&#xff0c;代码难免不尽人意 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的配置&#xff0c;修改名称为 test-d…...

Dijkstra(求最短路)

时间复杂是 O(n2m) &#xff0c;n 表示点数&#xff0c;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 脚手架&#xff08;React boilerplate&#xff09;是一种预先设置好的、可以快速启动 React 项目的工具。脚手架已经包含了 React、Webpack、Babel、ESLint、Jest 等一些常用的工具和库&#xff0c;并已经配置好了这些工具的参数&#xff0c;可以直接使用和…...

CTFSHOW php命令执行

目录 web29 过滤flag web30 过滤system php web31 过滤 cat|sort|shell|\. 这里有一个新姿势 可以学习一下 web32 过滤 &#xff1b; . 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中&#xff0c;把自动下载索引改成不下载使用本地索引...

Http请求响应时间一般划分标准

HTTP请求的响应时间被认为是长或短通常取决于具体应用场景和性能需求。一般来说&#xff0c;以下是一些常见的对HTTP请求响应时间进行划分的标准&#xff1a; 即时响应&#xff1a;通常在毫秒级别的响应时间被认为是即时响应。这适用于对实时性要求较高的应用&#xff0c;如实时…...

生成测试报告,在Unittest框架中就是简单

测试套件&#xff08;Test Suite&#xff09;是测试用例、测试套件或两者的集合&#xff0c;用于组装一组要运行的测试&#xff08;多个测试用例集合在一起&#xff09;。 &#xff08;1&#xff09;创建一个测试套件&#xff1a; import unittest suite unittest.TestSuite…...

生成式人工智能的潜在有害影响与未来之路(一)

这是本文的第1版&#xff0c;反映了截至2023年5月15日&#xff0c;Generative AI的已记载的和预期的危害。由于Generative AI的发展、使用和危害的快速变化&#xff0c;我们承认这是一篇内在的动态论文&#xff0c;未来会发生变化。 在本文中&#xff0c;我们使用一种标准格式…...

lightdb23.3 表名与包名不能重复

LightDB 表名与包名不能重复 从 LightDB 23.3 版本开始表名和包名不能重复&#xff0c;与 oracle 一致。原先已已支持包名和schema名不能重复。 背景 在之前版本在同一schema 下可以创建相同名字的表和包。这会导致在存储过程中使用%type指定变量类型时&#xff0c;如果存在…...

Oracle 开发篇+Java通过HiKariCP访问Oracle数据库

标签&#xff1a;HikariCP、数据库连接池、JDBC连接池、释义&#xff1a;HikariCP 是一个高性能的 JDBC 连接池组件&#xff0c;号称性能最好的后起之秀&#xff0c;是一个基于BoneCP做了不少的改进和优化的高性能JDBC连接池。 ★ Java代码 import java.sql.Connection; impor…...

进销存管理系统(小杨国贸)springboot采购仓库财务java jsp源代码mysql

本项目为前几天收费帮学妹做的一个项目&#xff0c;Java EE JSP项目&#xff0c;在工作环境中基本使用不到&#xff0c;但是很多学校把这个当作编程入门的项目来做&#xff0c;故分享出本项目供初学者参考。 一、项目描述 进销存管理系统&#xff08;小杨国贸&#xff09;spri…...

指针初阶(2)

文章目录 5. 指针和数组6. 二级指针7. 指针数组 附&#xff1a; 5. 指针和数组 指针变量&#xff1a;指针变量就是指针变量&#xff0c;不是数组&#xff0c;指针变量的大小是4/8个字节&#xff0c;专门是用来存放地址的。 数组&#xff1a;数组就是数组&#xff0c;不是指针&a…...

基于Gradio的GPT聊天程序

网上很多别人写的&#xff0c;要用账号也不放心。就自己写了一个基于gradio的聊天界面&#xff0c;部署后可以本地运行。 特点&#xff1a; 可以用openai的&#xff0c;也可以用api2d&#xff0c;其他api可以自己测试一下。使用了langchain的库 可以更改模型&#xff0c;会的…...

包管理工具详解npm 、 yarn 、 cnpm 、 npx 、 pnpm(2023)

1、包管理工具npm &#xff08;1&#xff09;包管理工具npm&#xff1a; Node Package Manager&#xff0c;也就是Node包管理器&#xff1b;但是目前已经不仅仅是Node包管理器了&#xff0c;在前端项目中我们也在使用它来管理依赖的包&#xff1b;比如vue、vue-router、vuex、…...

Terraform 系列-批量创建资源时如何根据某个字段判断是否创建

系列文章 Terraform 系列文章Grafana 系列文章 概述 前文 Grafana 系列 - Grafana Terraform Provider 基础 介绍了使用 Grafana Terraform Provider 创建 Datasource. 这几天碰到这么一个现实需求&#xff1a; 使用 Terraform 批量创建日志数据源时, 有的数据源类型是 El…...

Android侧滑栏(一)可缩放可一起移动的侧滑栏

在实际的各类App开发中&#xff0c;经常会需要做一个左侧的侧滑栏&#xff0c;类似于QQ这种。 今天这篇文章总结下自己在开发中遇到的这类可以跟随移动且可以缩放的侧滑栏。 一、实现原理 使用 HorizontalScrollView 实现一个水平方向的可滑动的View&#xff0c;左布局为侧滑…...

简单程度与自负是否相关?探索STM32的学习价值

事实上&#xff0c;无论STM32是否简单并不重要&#xff0c;更重要的是我们能通过学习STM32获得什么。通过STM32&#xff0c;我们可以学习到许多知识&#xff1a;如果我们制作一个键盘或鼠标&#xff0c;我们可以学习USB协议。如果我们制作一个联网设备&#xff0c;我们需要学习…...

第二章: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 …...

AI Agent开发资源全指南:从框架选择到项目实战

1. 项目概述&#xff1a;AI Agent生态的“Awesome”清单如果你最近在关注AI领域&#xff0c;尤其是AI Agent&#xff08;智能体&#xff09;这个方向&#xff0c;可能会感觉信息爆炸。每天都有新的框架、工具、论文和应用冒出来&#xff0c;从AutoGPT到LangChain&#xff0c;从…...

企业级语义搜索实战:基于WideSearch构建智能知识检索系统

1. 项目概述&#xff1a;从“宽搜”到企业级知识检索的跃迁最近在折腾企业内部知识库和文档检索系统&#xff0c;发现了一个挺有意思的开源项目——ByteDance-Seed/WideSearch。这个名字直译过来是“宽搜”&#xff0c;听起来有点抽象&#xff0c;但当你深入进去&#xff0c;会…...

React Reconciliation 算法理解

React Reconciliation算法理解 React作为现代前端开发的核心框架&#xff0c;其高效的渲染机制一直是开发者关注的焦点。而Reconciliation&#xff08;协调&#xff09;算法正是React实现高效更新的核心。它通过智能比较虚拟DOM的差异&#xff0c;最小化真实DOM操作&#xff0…...

监控仪表板:实时数据可视化与交互式探索

监控仪表板&#xff1a;实时数据可视化与交互式探索 在当今数据驱动的时代&#xff0c;企业需要快速获取、分析并响应海量数据。监控仪表板作为一种高效的数据展示工具&#xff0c;能够将复杂的数据转化为直观的可视化图表&#xff0c;帮助用户实时掌握业务动态。无论是生产线…...

2026跨境独立站技术选型:Taoify API全开放架构,打造国产Shopify平替的技术壁垒

随着跨境电商向精细化、规模化发展&#xff0c;企业对独立站的技术适配性、系统扩展性要求持续提升&#xff0c;传统海外建站工具&#xff08;如Shopify&#xff09;的封闭架构、高佣金模式、响应滞后等问题&#xff0c;已难以满足国内中小外贸企业、工厂及新手卖家的核心需求。…...

字节开源trae-agent:Rust构建的高性能服务网格数据平面解析

1. 项目概述&#xff1a;一个现代服务网格数据平面的诞生最近在梳理服务网格生态时&#xff0c;我注意到了字节跳动开源的trae-agent。这个名字乍一看有点陌生&#xff0c;不像Envoy、Linkerd-proxy那样如雷贯耳&#xff0c;但深入了解后&#xff0c;我发现它代表了一种非常务实…...

为什么你的FP16算子在CUDA 13.2上反而变慢?深度解析Warp Matrix Instructions兼容性陷阱(附NVCC编译参数黄金组合)

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;FP16算子性能退化现象与问题定位全景图 在混合精度训练中&#xff0c;FP16&#xff08;半精度浮点&#xff09;本应提升计算吞吐并降低显存占用&#xff0c;但实践中常观察到部分算子&#xff08;如 L…...

如何实现SQL存储过程日志记录_建立标准化审计表方案

...

词级神经语言模型开发实战:从原理到应用

1. 词级神经语言模型开发指南在自然语言处理领域&#xff0c;词级神经语言模型是构建智能文本系统的基石。这类模型通过分析大量文本数据&#xff0c;学习词语之间的概率分布关系&#xff0c;不仅能预测下一个可能出现的单词&#xff0c;还能生成连贯的新文本。我在实际项目中多…...

2026届最火的AI辅助写作平台实测分析

Ai论文网站排名&#xff08;开题报告、文献综述、降aigc率、降重综合对比&#xff09; TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 在人工智能进行交互期间&#xff0c;指令存在冗余情形常常会致使输出出现偏差以及造成效率方…...