1010 Radix
1010 Radix
注意点
- 如
111 1 1 10类似情况下，若n为个位数，如果本身比另一个数小，则多少的进制都是没有用的(可能会造成空循环而超时)，不过好像没有这么一个测试用例- 进制应该比最少数据中的最大的数要大一，如8最少是9进制的数，z最少是36进制的数
- 注意算法中的超时问题如
9999999999 11 1 10很容易超时，注意匹配的算法- 如果用c等强类型语言写，注意溢出问题，int类型肯定是不够的
python3代码
def getNum(num, radix):
sum = 0
count = 0
for i in num[::-1]:
if i <= '9':
sum += int(i)*pow(radix, count)
else:
sum += (ord(i)-87)*pow(radix, count)
count += 1
return sum
num0 = 0
num1 = 0
data_list = input().split(" ")
if data_list[2] == '1':
num0 = getNum(data_list[0], int(data_list[3]))
num1 = data_list[1]
else:
num0 = getNum(data_list[1], int(data_list[3]))
num1 = data_list[0]
if len(num1) == 1 and getNum(num1, 36) < num0:
print("Impossible")
exit()
max_c = max(num1)
if max_c > '9':
max_c = ord(max_c) - 87
else:
max_c = int(max_c)
radix = max_c + 1
result = getNum(num1, radix)
basic = 5
while result < num0:
radix *= basic
result = getNum(num1, radix)
if result > num0:
radix //= basic
basic = radix // 2
result = getNum(num1, radix)
while result < num0:
if basic == 0:
break
radix += basic
result = getNum(num1, radix)
if result > num0:
radix -= basic
result = getNum(num1, radix)
basic //= 2
if result == num0:
print(radix)
else:
print("Impossible")
更多精彩
