Разбор олимпиадной задачи — A06. Линии Жизни

Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6239
      @admin
      StudLance.ru

      Условие задачи взято с codeforces (ограничение по времени на тест — 1 секунда,
      ограничение по памяти на тест — 256 мегабайт, ввод: стандартный ввод,
      вывод: стандартный вывод):

      Многие люди уверены, что жизнь состоит из неких чередующихся черных и белых «полос». Разумеется, если каждый день жизни считать либо «черным», либо «белым», а дни одного цвета объединять в полосы, то эти полосы в любом случае будут чередоваться.

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

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

      В единственной строке входного файла содержится последовательность нулей и единиц — описание жизни. «Черный» день задается единицей, «белый» день — нулем. Количество дней в описании не менее 1 и не более 100. Обратите внимание, что количество дней напрямую не задается.

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

      Вывести два числа — количество черных и количество белых полос.

      Примечание
      В первом примере сначала идет черная полоса из одного дня, потом белая полоса из одного дня, потом черная полоса из двух дней.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 1 0 1 1 2 1
      2 0 0 0 0 1

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

      В задаче требуется посчитать количество линий, при этом линия — последовательность из нулей или единиц. Решить ее можно по-разному,

      Во-первых, можно заметить, что для существования всех линий кроме первой, в последовательности обязательно появляется место где соседние символы различны. Значит мы можем найти все такие «места» в последовательности и добавить соответствующие полосы. При этом, нас будет интересовать именно пара символов — из текущей полосы и предыдущей (как показано на рисунке). Первую полосу придется обработать отдельно — ее однозначно задает первый символ:

      #include <string>
      #include <iostream>
      #include <algorithm>
      using namespace std;
      
      void add_line(char c, size_t& black_lines, size_t& white_lines) {
        if (c == '1')
          ++white_lines;
        else if (c == '0')
          ++black_lines;
        else
          throw "bad symbol";
      }
      
      int main() {
        size_t black_lines = 0, white_lines = 0;
        string life;
      
        getline(cin, life);
        life.erase(remove(life.begin(), life.end(), ' '), life.end());
      
        add_line(life[0], black_lines, white_lines);
      
        for (size_t i = 1; i < life.size(); ++i) {
          if (life[i] != life[i-1]) {
            add_line(life[i], black_lines, white_lines);
          }
        }
      
        cout << white_lines << ' ' << black_lines;
      }

      В этом решении из входные данные преобразуются в строку, из которой предварительно убираются все пробелы (remove — удаляет их, а erase изменяет размер строки, см. erase-remove idiom).

      Возможно и другое решение. На самом деле, зачем на считать изменения в строке, когда нам нужны лишь полосы. Если полоса состояла бы всегда из одного символа — то задача была бы совсем легкой. Значит, проблема в том, что в полосе может быть много одинаковых символов. Удалим из строки последовательно идущие одинаковые символы — звучит сложно, но в стандартной библиотеке для этого есть готовая функция — unique:

      Алгоритмы std::unique удаляет все последовательно повторяющиеся элементы из диапазона [first, last) и возвращает итератор на элемент, следующий за последним элементом нового диапазона. То есть он работает также как std::remove, для нормальной работы с ним применяется таже идиома.

      #include <string>
      #include <iostream>
      #include <algorithm>
      using namespace std;
      
      int main() {
        string life;
      
        getline(cin, life);
        life.erase(remove(life.begin(), life.end(), ' '), life.end());
        life.erase(unique(life.begin(), life.end()), life.end());
      
        cout << count(life.begin(), life.end(), '1') << ' '
             << count(life.begin(), life.end(), '0');
      }

      В этом решении после удаления дубликатов, к строке применяется стандартный алгоритм count, который и считает полосы.

      StudLance.ru

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