1776. Rails
There is a famous railway
station in PopPush City. Country there is incredibly hilly. The station was
built in the last century. Unfortunately, funds were extremely limited that
time. It was possible to establish only a surface track. Moreover, it turned
out that the station could be only a dead-end one (see picture) and due to lack
of available space it could have only one track.
The local tradition is that
every train arriving from the direction A continues in the
direction B with coaches reorganized in some way. Assume that the
train arriving from the direction A has n ≤ 1000 coaches numbered in increasing order 1, 2,
..., n. The chief for train
reorganizations must know whether it is possible to marshal coaches continuing
in the direction B so that their order will be a1, a2, ..., an. Help him and 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 themselves until they are on the track in the direction B. 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 in the direction A and also once it has left the station in
the direction B it cannot return back to the station.
Input.
Consists of blocks of lines. Each block except the last describes one train and
possibly more requirements for its reorganization. In the first line of the
block there is an integer n described
above. In each of the next lines of the block there is a permutation of 1, 2,
..., n. The last line of the block
contains just 0.
The last block consists of
just one line containing 0.
Output. For
each input line containing a permutation of numbers, output Yes if the
indicated permutation of cars can be performed, and No otherwise. After
outputting answers to all permutations of each test, output an empty string.
Nothing should be output for the last null test.
|
Sample input |
Sample output |
|
5 1 2 3 4 5 5 4 1 2 3 0 6 6 5 4 3 2 1 0 0 |
Yes No Yes |
SOLUTION
data structures - stack
Algorithm analysis
Store the cars
that will enter the dead-end station in the stack s. On side A, the cars are in the sequence 1, 2, ..., n. If the first car on side B should be
car k, then this can
be achieved by driving into a dead end all carriages with numbers 1, 2, ..., k, and then moving the car with number
k to side B.
Let after that
the car with number l should be the
second on side B. If l < k, then it can be moved in the direction B only if it is currently at the top of
the stack s (otherwise, the required
rearrangement of cars is not possible). If l > k, then we move from side A all the cars up to the l-th iton the stack, and then we move the car l to the
side B. Continue
to simulate the moving of cars
in this way until all cars are transported from side A to side B.
Algorithm realization
Declare a stack s, thet will contain the cars at the station.
stack<int> s;
Process
input tests sequentially.
while(scanf("%d",&n),n)
{
while(scanf("%d",&x),x)
{
cur = ok = 1;
Before processing the data of the
next test, clear the stack.
while(!s.empty())
s.pop();
Process the input sequence.
for(i = 1;
i < n; i++)
{
Move the car with number x to the side B. If the car with the number x is on the side A, push all cars up to x inclusive to the stack.
for(;cur
<= x; cur++) s.push(cur);
If the car at the top of the stack
has number that does not equal to x, then required sorting is impossible (in this case, set ok = 0).
if
(s.top() != x) ok = 0;
s.pop();
scanf("%d",&x);
}
Depending on the value of the variable ok, print the answer.
printf(ok ? "Yes\n"
: "No\n");
}
printf("\n");
}
Java realization
Using
the Scanner class gives Time Limit.
import java.util.*;
public class Main
{
public static void
main(String[] args)
{
Scanner con = new Scanner(System.in);
int n;
while((n = con.nextInt()) != 0)
{
int x, cur, ok;
while((x = con.nextInt()) != 0)
{
cur = ok = 1;
Stack<Integer> s = new Stack<Integer>();
for(int i = 1; i < n; i++)
{
for(; cur <= x; cur++) s.push(cur);
if (s.peek() != x) ok = 0;
s.pop();
x = con.nextInt();
}
String Answer = (ok == 1) ? "Yes" : "No";
System.out.println(Answer);
}
System.out.println("");
}
con.close();
}
}
Java realization – FastScanner
import java.util.*;
import java.io.*;
public class Main
{
public static void main(String[] args)
{
FastScanner con =
new FastScanner(new
InputStreamReader(System.in));
int n;
while((n = con.nextInt()) !=
0)
{
int x, cur, ok;
while((x = con.nextInt()) !=
0)
{
cur = ok = 1;
Stack<Integer>
s = new
Stack<Integer>();
for(int i = 1; i < n; i++)
{
for(; cur <= x; cur++) s.push(cur);
if (s.peek() != x) ok = 0;
s.pop();
x = con.nextInt();
}
String Answer = (ok == 1) ? "Yes" : "No";
System.out.println(Answer);
}
System.out.println("");
}
}
}
class FastScanner
{
private BufferedReader br;
private StringTokenizer
st;
public
FastScanner(InputStreamReader reader)
{
br = new BufferedReader(reader);
}
public String next()
{
while (st == null || !st.hasMoreTokens())
{
try
{
st = new
StringTokenizer(br.readLine());
} catch (Exception e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt()
{
return Integer.parseInt(next());
}
public double nextDouble()
{
return Double.parseDouble(next());
}
public void close() throws Exception
{
br.close();
}
}
Java realization – buffer reading
import java.util.*;
import java.io.*;
import java.util.Stack;
public class Main
{
public static void main(String[]
args)
throws Exception
{
BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
String Line;
while(!(Line =
in.readLine()).equals("0"))
{
int n = Integer.parseInt(Line);
int cur, ok;
String Line1;
while(!(Line1 =
in.readLine()).equals("0"))
{
StringTokenizer
st = new
StringTokenizer(Line1);
int x = Integer.parseInt(st.nextToken());
cur = ok = 1;
Stack<Integer> s = new Stack<Integer>();
for(int i = 1; i <
n; i++)
{
for(; cur <= x;
cur++) s.push(cur);
if (s.peek() != x)
ok = 0;
s.pop();
x = Integer.parseInt(st.nextToken());
}
String Answer =
(ok == 1) ? "Yes" : "No";
System.out.println(Answer);
}
System.out.println("");
}
}
}
Java realization – own class Stack
import java.util.*;
import java.io.*;
public class Main
{
public static class ArrayStack implements Stack
{
private int top;
private int[] storage;
ArrayStack(int capacity)
{
if (capacity <=
0)
throw new
IllegalArgumentException
("Stack's
capacity must be positive");
storage = new int[capacity];
top = -1;
}
public void push(int value)
{
if (top == storage.length)
throw new
StackException("Stack's
underlying storage is overflow");
top++;
storage[top] = value;
}
public int peek()
{
if (top == -1)
throw new StackException("Stack is
empty");
return storage[top];
}
public void pop()
{
if (top == -1)
throw new StackException("Stack is
empty");
top--;
}
public boolean isEmpty()
{
return (top == -1);
}
public class StackException extends
RuntimeException
{
public
StackException(String message)
{
super(message);
}
}
}
public interface Stack
{
void push(int value);
int peek();
void pop();
boolean isEmpty();
}
public static void main(String[] args)
throws Exception
{
BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
String Line;
while(!(Line =
in.readLine()).equals("0"))
{
int n = Integer.parseInt(Line);
int cur, ok;
String Line1;
while(!(Line1 =
in.readLine()).equals("0"))
{
StringTokenizer
st = new
StringTokenizer(Line1);
int x = Integer.parseInt(st.nextToken());
cur = ok = 1;
ArrayStack s = new
ArrayStack(2000);
for(int i = 1; i <
n; i++)
{
for(; cur <= x;
cur++) s.push(cur);
if (s.peek() != x)
ok = 0;
s.pop();
x = Integer.parseInt(st.nextToken());
}
String Answer =
(ok == 1) ? "Yes" : "No";
System.out.println(Answer);
}
System.out.println("");
}
}
}