這是 meelo 原創(chuàng)的 IEEEXtreme極限編程大賽題解
Xtreme 10.0 - Full Adder
題目來源 第10屆IEEE極限編程大賽
https://www.hackerrank.com/contests/ieeextreme-challenges/challenges/full-adder
We would like your help to create a basic adder. However, this adder, should work in any base, with any set of symbols.
Input Format
The first line of input contains an integer b, a space, and a list of b symbols that make up the base. The symbols are listed in order from the least significant symbol to the most significant symbol. In other words, the first symbol listed corresponds to 0, the second corresponds to 1, etc. These symbols can be numbers, uppercase letters, or lowercase letters.
The remaining lines contain the addition problem to be solved, as shown in the sample input and output. The operands will be non-negative numbers expressed in the given base. Note that the last line contains question marks which must be replaced with the correct value.
Constraints
2 ≤ b ≤ 62
The numbers to be added can contain up to 107 symbols.
Output Format
The first four lines of output should be identical to the input. The last line should contain the solution to the problem, with the answer aligned appropriately.
Sample Input
10 0123456789
752
+76045
------
???
Sample Output
10 0123456789
752
+76045
------
76797
Explanation
The first sample corresponds to a normal base-10 addition problem.
Additional sample problems are available if you click on the Run Code
button.
The second sample problem has the following input:
10 wj8Ma04HJg
H
+8J4J
-----
???
This is a base-10 problem with different symbols. H corresponds to the digit 7 and 8J4J is the number 2868. When adding these numbers, the result is 2875, which is represented as 8JH0 in the given base. Thus the expected output is:
10 wj8Ma04HJg
H
+8J4J
-----
8JH0
算法解析
題目要求實現(xiàn)一個加法，但是字符集是輸入的字符集。
需要建立一個字典，表示字符到值得映射；原始表示字符集的字符串，就可以表示值到字符的映射。
加法是從后往前進行的，Python中用range(len(add1)-1, 0, -1)就可以方便的實現(xiàn)。
一個小技巧是在字典中加入一個從空格到0的映射，就可以解決兩個字符串長度不同的問題。
還需要注意，輸出的最后一行之前需要加上合適長度的空格。
程序
Python3
line1 = input()
add1 = input()
add2 = input()
line4 = input()
base, symbols = line1.split(' ')
m = {}
m[' '] = 0 # treat preceding space as 0
base = int(base)
# character -> value
for i, c in enumerate(symbols):
m[c] = i
total = 0
addin = 0
result = ''
# add from back to front
for i in range(len(add1)-1, 0, -1):
total = m[add1[i]] + m[add2[i]] + addin
addin = total // base
result += symbols[total % base]
print(line1)
print(add1)
print(add2)
print(line4)
print(' '*(len(add1)-len(result)) + result[::-1])
