← 返回题目列表

AtCoder · tenka1_2015_qualB_d

D. 天下一计算器英语作文

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

問題文

Yoshio喜欢用计算器写英语作文,但他写不出很好的英语作文。让我们为吉雄写最好的英语作文吧。

计算器上显示的数字在倒过来看时可以看作是英文字符串。例如:

0.7734

从另一边看hELLO

这就是 Yoshio 喜欢用计算器写英语的方式。顺便说一句,Yoshio 使用的转换表如下。

数字 英字
0 O
D
1 I
2 Z
3 E
4 h
5 s
6 q
7 L
8 B
9 G

根据 Yoshio 的说法,分数越高,英文字母串越好。
从其原始方向看,每个字母串的分数与计算器上显示该字符串时的数字相同。
换句话说,EGG如果 993 点、ODDEGG如果 993000 点。

另外,像普通计算器一样,最高有效数字是 您无法创建成为 0 的整数。
如果最后一个字符是O或 如果要创建像D这样的英文字符串,则需要使用小数点。
换句话说,如上图示例所示,hELLO的分数是 0.7734 点。
一方hELLOEGG如果 交换 99307734 点。
但是,根据计算器上的显示,最后一个 可以添加 0 。 可以显示
换句话说,OLD,分数为 0.7 点。

Yoshio 具有最大显示位数 D 计算器和 我有一本词汇书,其中包含 N 个单词。
单词书上的英语单词串可以在此计算器上显示的最高分数是多少?
词汇列表中包含的单词 W_1, W_2, ..., W_N 它们的编号最大为 1 选择并以任意顺序连接的英文字符串中,字符串长度为 D 找出以下分数中的最高分。
但是,您不能从词汇列表中多次选择同一个单词。


入力

输入将以以下形式通过标准输入给出。

D
N
W_1
W_2
:
W_N
  • 1 行包含一个整数,表示计算器上显示的最大位数。 给出 D ( 1 \leq D \leq 200 )。
  • 2 行包含一个整数,表示词汇列表中包含的单词数。 N ( 1 \leq N \leq 10000 )。
  • 3 来自行 N 行包含词汇列表中包含的单词。 W_i ( 1 \leq |W_i| \leq {\rm min}(32, D) )。
    这些话是1 以每行一个字的形式给出。
    W_i 是转换表中包含的字符O,D,I,Z,E,h,s,q,L,B,G'' 并且没有其他字符。
  • i \neq j 如果 W_i \neq W_j 。

出力

最高分 1 行输出。

如果答案是小数,则尾随 应从输出中删除 0 。另外,小数点以下的所有内容都是 0 应作为整数输出。

在输出末尾包含换行符。 如果所有满足

配点

针对此问题设置了部分分数。 如果正确答案是满足

  • N \leq 8 的测试用例都得到正确回答,45 分被给予。
  • 如果所有测试用例都回答正确,除上述之外, 75 分被给予。

入力例1

9
4
hELLO
hELL
EGG
ODD

出力例1

773407734

会给你最高分的英文字符串是hELLOhELL。


入力例2

5
3
ZO
OIO
IOIO

出力例2

0.201

会给你最高分的英文字符串是OIOZO。


入力例3

25
10
BED
BEL
BIG
DIE
DIG
DOG
OLD
shE
qED
ZOO

出力例3

918910900738345310070038

会给你最高分的英文字符串是BEDOLDDIEshEBELDOGDIGBIG。


入力例4

5
1
hELLO

出力例4

0.7734

如上图所示,小数点不消耗计算器上显示的位数,因此位数 可以使用 D=5 计算器来显示。