罗马数字

要正确地用罗马数字表达一个数，必须遵循一些基本规则。尽管符合规则的写法有时会多于一种，但对每个数来说总是存在一种“最好的”写法：

例如，至少有六种写法可以表达16这个数：

IIIIIIIIIIIIIIII

VIIIIIIIIIII

VVIIIIII

XIIIIII

VVVI

XVI

根据规则，应采用最后一种写法，因为它最为简洁（使用的字符最少）。

在文件roman.txt中包含了一千个罗马数字，且并一定不都是最简洁的写法；若将这些数都改写为标准写法（即最简洁的写法），求所能节省的总字符数。

注意：文件中的所有罗马数字都中不会连续出现四个以上的相同字符。

本题难度:

解答

并无值得一提之处。先递归计算罗马数字的值，再用循环将值转化为标准写法，比较两者长度之差。结果是$743$。

x=[1000,900,500,400,100,90,50,40,10,9,5,4,1]
y="M CM D CD C XC L XL X IX V IV I".split()
d=dict(zip(y,x))

def val(t):
    if len(t)==0:
        return 0
    elif len(t)==1:
        return d[t]
    else:
        i=0
        while y[i] not in t:
            i+=1
        k=t.index(y[i])
        return x[i]+val(t[k+len(y[i]):])-val(t[:k])

s=[]
with open("089_roman.txt") as f:
    for line in f:
        s.append(line.strip())
res=0

for c in s:
    i,r,a=0,"",val(c)
    while a>0:
        r+=y[i]*(a//x[i])
        a=a%x[i]
        i+=1
    res=res+len(c)-len(r)

print res