← 返回题目列表

Codeforces · 343/B

B. 交流电

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

疯狂科学家迈克刚刚完成了一个新设备的建造,以寻找外星智慧生命!第一次启动时,他太着急了,连看都没看一眼就插上电源,立刻开始实验。过了一会儿,迈克发现电线最终纠缠在一起,现在必须再次解开。

该设备由“正”和“负”两根线供电。电线沿着地板从墙壁(左侧)延伸到设备(右侧)。墙壁和设备在同一水平面上都有两个触点,电线按某种顺序插入其中。如果有一个或多个地方一根电线高于另一根电线,则认为电线缠结。例如下图就有四个这样的地方(俯视图):

Mike 知道电线在彼此上方运行的顺序。迈克还注意到,在左侧,“+”线始终插入顶部触点(如图所示)。他想在不拔掉插头、不移动设备的情况下解开电线。确定是否可以这样做。电线可以在地板上自由移动和拉伸,但不能被切断。

为了更好地理解问题,请阅读测试示例的注释。

输入

单行输入包含长度为 n (1 ≤ n ≤ 100000) 的字符“+”和“-”序列。序列的第 i (1 ≤ i ≤ n) 个位置包含字符“+”,如果在距离墙壁第 i 个台阶上“正”线位于“负”线上方,否则包含字符“-”。

输出

如果电线可以解开,则打印“是”(不带引号);如果电线无法解开,则打印“否”(不带引号)。

示例

输入 #1

-++-

输出 #1

Yes

输入 #2

+-

输出 #2

No

输入 #3

++

输出 #3

Yes

输入#4

-

输出#4

No

注意

第一个测试用例对应于语句中的图片。要解开电线,可以先将“正”线移低,从而消除中间的两个十字,然后将其拉到“负”线下方,也消除剩余的两个十字。

在第二个测试用例中,“正”线绕“负”线旋转一整圈。因此,电线无法解开:

在第三个测试用例中,“正”线只是按顺序在“负”线上方运行两次。通过提起“plus”并将其移得更高可以解开缠结的电线:

在第四个测试用例中,“负”线在“正”线上运行一次。如果不移动设备本身,就无法解开电线: