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

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 1 неделя, 4 дн. назад.

  • Автор
    Сообщения
  • #5919
    @admin

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

    В доме Вилли установили скоростной лифт новой экспериментальной модели. В этом лифте кнопки с номерами этажей заменены двумя другими кнопками. При нажатии на первую кнопку лифт поднимается на один этаж вверх, а при нажатии на вторую – опускается на один этаж вниз.

    Младшему брату Вилли Дилли очень нравится кататься на новом лифте. Он катается на нём до тех пор, пока не побывает на каждом из этажей хотя бы по одному разу. После этого Дилли довольный возвращается домой.

    Зная порядок, в котором Дилли нажимал на кнопки лифта, попробуйте определить общее количество этажей в доме Вилли и Дилли.

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

    Первая строка входного файла INPUT.TXT содержит последовательность нажатий на кнопки лифта. Символ «1» означает, что была нажата первая кнопка, а символ «2» – что была нажата вторая кнопка. Символы «1» и «2» не разделены пробелами. Количество нажатий от 1 до 100. Гарантируется, что лифт никогда не опускался ниже первого и не поднимался выше последнего этажа.

    Выходные данные
    В выходной файл OUTPUT.TXT следует вывести одно число – количество этажей в доме Вилли и Дилли.

    Примеры

    INPUT.TXT OUTPUT.TXT
    1 11 3
    2 21212 2
    3 1221221221221 6

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

    Сначала разберем «неудачное» решение задачи, а затем — посмотрим как можно было сделать лучше. В обоих случаях программа будет иметь следующую логику работы:

    1. Начнем с некоторого начального этажа — значение не важно;
    2. При смещении вверх — увеличиваем текущий этаж, вниз — уменьшаем;
    3. Отдельно сохраняем максимальные значения этажей
    4. В конце работы считаем разницу максимального и минимального этажа — это и будет искомый результат.

    В первом варианте решения студент попытался выделить сущности — этаж (как это «прнято» в ООП):

    #include <fstream>
    #include <string>
    using namespace std;
     
    struct Floor {
      int minFloor;
      int maxFloor;
    
      Floor() {
        minFloor = maxFloor = 0;
      }
    };
    
    int main() {
      ifstream input("INPUT.TXT");
      ofstream output("OUTPUT.TXT");
    
      //максимальное количество элементов
      const int maxSize = 100;
      string pressures;
    
      // ввод данных
      input >> pressures;
      int n = pressures.length();
      
      Floor floor;
    
      int currentFloor = 0;
      for (int j = 0; j < n; j++) {
        if (pressures[j] == '1') {
          //поднимаемся вверх
          currentFloor++;
          if (currentFloor > floor.maxFloor) {
            floor.maxFloor = currentFloor;
          }
        }
        else {
          //опускаемся вниз
          currentFloor--;
          if (currentFloor < floor.minFloor) {
            floor.minFloor = currentFloor;
          }
        }
      }
      
      //результат - это разница между мин. и макс. этажом плюс 1
      output << floor.maxFloor - floor.minFloor + 1;
    }

    Код от этого не стал лучше. Не улучшится он и при преобразовании Входной Строки в
    массив «команд». Дело в том, что классы должны описывать абстракции, которые должны помогать в повторном использовании кода, а специфика олимпиадного программирования в том, что разработанные вами абстракции (даже будь они очень хорошими, а не как тут) — будут использованы лишь единожды, при решении этой конкретной задачи. Исключение могут составлять классы обработки структур типа графов или, например, реализация длинной арифметики.

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

    #include <fstream>
    #include <string>
    using namespace std;
     
    int main() {
      ifstream in("INPUT.txt");
      ofstream out("OUTPUT.txt");
    
      string str;
      in >> str;
    
      int max_floor = 0, min_floor = 0, current_floor = 0;
    
      in >> str;
    
      for (int i = 0; i < str.length(); i++) {
        if (str[i] == '1')
          current_floor++;
        else
          current_floor--;
    
        if (max_floor < current_floor)
            max_floor = current_floor;
        if (min_floor > current_floor)
            min_floor = current_floor;
      }
    
      out << abs(min_floor) + abs(max_floor) + 1;
    }

    Визуализация:

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