首页 > 试题广场 >

Radix (25)

[编程题]Radix (25)

热度指数：7063 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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.

输入描述:

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.

输出描述:

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.

示例1

输入

6 110 1 10

输出

2<br/>Sample Input 2:<br/>1 ab 1 2<br/>Sample Output 2:<br/>Impossible

算法知识视频讲解

Python

初心者托奇

# 今天才知道二分法的强大，题目的用例化简之后居然超过了2 的50次幂，真是丧心病狂！

import sys
a = input().split(' ')
b = a[int(a[2]) - 1]
m = 0;p = 36;q = pow(2,60);f = 0
j = len(b) - 1
for i in b:
    if i <= 'z' and i >= 'a':
        i = ord(i) - 87
    m += int(i) * (int(a[3]) ** j)
    j -= 1

def jian(x):
    n = 0
    j = len(a[2 -int(a[2])]) - 1
    for i in a[2 -int(a[2])]:
        if i <= 'z' and i >= 'a':
            i = ord(i) - 87
        n += int(i) * (x ** j)
        j -= 1
    return n
   
while f == 0:
    n = jian(p)
    if m == n:
        print(p);sys.exit(0)
    elif m < n:
        f = 1
    else:
        f = 2

while f == 1:
    if n > m:
        p -= 1
    elif n < m&nbs***bsp;p < 2 :
        print('Impossible');sys.exit(0)
    else:
        print(p);sys.exit(0)
    n = jian(p)

while f == 2:
    if m < n:
        p += q
    elif m == a:
        print(p);sys.exit(0)
    else:
        break
    n = jian(p)

while f:
    q = (q + 1) // 2
    if n > m:
        p -= q
    elif n < m:
        p += q
    else:
        print(p);sys.exit(0)
    if q == 1:
        f -= 1
    n = jian(p)
print('Impossible')

发表于 2020-01-28 15:56:58 回复(0)