← 返回题目列表

AtCoder · dwango2017final_a

A. 计算演练

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

配点 : 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+可以最大化答案