Magnet Chain
Time limit1sMemory limit256 MB
Given up to 5 magnets as a 1/2 sequence, decide whether the chain is fully connected after at most one magnet flip.
- Level
Easy2 of 10
- Topics
- Implementation, Brute force, Simulation, Math
- Solved
- No attempts yet
Problem
Gwanbin, an elementary school student who has heard about blockchain, wants to stick magnets together to make a magnet chain and then use it to create a virtual currency.
Gwanbin has unusual magnets: the (+) pole of each magnet has the number 1 written on it, and the (-) pole has the number 2. Each magnet is shaped like a rod and has exactly one (+) pole and one (-) pole.
Normally, magnets repel poles of the same kind and attract poles of different kinds, sticking together. Using this property, Gwanbin carefully stuck all his magnets together into a connected magnet chain and fell asleep dreaming that his magnet coin would soar. But that night, Gwanbin's father, worried about the magnet coin soaring, may have flipped the direction of one of the connected magnets and broken the magnet chain! For Gwanbin, who fears a crash of the magnet coin, determine whether the magnet chain is still fully connected.
Input
The first line gives N, the number of magnets Gwanbin has. (3 ≤ N ≤ 5)
The second line gives a sequence a1a2a3 ... a2N (each ai is 1 or 2) representing the current connection state of Gwanbin's magnets. Starting from the left end of the sequence, each pair of adjacent numbers in order represents one magnet. ( [a1a2][a3a4]... ) In the sequence, 1 represents the (+) pole and 2 represents the (-) pole.
At most one magnet may be flipped compared to the original state (the state in which all magnets are connected).
Output
Based on the current state of the magnets, print "Yes" on one line if they are all connected, or "No" if they are not all connected. When printing, omit the quotation marks ("") and match the case exactly.