Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Railroad cars numbered 1 , 2 , . . . , n on the right track are to be permuted and moved along on the
Railroad cars numbered n on the right track are to be permuted and moved along on the left track. A car may be moved directly onto the left track, or it may be shunted onto the siding to be removed at a later time and placed on the left track. The siding thus operates as a stack, a push operation moving a car from the right track onto the siding and a pop operation moving the "top" car from the siding onto the left track. For example, when n push push move pop pop arranges them in the order
Are any permutations not possible? Yes, for example, is an impossible permutation.
Assume that the train arriving from the direction A has N coaches numbered in increasing order N The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the same direction so that their order will be Your job is to help him to write a program that decides whether it is possible to get the required order of coaches.
You can assume that single coaches can be disconnected from the train before they enter the station and that they can move until they are on the track in the same direction. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track on the right and also once it has left the station in the direction on the left it cannot return back to the station.
input
The input file consists of blocks of lines, each of which is a test case. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block, there is the integer N which is the number of coaches in the train. In each of the next lines of the block there is a permutation of N For example, if N is the permutation could be Your program will take this permutation as input and determine whether you can marshal the coaches from the right track an incoming order to the left track with an outgoing order using the station, which can be treated as a stack.
The last line of the block contains just
If a block starts with a zero, the program will terminate
output
The output file contains the lines corresponding to the lines with permutations in the input file. A line of the output file contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input file. Otherwise, it contains No In addition, there is one empty line after the lines corresponding to one block of the input file. There is no line in the output file corresponding to the last null' block of the input file.
Sample Input:
start of the first block
end of the first block
start of the second block
end of the second block
end of input
Sample Output:
Yes
No
Yes
input file: Aintxt
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
New Trends In Databases And Information Systems ADBIS 2015 Short Papers And Workshops BigDap DCSA GID MEBIS OAIS SW4CH WISARD Poitiers In Computer And Information Science 539
Authors: Tadeusz Morzy ,Patrick Valduriez ,Ladjel Bellatreche
1st Edition
3319232002, 978-3319232003
