Xtreme 10.0 - Full Adder
这是 meelo 原创的 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
算法解析
题目要求实现一个加法，但是字符集是输入的字符集。
需要建立一个字典，表示字符到值得映射；原始表示字符集的字符串，就可以表示值到字符的映射。
加法是从后往前进行的，Python中用range(len(add1)-1, 0, -1)就可以方便的实现。
一个小技巧是在字典中加入一个从空格到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])
