1776. Рельсы

 

В городе PopPush находится известная железнодорожная станция. Страна, в которой находится город, невероятно холмистая. Станция была построена в прошлом веке. К сожалению, в то время средства для постройки были крайне ограничены, поэтому удалось построить только одну железнодорожную колею. Более того, выяснилось, что станция может быть только тупиковой (см. рисунок), и из-за отсутствия свободного места может иметь только одну колею.

Местная традиция гласит, что каждый поезд, приходящий со стороны A, продолжает свое движение в направлении B, при этом его вагоны перестанавливаются в некотором порядке. Предположим, что каждый поезд, приходящий из направления A, имеет n ≤ 1000 вагонов, пронумерованных в возрастающем порядке 1, 2, ..., n. Ответственный за реорганизацию вагонов должен знать, возможно ли перевезти их в направлении B в порядке a1, a2, ..., an. Помогите ему написать программу, которая определит, возможна ли такая перестановка вагонов. Вагоны можно отсоединять от поезда до того как они попадут на станцию и можно их отдельно передвигать пока все они не буду находиться в направлении B. На станции в любой момент времени может находиться любое количество вагонов. Но если вагон зашел на станцию, он уже не может вернуться на колею в направлении A, а также если он уже выехал в направлении B, то уже не может вернуться на станцию.

 

Вход. Состоит из нескольких тестов. Каждый тест кроме последнего описывает один поезд и возможно несколько требований для его реорганизации. Первая строка теста содержит целое число n. Каждая из следующих строк теста содержит перестановку 1, 2, ..., n. Последняя строка блока содержит 0.

Последний тест состоит из единственной строки, содержащей 0.

 

Выход. Для каждой входной строки, содержащей перестановку чисел, следует вывести Yes, если можно совершить указанную перестановку вагонов, и No иначе. После вывода ответов на все перестановки каждого теста следует вывести пустую строку. Для последнего нулевого теста ничего выводить не следует.

 

Пример входа

Пример выхода

5

1 2 3 4 5

5 4 1 2 3

0

6

6 5 4 3 2 1

0

0

Yes

No

 

Yes

 

 

РЕШЕНИЕ

структуры данных - стек

 

Анализ алгоритма

Вагоны, которые будут заезжать на станцию-тупик, будем хранить в стеке s. На стороне А вагоны находятся в последовательности 1, 2, ..., n. Если первым на стороне B должен быть вагон k, то этого можно достичь загнав в тупик все вагоны с номерами 1, 2, ..., k, после чего перегнав вагон с номером k на сторону B.

Пусть после этого вторым на стороне B должен находиться вагон с номером l. Если l < k, то его можно перевезти в направлении B только если он на данный момент находится на вершине стека s (иначе требуемая перестановка вагонов неосуществима). Если l > k, то перегоняем со стороны А все вагоны вплоть до l-го в стек, после чего перевозим вагон l на сторону B. Продолжаем моделировать перевозку вагонов указанным образом, пока все вагоны не будут перевезены со стороны А в сторону B.

 

Реализация алгоритма

Объявим стек s, в котором будут содержаться находящиеся на станции вагоны.

 

stack<int> s;

 

Обрабатываем последовательно входные тесты.

 

while(scanf("%d",&n),n)

{

  while(scanf("%d",&x),x)

  {

    cur = ok = 1;

 

Перед обработкой данных очередного теста очистим стек.

 

    while(!s.empty()) s.pop();

 

Обрабатываем входную последовательность.

 

    for(i = 1; i < n; i++)

    {

 

Перегоняем вагон с номером x на сторону B. Если вагон с номером x находится на  стороне А, то все вагоны до x включительно заводим в стек.

 

      for(;cur <= x; cur++) s.push(cur);

 

Если вагон, находящийся на вершине стека, имеет номер, не равный x, то требуемая сортировка невозможна (в этом случае устанавливаем ok = 0).

 

      if (s.top() != x) ok = 0;

      s.pop();

      scanf("%d",&x);

    }

 

В зависимости от значения переменной ok выводим ответ.

 

    printf(ok ? "Yes\n" : "No\n");

  }

  printf("\n");

}

 

Java реализация

Использование класса Scanner дает 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 реализация – 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 реализация – буферное чтение

 

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 реализация – собственный класс 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("");   

    }

  }

}