Разбор олимпиадной задачи — Кругляши

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

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

      Однажды в просторах рунета появился следующий ребус:

      157892 = 3
      203516 = 2
      409578 = 4
      236271 = ?

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

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

      Во входном файле INPUT.TXT записано целое число N (0 ≤ N ≤ 10^100).

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

      В выходной файл OUTPUT.TXT выведите одно число – количество кругляшей в числе N.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 157892 3
      2 203516 2
      3 409578 4
      4 236271 1

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

      Это прекрасная задача для знакомства со стандартной библиотекой. Попробуйте решить ее как можно более «стандартными» методами (меньше кода писать самому).

      Итак, в некоторых числах есть Кругляши — в 0, 6 и 9 их 1, а в 8 их 2. Нужно посчитать сколько их во входном числе. Число очень большое и работать с ним можно только как со строкой. Простейшее решение на С++ может выглядеть так:

      #include <fstream>
      #include <string>
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        string number;
        ifst >> number;
      
        int counter = 0;
        for (size_t i = 0; i < number.size(); ++i) {
          if (number[i] == '0' || number[i] == '6' || number[i] == '9')
            counter += 1;
          else if (number[i] == '8')
            counter += 2;
        }
      
        ofst << counter;
      }

      Как его улучшить? — можно применить цикл for по коллекции:

      for (auto c : number) {
        if (c == '8') // ...
      }

      А можно вообще не писать самому цикл — ведь он вычисляет сумму, а для этого в стандартной библиотеке (модуле numeric) есть функция accumulate. Эта функция может вычислять сумму или произведение в зависимости от того, какая функция-оператор передана в виде дополнительного параметра. В стандартной библиотеке определен ряд таких функций std::plus, std::minus, std::multiplies, std::negate, ..., но нам то нужно что-то нестандартное, чтобы для символа ‘1’ добавляла 0, для символа ‘8’ — 2, … . Надо написать свой оператор — он принимает два аргумента: старое значение и обрабатываемый элемент. Посмотрите как можно описать свою функцию для accumulate и решить задачу:

      #include <fstream>
      #include <string>
      #include <numeric>
      using namespace std;
      
      int circles_count(int init, int c) {
        if (c == '0' || c == '6' || c == '9')
          return init+1;
        if (c == '8')
          return init+2;
        return init;
      }
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        string number;
        ifst >> number;
      
        ofst << accumulate(number.begin(), number.end(), 0, circles_count);
      }

      Выглядит гораздо лучше, но что еще можно улучшить? — не считывать строку, а обрабатывать символы прямо из файла. Хорошо, что accumulate умеет работать с итераторами файловых потоков:

      #include <fstream>
      #include <numeric>
      #include <iterator>
      using namespace std;
      
      int circles_count(int init, int c) {
        if (c == '0' || c == '6' || c == '9')
          return init+1;
        if (c == '8')
          return init+2;
        return init;
      }
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        ofst << accumulate(istream_iterator<char>(ifst), istream_iterator<char>(), 0, circles_count);
      }

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