1010 Radix (25 分)
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 N1 and N2, 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
注意点:1.left<=right;
2.数据范围用long long
#include<bits/stdc++.h>
using namespace std; long long digit[]; const long long inf = (1LL<<)-; void init(){ for(char c='';c<='';c++)
digit[c] = c-''; for(char c='a';c<='z';c++)
digit[c] = c-'a'+;
} long long convertNum10(string str1,long long radix,long long t){
long long ans=; long long len = str1.size(); for(long long i=;i<len;i++){
char c=str1[i];
ans=ans*radix+digit[c]; if(ans<||ans>t) return -;
} return ans; } long long cmp(string str2,long long radix,long long t){
long long n2=convertNum10(str2,radix,t);
if(n2<)return ;
else if(n2==t) return ;
else if(n2>t) return ;
else return -; } long long binary_search(string &str2,long long low,long long high,long long t){
long long left=low,right=high;
long long mid; while(left<=right){
mid=(left+right)/; long long flag=cmp(str2,mid,t); if(flag<)left =mid+;
else if(flag>)right = mid-;
else return mid;
} return -; } long long findLargest(string &str){
long long ans=-;
long long len=str.size(); for(long long i=;i<len;i++){
if(digit[str[i]]>ans)
ans=digit[str[i]];
} return ans+; } int main(){
string str1,str2;
long long tag,radix; cin>>str1>>str2>>tag>>radix; init(); if(tag==)
swap(str1,str2); long long t=convertNum10(str1,radix,inf); long long low = findLargest(str2); long long high=max(low,t)+; long long ans=binary_search(str2,low,high,t); if(ans==-)cout<<"Impossible\n";
else cout<<ans<<endl; }
最新文章
- ios UIWebView自定义Alert风格的弹框
- Android-MediaRecorder-音频录制-警告-W/MediaRecorder(13811): mediarecorder went away with unhandled events
- 115个Java面试题和答案——终极列表(下)
- HTML5的新特性及技巧分享总结
- iOS开发网络篇—文件的上传
- 阅读推荐——深入浅出Mesos
- Linux常见问题的处理方法(长期更新)
- 多线程要点--CLR C#学习笔记
- c#启动进程
- sql中truncate 、delete与drop区别
- 【Web Service】WSDL文档
- Android 静默安装/后台安装
- python urllib基础学习
- Spring.net-业务层仓储
- C#操作Xml:使用XmlReader读Xml
- ASP.Net上传文件
- LwIP Application Developers Manual10---LwIP IPv4/IPv6 stacks
- shell脚本使用技巧5--字符分隔
- MOT北京站 | 卓越研发之路:亿万级云端架构演进
- C# ZipHelper C#公共类 -- ZipArchive实现压缩和解压