问题描述

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​₁and N₂ , 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:
N₁ N₂ tag radix
Here N₁ and N₂ 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 N₁ if tag is 1, or of N₂ if tag is 2.
Output Specification:
For each test case, print in one line the radix of the other number so that the equation N₁ = N₂ is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.

解决方法

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
typedef long long LL;
/*
  一开始这些用例无法通过 6 8 10 12 13 15 16 溢出的情况处理出错
  题目中并没有说对比的数转换为十进制无溢出,看了算法笔记后才知晓
*/

//初始化map做字符和数字的映射
map<char, int> m;
void init()
{
  for (int i = '0'; i <= '9'; i++)
  {
    m[i] = i - '0';
  }
  for (int i = 'a'; i <= 'z'; i++)
  {
    m[i] = i - 'a' + 10;
  }
}

//设置转换为十进制的方法
LL convertTen(char a[], LL radix)
{
  int length = strlen(a);
  LL res = 0L;
  for (int i = 0; i < length; i++)
  {
    //从高位向低位遍历
    res = res * radix + m[a[i]];
    //处理溢出情况
    if (res < 0)
    {
      return -1;
    }
  }
  return res;
}
//输出所有位的最大的数
int maxPos(char a[])
{
  int length = strlen(a);
  int max = 0;
  for (int i = 1; i < length; i++)
  {
    if (m[a[i]] > m[a[max]])
    {
      max = i;
    }
  }
  return m[a[max]];
}
//二分查找所需进制
LL binaryRadix(char a[], LL left, LL right, LL flag)
{
  while (left <= right)
  {
    LL mid = left + (right - left) / 2;
    LL midVal = convertTen(a, mid);
    //如果溢出 就认为midVal > flag
    if(midVal == -1)
    {
      right = mid - 1;
      continue;
    }
    if (midVal < flag)
    {
      left = mid + 1;
    }
    else if (midVal > flag)
    {
      right = mid - 1;
    }
    else
    {
      return mid;
    }
  }
  return -1;
}

int main(void)
{
  char a[11], b[11], temp[11];
  LL radix, flag, maxp,tag;
  scanf("%s %s %lld %lld", a, b, &tag, &radix);
  init();
  //始终把对比的数放在a处
  if (tag == 2)
  {
    strcpy(temp, a);
    strcpy(a, b);
    strcpy(b, temp);
  }
  flag = convertTen(a, radix);
  maxp = maxPos(b);
  LL result = binaryRadix(b, maxp + 1, flag + 1, flag);
  if (result != -1)
  {
    printf("%lld", result);
  }
  else
  {
    printf("Impossible");
  }
  return 0;
}

基本策略

• 主要是依照进制越大转换出的数就越大

注意点(解释的还是不是很好)

• 因为本身只能取到z,如果N₂是一位相等的话最小上界等于下界也等于N₁+1
• 如果N₂至少是两位相等的最小上界为N₁+1且一定大于下界,如果再大就会导致相等时N2不能有两位

结果展示

PatA1010.png