← 返回题目列表

AtCoder · kupc2017_c

C. 最佳密码

中文机器翻译题面 查看原题

分数: 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

在某些情况下,哈希值非常大。 有