分数: 100 点
问题陈述
京都大学的一栋建筑需要密码才能进入。
该密码由小写字母组成,您(大楼的使用者之一)知道该密码。
建筑物的身份验证系统根据输入的密码计算哈希值,并检查哈希值是否匹配。
字符串的哈希值 S 长度 N 根据以下公式计算。
A^1 \times C[S_1] + A^2 \times C[S_2] + ... + A^N \times C[S_N]
A 是大于或等于的整数 2 且小于或等于 10,和 C[a]=1, C[b]=2, ..., C[z]=26.
您太忙了,想用尽可能短的密码通过认证。
找到最短的密码,其哈希值与原始密码相同。 如果存在多个最小长度的密码,请找到字典顺序最大的一个。
约束
- 2 \leq A \leq 10
- A 是一个整数。
- 1 \leq |S| \leq 1,000
- S 由小写字母组成。
输入
输入由标准输入按以下格式给出:
A S
输出
打印上面所需的密码。
示例输入 1
2 kupc
示例输出 1
yzp
原始字符串的哈希值为
2^1 \times 11 + 2^2 \times 21 + 2^3 \times 16 + 2^4 \times 3 = 282.
输出的哈希值也是
2^1 \times 25 + 2^2 \times 26 + 2^3 \times 16 = 282.
示例输入 2
10 abcde
示例输出 2
utuvc
示例输入 3
4 zzz
示例输出 3
zzz
示例输入 4
9 kyotouniversityprogrammingcontest
示例输出 4
txxsxtwztwyrrsyyzwxyrtuzuxsvvswzs
在某些情况下,哈希值非常大。 有