2.9. Разбор задач к главе «Базовые конструкции C++»

Напишите программу, печатающую на экране первые строчки со страницы Бьярне Страуструпа про C++:

C++ is a general-purpose programming language with a bias towards systems programming that
  - is a better C
  - supports data abstraction
  - supports object-oriented programming
  - supports generic programming.

Не потеряйте парные пробелы в начале строк и переносы в конце строк.

Задача очень похожа на программу Hello world. Отличие в том, что здесь надо напечатать несколько строк текста. Сам символ перевода строки не может содержаться в обычных строковых литералах, поэтому в программе его придётся заменить на \n. Можно просто вывести каждую строчку отдельно:

#include <iostream>

int main() {
    std::cout << "C++ is a general-purpose programming language with a bias towards systems programming that\n";
    std::cout << "  - is a better C\n";
    std::cout << "  - supports data abstraction\n";
    std::cout << "  - supports object-oriented programming\n";
    std::cout << "  - supports generic programming.\n";
}

Однако писать каждый раз std::cout утомительно. В конструкции std::cout поддерживается вывод нескольких величин сразу. Можно оставить только самый первый std::cout, а остальные строки вывести через <<:

#include <iostream>

int main() {
    std::cout << "C++ is a general-purpose programming language with a bias towards systems programming that\n"
              << "  - is a better C\n"
              << "  - supports data abstraction\n"
              << "  - supports object-oriented programming\n"
              << "  - supports generic programming.\n";
}

Здесь мы нарочно для лучшей читаемости отформатировали программу так, чтобы символы << стояли друг под другом.

Рассмотрим ещё два способа решить задачу. Строковые константы, расположенные просто друг за другом, автоматически конкатенируются при компиляции программы. Так "Hello," " world!" даст "Hello, world!. Поэтому можно написать так:

#include <iostream>

int main() {
    std::cout << "C++ is a general-purpose programming language with a bias towards systems programming that\n"
                 "  - is a better C\n"
                 "  - supports data abstraction\n"
                 "  - supports object-oriented programming\n"
                 "  - supports generic programming.\n";
}

Можно ли избавиться от необходимости писать \n в конце каждой строки? Да, для этого можно воспользоваться raw-литералами. Они могут содержать внутри без экранирования любые символы, в том числе перевод строки, лишь бы они были отличны от выбранных ограничителей. Такие литералы предваряются символом R, а в начале и в конце должна стоять произвольно выбранная одинаковая последовательность символов и круглые скобки. Например, raw(...)raw, или ~~~(...)~~~:

#include <iostream>

int main() {
    std::cout <<
R"~~~(C++ is a general-purpose programming language with a bias towards systems programming that
  - is a better C
  - supports data abstraction
  - supports object-oriented programming
  - supports generic programming.
)~~~";
}

Подробнее про строковые литералы читайте здесь.

Вам даны два целых числа. Напечатайте их сумму.

Формат ввода

Вводятся два числа, по модулю не превосходящие миллиарда.

Формат вывода

Напечатайте сумму этих чисел. В конце поставьте перевод строки.

Пример

#include <iostream>

int main() {
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << "\n";
}

Проверять корректность условия (то, что числа по модулю не превосходят миллиарда) в программе не нужно.

Из условия следует, что сумма этих чисел по модулю не будет превосходить двух миллиардов. Забегая немного вперёд, скажем, что это гарантирует, что сумма поместится в тип int. Такие условия позволяют выбрать правильный тип данных для решения задачи.

Напишите программу для перевода сантиметров в дюймы. В одном дюйме сантиметра.

Формат ввода

На вход поступает длина в сантиметрах. Значение может быть дробным. Используйте тип double для его хранения.

Формат вывода

Напечатайте эту длину в дюймах. Округление не требуется. Достаточно использовать стандартную точность вывода до 6 знаков после запятой, которая установлена по умолчанию.

Пример

Если в одном дюйме сантиметра, то в одном сантиметре дюйма:

#include <iostream>

int main() {
    double centimeters;
    std::cin >> centimeters;

    double inches = centimeters / 2.54;

    std::cout << inches << "\n";
}

Перед вами программа, которая считает сумму первых натуральных чисел по формуле суммы арифметической прогрессии:

#include <iostream>

int main() {
    int n;
    std::cin >> n;
    std::cout << n * (n + 1) / 2 << "\n";
}

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

Никакой ошибки в формуле нет. Всё дело в используемом типе данных. При происходит переполнение типа int32_t, а при n = 3037000500 происходит переполнение типа int64_t. При выборе беззнакового типа uint64_t переполнения на не случится. Поэтому просто заменим тип данных на uint64_t.

#include <cstdint>
#include <iostream>

int main() {
    std::uint64_t n = 0;
    std::cin >> n;
    std::cout << n * (n + 1) / 2 << "\n";
}

Можно было бы сначала выяснить, является ли n чётным, чтобы сначала произвести деление, а потом умножить:

#include <cstdint>
#include <iostream>

int main() {
    std::uint64_t number = 0;
    std::cin >> number;

    if (number % 2 == 0) {
        std::cout << (number / 2) * (number + 1);
    } else {
        std::cout << ((number + 1) / 2) * number;
    }
    std::cout << "\n";
}

Тогда лимиты выросли бы ещё больше. Но в решении этого не потребовалось.

Шахматный ферзь ходит на любое количество клеток по диагонали, горизонтали или вертикали. Даны две различные клетки на шахматной доске без фигур. Определите, может ли ферзь попасть с первой клетки на вторую одним ходом.

Формат ввода

Программа получает на вход четыре целых числа от 1 до 8. Первая пара чисел задаёт номер столбца и номер строки для первой клетки. Вторая пара чисел аналогично задаёт вторую клетку.

Формат вывода

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

Пример 1

Пример 2

Пример 3

Ферзь может ходить по вертикали, горизонтали и диагонали. Для того чтобы проверить, является ли ход вертикальным или горизонтальным, достаточно сравнить координаты или . Для проверки является ли ход диагональным достаточно сравнить модуль разности координат . Если ни одно из условий не выполняется — ход не может быть совершён ферзём. Для нахождения модуля удобно использовать стандартную функцию std::abs.

#include <cmath>
#include <iostream>

int main() {
    int x1, y1, x2, y2;
    std::cin >> x1 >> y1;
    std::cin >> x2 >> y2;

    if (x1 == x2 || y1 == y2 || std::abs(x1 - x2) == std::abs(y1 - y2)) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

Напишите программу, которая проверяет является ли треугольник прямоугольным.

Формат ввода

На стандартный поток ввода подаётся три целых положительных числа — стороны треугольника. Числа не превосходят 30000.

Формат вывода

Если полученный треугольник является прямоугольным, напечатайте YES. Если треугольник не является прямоугольным, напечатайте NO. Если с заданными сторонами невозможно построить треугольник, напечатайте UNDEFINED.

Пример 1

Пример 2

Во-первых, нам необходимо проверить существует ли такой треугольник. Для этого достаточно воспользоваться неравенством треугольника: . Если хотя бы одно из этих условий не выполняется, программа должна выводить UNDEFINED.

Далее необходимо проверить является ли треугольник прямоугольным. Есть несколько способов это сделать. Самый простой — воспользоваться теоремой Пифагора. Если одно из равенств выполняется, программа должна вывести YES. В противном случае надо вывести NO.

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

#include <iostream>

int main() {
    int a, b, c;
    std::cin >> a >> b >> c;

    if (a + b <= c || a + c <= b || b + c <= a) {
        std::cout << "UNDEFINED\n";
    } else if (a * a + b * b == c * c || a * a + c * c == b * b || b * b + c * c == a * a) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

Определите, является ли год високосным по григорианскому календарю.

Напоминание:

• год, номер которого кратен 400, — високосный;
• остальные годы, номер которых кратен 100, — невисокосные (например, годы 1700, 1800, 1900, 2100, 2200, 2300);
• остальные годы, номер которых кратен 4, — високосные.
• все остальные годы — невисокосные.

Формат ввода

Вводится целое положительное четырёхзначное число — номер года.

Формат вывода

Программа выводит YES если год високосный и NO в противном случае.

Пример 1

Пример 2

Пример 3

Грамотно перепишем определения из условия через if/else и проверку остатка от деления:

#include <iostream>

int main() {
    int year;
    std::cin >> year;

    if (year % 400 == 0) {
        std::cout << "YES\n";
    } else if (year % 100 == 0) {
        std::cout << "NO\n";
    } else if (year % 4 == 0) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

Заметим, что в получившимся коде дублируются ветви условий. Попробуем его упростить. Для этого достаточно заметить, что високосным является любой год, который делится на 400 или делится на 4, но не делится на 100. После этого упрощения получим следующий код:

#include <iostream>

int main() {
    int year;
    std::cin >> year;

    if ((year % 400 == 0 || year % 100 != 0) && year % 4 == 0) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

Напишите программу, выводящую количество дней в месяце по заданному номеру месяца и году.

Формат ввода

На вход программе подается два целых положительных числа: номер месяца (от 1 до 12) и четырёхзначный год.

Формат вывода

Необходимо вывести одно число — количество дней в заданном месяце.

Пример 1

Пример 2

Пример 3

Примечание

Рекомендуется сначала решить задачу «Високосный год» и использовать её решение для вывода количества дней в феврале.

Эту задачу можно решать либо через if/else, либо через switch/case. Мы воспользуемся вторым вариантом, потому что в таком случае удобно описывать ветви, у которых много разных возможных условий.

Перечислим все возможные месяцы, для которых ответ будет 31: это январь (1), март (3), май (5), июль (7), август (8), октябрь (10), декабрь (12). Для февраля (2) ответ будет зависеть от года. Воспользуемся кодом из задачи «Високосный год», заменив вывод с YES/NO на 29/28. Для остальных месяцев воспользуемся инструкцией default и выведем 30.

#include <iostream>

int main() {
    int month, year;
    std::cin >> month >> year;

    switch (month) {
        case 1:
        case 3:
        case 5:
        case 7:
        case 8:
        case 10:
        case 12:
            std::cout << "31\n";
            break;
        case 2:
            if ((year % 400 == 0 || year % 100 != 0) && year % 4 == 0) {
                std::cout << "29\n";
            } else {
                std::cout << "28\n";
            }
            break;
        default:
            std::cout << "30\n";
    }
}

Напечатайте месяц из календаря по заданному начальному дню и количеству дней. Ваш ответ должен выглядеть примерно так:

                   1
 2  3  4  5  6  7  8
 9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31

Формат ввода

Вводится два числа: n — номер дня недели первого числа месяца (целое число от 1 до 7) и k — количество дней в этом месяце (целое число от 1 до 99). . Обратите внимание, что число дней в месяце не обязательно должно быть таким же, как в привычном календаре.

Формат вывода

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

Для начала выведем отступ перед первым днём. Номер одного дня записывается в два символа, все дни разделены пробелом. Соответственно, необходимо вывести n - 1 раз строку из трёх пробелов.

Далее введём счётчик dayOfWeek и выставим ему начальное значение, равное n. Будем использовать его для отсчета текущего столбца. Воспользуемся циклом for от 1 до k включительно. Будем выводить текущее число и прибавлять к счётчику 1. Каждый раз, когда счётчик достигает семи, сбрасываем его в единицу и печатаем символ переноса строки \n. Также нужно не забыть, что числа от 1 до 9 занимают всего один символ в нашем календаре. Чтобы это исправить добавим дополнительный if, который ставит пробел перед числом.

В самом конце проверим, в какой день недели закончился месяц. Если он закончился не в воскресенье, то необходимо допечатать перевод строки.

#include <iostream>

int main() {
    int n, k;
    std::cin >> n >> k;

    int dayOfWeek = n;

    for (int i = 1; i < n; ++i) {
        std::cout << "   ";
    }

    for (int day = 1; day <= k; ++day) {
        if (day < 10) {
            std::cout << " ";
        }

        std::cout << day;

        if (dayOfWeek == 7) {
            std::cout << "\n";
            dayOfWeek = 1;
        } else {
            std::cout << " ";
            dayOfWeek += 1;
        }
    }

    if (dayOfWeek != 1) {
        std::cout << "\n";
    }
}

Вычислите сумму цифр неотрицательного целого числа.

Формат ввода

На вход подаётся одно неотрицательное целое число, не превосходящее .

Формат вывода

Выведите сумму цифр этого числа.

Пример

По условию задачи число помещается в тип int. Поэтому можно написать цикл, который будет прибавлять к ответу последнюю цифру этого числа (остаток при делении на 10) и делить число на 10 без учёта остатка.

#include <iostream>

int main() {
    int x;
    std::cin >> x;

    int s = 0;
    while (x != 0) {
        s += x % 10;
        x /= 10;
    }

    std::cout << s << "\n";
}

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

Чтобы превратить очередной символ в цифру, воспользуемся тем, что символы цифр в таблице ASCII идут подряд. Поэтому разность кодов символов c - '0' будет как раз давать числовое представление очередной цифры.

#include <iostream>
#include <string>

int main() {
    std::string digits;
    std::cin >> digits;

    int s = 0;
    for (char digit : digits) {
        s += digit - '0';
    }

    std::cout << s << "\n";
}

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

Указание: используйте тип double для работы с числами с плавающей точкой. Используйте стандартную точность вывода.

Формат ввода

Вводится целое положительное число , помещающееся в тип int.

Формат вывода

Программа выводит ответ на задачу.

Пример 1

Пример 2

Пример 3

Объявим две переменные sign и result. В result будем складывать итоговое значение, а в sign будем хранить 1 или -1. Знак переменной sign будет каждый раз меняться.

Важно привести один из аргументов дроби sign / i к типу double, чтобы не получилось целочисленного деления.Проще всего это сделать, выбрав для переменной sign тип double.

#include <iostream>

int main() {
    int n;
    std::cin >> n;

    double sign = 1;
    double result = 0.0;

    for (int i = 1; i <= n; ++i) {
        result += sign / i;
        sign = -sign;
    }
    std::cout << result << "\n";
}

Пароль от некоторого сервиса должен удовлетворять таким ограничениям:

• состоять из символов таблицы ASCII с кодами от 33 до 126;
• быть не короче 8 символов и не длиннее 14;
• из 4 классов символов — большие буквы, маленькие буквы, цифры, прочие символы — в пароле должны присутствовать не менее трёх любых.

Напишите программу, которая проверит, что введённый пароль подходит под эти ограничения.

Формат ввода

На входе дана одна строка с паролем.

Формат вывода

Выведите YES, если пароль удовлетворяет требованиям, и NO в противном случае.

Пример

Примечания

Вы можете воспользоваться функциями из заголовочного файла cctype или реализовать самостоятельно их аналоги.

Решение можно целиком записать внутри функции main, но нам будет удобнее оформить проверку пароля в виде отдельной функции IsGood, которая возвращает логическое значение. Из такой функции всегда можно удобно выйти с помощью return, если ответ уже известен.

#include <iostream>
#include <string>

bool IsGood(const std::string& password) {
    if (password.size() < 8 || password.size() > 14) {
        return false;
    }
    int upper = 0;
    int lower = 0;
    int digit = 0;
    int other = 0;

    for (char c : password) {
        if (c < 33 || c > 126) {
            return false;
        }
        if ('A' <= c && c <= 'Z') {
            upper = 1;
        } else if ('a' <= c && c <= 'z') {
            lower = 1;
        } else if ('0' <= c && c <= '9') {
            digit = 1;
        } else {
            other = 1;
        }
    }

    return upper + lower + digit + other >= 3;
}

int main() {
    std::string password;
    std::getline(std::cin, password);
    if (IsGood(password)) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

Здесь мы используем явные сравнения с другими символами вида '0' <= c && c <= '9'. Можно было бы использовать функции std::isupper, std::islower и std::isdigit из заголовочного файла cctype.

Известный алгоритм Soundex определяет, похожи ли два английских слова по звучанию. На вход он принимает слово и заменяет его на некоторый четырёхсимвольный код. Если коды двух слов совпадают, то слова, как правило, звучат похоже.

Вам требуется реализовать этот алгоритм. Он работает так:

1. Первая буква слова сохраняется.
2. В остальной части слова буквы a, e, h, i, o, u, w и y удаляются;
3. Оставшиеся буквы заменяются на цифры от 1 до 6, причём похожим по звучанию буквам соответствуют одинаковые цифры:

• b, f, p, v: 1
• c, g, j, k, q, s, x, z: 2
• d, t: 3
• l: 4
• m, n: 5
• r: 6

4. Любая последовательность идущих подряд одинаковых цифр сокращается до одной такой цифры.
5. Итоговая строка обрезается до первых четырёх символов.
6. Если длина строки получилась меньше четырёх символов, в конце добавляются нули.

Примеры:

аmmonium → ammnm → a5555 → a5 → a500.

implementation → implmnttn → i51455335 → i514535 → i514.

Формат ввода

На вход подаётся одно непустое слово из строчных латинских букв. Длина слова не превосходит 20 символов.

Формат вывода

Напечатайте четырёхбуквенный код, соответствующий слову.

Пример 1

Пример 2

Хотя задачу можно решить и без функций, нам будет удобно оформить её решение в виде отдельной функции Soundex. Шаги 3 и 4 можно оформить в виде оператора switch.

Напишем также вспомогательную функцию Append, добавляющую символ к ответу в случае, если он не дублируется. В эту функцию удобно передать параметр res по ссылке, чтобы его можно было изменять.

#include <iostream>
#include <string>

void Append(std::string& res, char c) {
    if (res.back() != c) {
        res.push_back(c);
    }
}

std::string Soundex(const std::string& word) {
    std::string res;
    res.push_back(word[0]);
    for (size_t i = 1; i != word.size(); ++i) {
        char c = word[i];
        switch (c) {
            case 'b':
            case 'f':
            case 'p':
            case 'v':
                Append(res, '1');
                break;
            case 'c':
            case 'g':
            case 'j':
            case 'k':
            case 'q':
            case 's':
            case 'x':
            case 'z':
                Append(res, '2');
                break;
            case 'd':
            case 't':
                Append(res, '3');
                break;
            case 'l':
                Append(res, '4');
                break;
            case 'm':
            case 'n':
                Append(res, '5');
                break;
            case 'r':
                Append(res, '6');
                break;
        }
    }
    while (res.size() < 4) {
        res.push_back('0');
    }
    res.resize(4);
    return res;
}

int main() {
    std::string word;
    std::cin >> word;
    std::cout << Soundex(word) << "\n";
}

На мероприятие приглашены гостей. Им предлагают занять места с номерами от 1 до в зале. Гости занимают эти места в произвольном порядке. Известно, на каком месте сел очередной гость.

Выпишите для каждого очередного места номер гостя, который на него сел.

Формат ввода

Дано число , а затем различных чисел от 1 до . Число — это номер места, на которое сел -й гость.

Число не превосходит 20000.

Формат вывода

Выведите чисел от 1 до . Число должно обозначать номер гостя, который сел на -е место.

Пример 1

Пример 2

Примечания

Если говорить математическим языком, то вам дана перестановка и для неё требуется вычислить обратную перестановку.

Будем заполнять вектор seats, в котором для каждого номера места будет указан номер гостя. Не забудьте: элементы вектора индексируются с нуля, а номера мест и гостей в задаче начинаются с единицы.

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;

    std::vector<int> seats(n);
    for (int guest = 1; guest <= n; ++guest) {
        int seat;
        std::cin >> seat;
        seats[seat - 1] = guest;
    }

    for (int guest : seats) {
        std::cout << guest << " ";
    }
    std::cout << "\n";
}

Вам даны строки текстового файла. Отсортируйте набор этих строк по убыванию.

Формат ввода

Количество строк не превосходит 1000. Каждая строка состоит из символов ASCII с кодами от 32 до 126, длина строки не превосходит 100.

Формат вывода

Напечатайте строки в отсортированном по убыванию порядке. Для сравнения строк друг с другом достаточно использовать стандартные операторы сравнения, определённые для std::string.

Пример

Примечания

Компилятор не поддерживает std::ranges.

Строки необходимо прочитать и сложить в вектор, а затем отсортировать и вывести. По умолчанию они будут сортироваться по возрастанию. Есть несколько способов сделать сортировку и вывод в нужном порядке:

1. строки можно напечатать в обратном порядке;
2. можно передать в std::sort обратные итераторы;
3. можно передать в std::sort свою функцию сравнения;
4. можно передать в std::sort уже готовый компаратор std::greater<std::string>().

Воспользуемся, например, вторым способом:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> lines;

    std::string line;
    while (std::getline(std::cin, line)) {
        lines.push_back(line);
    }

    std::sort(lines.rbegin(), lines.rend());

    for (size_t i = 0; i != lines.size(); ++i) {
        std::cout << lines[i] << "\n";
    }
}

Типичная ошибка в решении этой задачи — считывать строки через std::cin >> line вместо std::getline. Такой код прочитает строку не целиком, а до ближайшего пробельного разделителя.

Дана строка из строчных латинских букв и пробелов. Проверьте, является ли она палиндромом без учета пробелов.

Формат ввода

На вход подается одна строка. В строке могут быть пробелы. Подряд может идти произвольное число пробелов. Длина строки не превосходит 100.

Формат вывода

Представьте, что из строки удалили все пробелы. Необходимо вывести YES, если полученная строка — палиндром, и NO в противном случае.

Пример 1

Пример 2

Примечание

Пустая строка считается палиндромом.

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

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::string s;
    std::getline(std::cin, s);

    int i = 0;
    int j = static_cast<int>(s.size()) - 1;
    bool isPalindrome = true;

     while (i < j) {
        if (s[i] == ' ') {
            ++i;
        } else if (s[j] == ' ') {
            --j;
        } else if (s[i] != s[j]) {
            isPalindrome = false;
            break;
        } else {
            ++i;
            --j;
        }
    }

    if (isPalindrome) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

Вот изящное решение этой задачи для тех, кто прочитал параграф про алгоритмы стандартной библиотеки:

#include <algorithm>
#include <iostream>
#include <string>

int main() {
    std::string s;
    std::getline(std::cin, s);

    std::erase(s, ' ');  // С++20

    // В С++17 пришлось бы написать
    // s.erase(std::remove(s.begin(), s.end(), ' '), s.end());

    if (std::equal(s.begin(), s.begin() + s.size() / 2, s.rbegin())) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

Вам необходимо построить поле для игры «Сапёр» по его конфигурации — высоте, ширине и координатам расставленных на нем мин.

Вкратце напомним правила построения поля для игры «Сапёр»:

• поле состоит из клеток с минами и пустых клеток;
• клетки с миной обозначаются символом *;
• пустые клетки содержат число от 0 до 8 — количество мин на соседних клетках.

Формат ввода

В первой строке содержатся три числа:

• число от 1 до 100 — количество строк на поле;
• число от 1 до 100 — количество столбцов на поле;
• число от 0 до — количество мин на поле.

В следующих строках содержатся пары чисел с координатами мин (номерами строки и столбца). Нумерация ведётся с единицы.

Формат вывода

Выведите построенное поле, разделяя строки поля символом \n, а столбцы — пробелом.

Пример

Заведём двумерный вектор и будем записывать в него мины и количество мин в соседних клетках. Мины будет удобно обозначать минус единицей.

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

Чтобы не выписывать восемь однотипных проверок на соседние клетки, удобно будет создать вектор «сдвигов» и перебирать эти сдвиги в цикле.

Можно также добавить к нашему игровому полю дополнительные клетки по краям, чтобы не делать проверки на корректность при обращении к соседней клетке. Поэтому размер поля в нашей программе на 2 больше указанного.

#include <iostream>
#include <vector>

struct Shift {
    int x = 0;
    int y = 0;
};

const std::vector<Shift> SHIFTS = {
    {-1, -1},
    {-1,  0},
    {-1,  1},
    { 0,  1},
    { 1,  1},
    { 1,  0},
    { 1, -1},
    { 0, -1},
};

int main() {
    size_t rows;
    size_t columns;
    size_t mines;
    std::cin >> rows >> columns >> mines;

    const int mineLabel = -1;

    std::vector<std::vector<int>> field(rows + 2, std::vector<int>(columns + 2));

    for (size_t index = 0; index != mines; ++index) {
        int row, column;
        std::cin >> row >> column;

        field[row][column] = mineLabel;

        for (auto shift : SHIFTS) {
            auto& cell = field[row + shift.x][column + shift.y];
            if (cell != mineLabel) {
                ++cell;
            }
        }
    }

    for (size_t row = 1; row <= rows; ++row) {
        for (size_t column = 1; column <= columns; ++column) {
            if (column > 1) {
                std::cout << " ";
            }
            if (field[row][column] == mineLabel) {
                std::cout << "*";
            } else {
                std::cout << field[row][column];
            }
        }
        std::cout << "\n";
    }
}

Обратите внимание на инициализацию ссылки cell. Мы специально объявили cell как ссылку, чтобы по этому краткому имени можно было изменить значение.

Вам требуется написать на C++ функцию со следующим заголовком:

std::pair<size_t, size_t> MatrixArgMax(const std::vector<std::vector<int>>& matrix);

Функция должна вернуть пару из индексов максимального элемента в матрице. Если максимальных элементов несколько, то нужно вернуть наименьшую такую пару.

Примечания

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

Подключите необходимые заголовочные файлы и напишите только код функции MatrixArgMax. Мы скомпилируем решение с нашей функцией main.

Сохраним в переменной argMax позицию начального элемента матрицы, а в переменной max — значение этого элемента. Обойдём все элементы матрицы с помощью вложенного цикла. Если обнаружим новый максиммум, то обновим эти переменные.

#include <utility>
#include <vector>

std::pair<size_t, size_t> MatrixArgMax(const std::vector<std::vector<int>>& matrix) {
    std::pair<size_t, size_t> argMax = {0, 0};
    int max = matrix[0][0];
    for (size_t i = 0; i != matrix.size(); ++i) {
        for (size_t j = 0; j != matrix[i].size(); ++j) {
            if (matrix[i][j] > max) {
                max = matrix[i][j];
                argMax = {i, j};
            }
        }
    }
    return argMax;
}

Напишите функцию для вычисления наибольшего общего префикса строк, переданных в векторе words:

std::string CommonPrefix(const std::vector<std::string>& words);

Например, для пустого вектора функция должна вернуть пустую строку, а для вектора из строк "apple", "apricot" и "application" — строку "ap".

Примечание

В решении не должно быть функции main: она будет в нашей тестирующей программе. Подключите необходимые библиотеки и напишите код функции CommonPrefix.

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

#include <string>
#include <vector>

std::string CommonPrefix(const std::string& a, const std::string& b) {
    size_t i = 0;
    while (i != a.size() && i != b.size() && a[i] == b[i]) {
        ++i;
    }
    return a.substr(0, i);
}

Теперь можно просто перебрать поданные на вход строки и вычислять на каждом шаге общий префикс у текущей строки и старого префикса:

std::string CommonPrefix(const std::vector<std::string>& words) {
    if (words.empty()) {
        return {};
    }
    std::string prefix = words[0];
    for (size_t i = 1; i != words.size() && !prefix.empty(); ++i) {
        prefix = CommonPrefix(prefix, words[i]);
    }
    return prefix;
}

Здесь мы вызываем в цикле первую функцию CommonPrefix. Компилятор понимает какую из функций надо вызвать по типам аргументов (здесь передаётся не вектор строк, а две строки).

Недостаток этого решения в том, что мы много раз создаём новые строки (префиксы), хотя на самом деле все они являются подстроками первой строки. Поэтому давайте перепишем первую функцию, чтобы она использовала std::string_view — конструкцию, о которой мы поговорим в параграфе «Адаптеры и представления». Во второй функции объявим prefix с явным типом std::string_view, а в конце вернём std::string(prefix): преобразование из string_view обратно в string надо описывать явно.

#include <string>
#include <string_view>
#include <vector>

std::string_view CommonPrefix(const std::string_view a, const std::string_view b) {
    size_t i = 0;
    while (i != a.size() && i != b.size() && a[i] == b[i]) {
        ++i;
    }
    return a.substr(0, i);
}

std::string CommonPrefix(const std::vector<std::string>& words) {
    if (words.empty()) {
        return {};
    }
    std::string_view prefix = words[0];
    for (size_t i = 1; i != words.size() && !prefix.empty(); ++i) {
        prefix = CommonPrefix(prefix, words[i]);
    }
    return std::string(prefix);
}

Рассмотрим альтернативное решение с синхронным проходом. Будем одновременно идти по всем словам. Для этого удобно сначала вычислить их минимальную длину, чтобы было проще проверять, когда пора остановиться.

#include <algorithm>
#include <string>
#include <vector>

std::string CommonPrefix(const std::vector<std::string>& words) {
    if (words.empty()) {
        return {};
    }

    size_t minLen = words[0].size();
    for (const auto& word : words) {
        minLen = std::min(minLen, word.size());
    }

    for (size_t i = 0; i < minLen; ++i) {
        const char c = words[0][i];
        for (const auto& word : words) {
            if (word[i] != c) {
                return word.substr(0, i);
            }
        }
    }

    return words[0].substr(0, minLen);
}

Вам требуется написать функцию со следующим заголовком:

std::vector<std::string> Split(const std::string& str, char delimiter);

Функция должна вернуть вектор строк, полученный разбиением строки str на части по указанному символу-разделителю delimiter. Если разделитель встретился в начале или в конце строки str, то в начале (соответственно, в конце) вектора с результатом должна быть пустая строка. Если два разделителя встретились рядом, то пустая строка между ними тоже должна попасть в ответ. Для пустой строки надо вернуть вектор, содержащий одну пустую строку.

Например, Split("What_is_your_name?", '_') должна вернуть вектор из строк What, is, your иname?.

Примечание

Подключите необходимые заголовочные файлы и напишите только код функции Split. Мы скомпилируем решение с нашей функцией main.

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

Будем поддерживать два индекса: начало и конец очередного фрагмента строки. Будем сдвигать конец вправо. Если нам встретится разделитель, добавим этот фрагмент к ответу и переназначим начало будущего фрагмента на следующий индекс.

В конце надо будет отдельно добавить к ответу последний фрагмент.

#include <string>
#include <vector>

std::vector<std::string> Split(const std::string& str, char delimiter) {
    std::vector<std::string> result;
    size_t i = 0;
    for (size_t j = 0; j != str.size(); ++j) {
        if (str[j] == delimiter) {
            result.push_back(str.substr(i, j - i));
            i = j + 1;
        }
    }
    result.push_back(str.substr(i));
    return result;
}

Заметим, что если исходная строка будет существовать после вызова функции, то может оказаться эффективнее разбивать строку на std::string_view (мы поговорим об этой конструкции в параграфе «Адаптеры и представления»).

#include <string>
#include <string_view>
#include <vector>

std::vector<std::string_view> Split(const std::string& s, char delimiter) {
    std::string_view str = s;
    std::vector<std::string_view> result;
    size_t i = 0;
    for (size_t j = 0; j != str.size(); ++j) {
        if (str[j] == delimiter) {
            result.push_back(str.substr(i, j - i));
            i = j + 1;
        }
    }
    result.push_back(str.substr(i));
    return result;
}

Вам требуется написать функцию Join со следующим заголовком:

std::string Join(const std::vector<std::string>& tokens, char delimiter);

Функция должна вернуть строку, полученную склейкой элементов вектора через указанный разделитель. Например, Join({"What", "is", "your", "name?"}, '_') должна вернуть строку "What_is_your_name?".

Примечание

Если вектор tokens пустой, то функция должна вернуть пустую строку. Если в векторе tokens ровно один элемент, то он и должен вернуться в ответе.

Подключите необходимые заголовочные файлы и напишите только код функции Join. Мы скомпилируем решение с нашей функцией main.

Будем идти по вектору и добавлять в ответ разделитель и очередной токен. Важно, чтобы разделители не оказались по краям — они должны быть только между токенами.

#include <string>
#include <vector>

std::string Join(std::vector<std::string>& tokens, char delim) {
    std::string result;
    for (size_t i = 0; i != tokens.size(); ++i) {
        if (i > 0) {
            result += delim;
        }
        result += tokens[i];
    }
    return result;
}

Дана прямоугольная матрица из строк и столбцов. Транспонированной матрицей называется матрица из строк и столбцов, в которой строки и столбцы поменялись ролями: элемент равен элементу .

Напишите функцию, которая возвращает транспонированную матрицу:

std::vector<std::vector<int>> Transpose(const std::vector<std::vector<int>>& matrix);

Примечание

Гарантируется, что вектор matrix непуст и все его элементы имеют равную ненулевую длину.

Подключите необходимые заголовочные файлы и напишите только код функции Transpose. Мы скомпилируем решение с нашей функцией main.

#include <vector>

std::vector<std::vector<int>> Transpose(const std::vector<std::vector<int>>& matrix) {
    const size_t m = matrix.size();
    const size_t n = matrix[0].size();

    std::vector<std::vector<int>> result(n);
    for (size_t j = 0; j != n; ++j) {
        result[j].resize(m);
        for (size_t i = 0; i != m; ++i) {
            result[j][i] = matrix[i][j];
        }
    }
    return result;
}

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

Формат ввода

Сначала задано количество точек . Затем идет последовательность из строк, каждая из которых содержит два целых числа — координаты точки. Величина не превосходит 100. Координаты точек по модулю не превосходят 1000.

Формат вывода

Выведите через пробел кординаты точек в порядке возрастания расстояний до начала координат. После каждой пары координат печатайте перевод строки.

Пример

Создадим структуру Point для хранения точки. Заполним вектор этих структур. Напишем лямбда-функцию для сравнения двух точек. Заметим, что вычислять квадратный корень не обязательно: достаточно сравнить целочисленную сумму квадратов.

#include <algorithm>
#include <iostream>
#include <vector>

struct Point {
    int x;
    int y;
};

int main() {
    size_t n;
    std::cin >> n;

    std::vector<Point> points(n);

    for (size_t i = 0; i != n; ++i) {
        std::cin >> points[i].x >> points[i].y;
    }

    std::sort(
        points.begin(),
        points.end(),
        [](const Point& p1, const Point& p2) {
            return p1.x * p1.x + p1.y * p1.y < p2.x * p2.x + p2.y * p2.y;
        }
    );

    for (const auto& point : points) {
        std::cout << point.x << " " << point.y << "\n";
    }
}

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