codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

343B.md (3135B)


      1 Source: https://codeforces.com/problemset/problem/343/B
      2 
      3 B. Alternating Current
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Mad scientist Mike has just finished constructing a new device to search for extraterrestrial intelligence! He was in such a hurry to launch it for the first time that he plugged in the power wires without giving it a proper glance and started experimenting right away. After a while Mike observed that the wires ended up entangled and now have to be untangled again.
     22 
     23 The device is powered by two wires "plus" and "minus". The wires run along the floor from the wall (on the left) to the device (on the right). Both the wall and the device have two contacts in them on the same level, into which the wires are plugged in some order. The wires are considered entangled if there are one or more places where one wire runs above the other one. For example, the picture below has four such places (top view):
     24 
     25  ![](https://espresso.codeforces.com/1309816e52de0c0bf3660cd3ab3757d3db8267fb.png) 
     26 
     27 Mike knows the sequence in which the wires run above each other. Mike also noticed that on the left side, the "plus" wire is always plugged into the top contact (as seen on the picture). He would like to untangle the wires without unplugging them and without moving the device. Determine if it is possible to do that. A wire can be freely moved and stretched on the floor, but cannot be cut.
     28 
     29 To understand the problem better please read the notes to the test samples.
     30 
     31 Input
     32 
     33 The single line of the input contains a sequence of characters "+" and "-" of length *n* (1 ≤ *n* ≤ 100000). The *i*-th (1 ≤ *i* ≤ *n*) position of the sequence contains the character "+", if on the *i*-th step from the wall the "plus" wire runs above the "minus" wire, and the character "-" otherwise.
     34 
     35 Output
     36 
     37 Print either "Yes" (without the quotes) if the wires can be untangled or "No" (without the quotes) if the wires cannot be untangled.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 -++-
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 Yes
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 +-
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 No
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 ++
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 Yes
     75 ```
     76 
     77 Input
     78 
     79 ```
     80 -
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 No
     87 ```
     88 
     89 Note
     90 
     91 The first testcase corresponds to the picture in the statement. To untangle the wires, one can first move the "plus" wire lower, thus eliminating the two crosses in the middle, and then draw it under the "minus" wire, eliminating also the remaining two crosses.
     92 
     93 In the second testcase the "plus" wire makes one full revolution around the "minus" wire. Thus the wires cannot be untangled:
     94 
     95  ![](https://espresso.codeforces.com/94481ff58b8789cb514d3430a4d76be9477aeff1.png) 
     96 
     97 In the third testcase the "plus" wire simply runs above the "minus" wire twice in sequence. The wires can be untangled by lifting "plus" and moving it higher:
     98 
     99  ![](https://espresso.codeforces.com/114e8a8b1f051256f7436bd6bec7b9ffd4525286.png) 
    100 
    101 In the fourth testcase the "minus" wire runs above the "plus" wire once. The wires cannot be untangled without moving the device itself:
    102 
    103  ![](https://espresso.codeforces.com/f75ea84222f5fce465aeb9cd90ee0a43ac529e1d.png)