配点 : 500 点
問題文
Nico Nico TV-chan决定做一些简单的计算作为心理练习。 顺便说一句,Nico Nico TV酱不是人类,所以她使用逆波兰符号进行计算。
具体来说,
由0 ~ 9, -, + 组成的字符串
根据以下规则计算 S 。
- 首先,创建一个最初为空、无限长的堆栈。 1 我想我有一个。并且, 从正面看字符S 。
- 如果
当出现
0~9时,将其放入堆栈即可。 当出现 - 如果
当出现
+时,从堆栈中删除一个。 a,再拿出一张 b 。和 将 b+a 推入堆栈。 - 如果
当出现
-时,从堆栈中删除一个。 a,再拿出一张 b 。和 将 b-a 推入堆栈。 - 最后,堆栈的内容是 如果是 1 那么这就是答案 如果中间取出的数字不是
- 如果 当出现 1 或者栈为空, S 不是有效的表达式。
Niconico TV-chan随机写入字符串。 我写了 S 。 仅仅计算这个会很无聊,所以我决定解决以下问题。
- 这个字符串 K 你能重写这些字符以使其成为正确的公式吗?另外,如果可能的话,在正确的公式中,计算出的答案的最大值是多少?
但这个问题太难了,请帮我解决一下。 是由
制約
- S 是
对于
0~9、-、+组成的字符串 - 1 ≦ |S| ≦ 52
- 0 ≦ K ≦ |S|
入力
输入将以以下形式从标准输入给出。
K S
出力
如果不能改成正确的公式
请输出 NG 。
如果可以的话
输出 OK ,然后在下一行输出计算出的答案的最大值。
入力例 1
0 21+
出力例 1
OK 3
该表达式可以用普通符号表示为2+1变为
将其重写为
入力例 2
1 21+
出力例 2
OK 11
29+可以最大化答案
入力例 3
1 21-
出力例 3
OK 8
91-可以最大化答案
入力例 4
0 1+1
出力例 4
NG
这样的表达式不是逆波兰表示法的有效表达式 将其重写为
入力例 5
3 1234567
出力例 5
OK 13
12+4+6+可以最大化答案