Разбор олимпиадной задачи — Метро

  • В этой теме 0 ответов, 1 участник, последнее обновление 4 месяца, 4 недели назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6204
      @admin

      Условие задачи взято с сайта acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 16%):

      Витя работает недалеко от одной из станций кольцевой линии метро, а живет рядом с другой станцией той же линии. Требуется выяснить, мимо какого наименьшего количества промежуточных станций необходимо проехать Вите по кольцу, чтобы добраться с работы домой.

      Входные данные

      Во входном файле INPUT.TXT заданы три числа: сначала N – общее количество станций кольцевой линии, а затем i и j – номера станции, на которой Витя садится, и станции, на которой он должен выйти. Станции пронумерованы подряд натуральными числами 1, 2, 3, …, N (1-я станция – соседняя с N-й), N не превосходит 100. Числа i и j не совпадают. Все числа разделены пробелом.

      Выходные данные

      В выходной файл OUTPUT.TXT требуется вывести минимальное количество промежуточных станций (не считая станции посадки и высадки), которые необходимо проехать Вите.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 100 5 6 0
      2 10 1 9 1

      Разбор решения задачи

      Чтобы понять задачу лучше всего нарисовать метро, например так:

      Цветом выделены начальная — from (зеленым) и конечная — to (красным) станции. По кольцу мы можем двигаться в двух направлениях, нужно найти оптимальное и определить число промежуточных станций. Критерий оптимальности — количество станций.

      Так как станции пронумерованы последовательно, то количество промежуточных станций, при движении в прямом направлении (по ходу увеличения номера станции) можно определить как to - from - 1, однако:

      • это сработает если from < to — например между 3-ей и 6-ой станциями есть 2 промежуточных (с номерами 4 и 5);
      • если to > from — то мы должны доехать до последней станции (n-from-1) промежуточная, и с нее проедем еще to станций. Например при движении со станции 6 до станции 3 в прямом направлении для нашего примера мы проедем 6 станций с номерами [7,8,9,10,1,2];

      По таким формулам мы можем получить два числа — для прямого и обратного направлений, выбрать из них наименьшее. Такое решение выльется в большое число условий. Однако, можно чуть упростить задачу — заметьте, что минимальное число станций при движении из A в B такое же как при движении из B в A, поэтому для упрощения расчетов можно переставить их если они стоят в «неудобном порядке»:

      #include <fstream>
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int n, from, to;
        int direct_stations, reverse_stations, min_stations;
      
        ifst >> n >> from >> to;
      
        if (from < to)
          swap(from, to);
      
        direct_stations = from - to;
        reverse_stations = n - direct_stations;
        min_stations = min(direct_stations, reverse_stations);
      
        ofst << min_stations - 1;
      }

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.