КШ ФИСТ. Олимпиадное программирование

Полезные ссылки

• Фолунин Владимир Александрович — v.folunin@gmail.com

Не забудьте указать тему, представиться и обстоятельно описать свою проблему.

• Дневник группы

• Архивы задач, которые мы используем:

• acmp.ru
• informatics.mccme.ru
• codeforces.com
• ulivt.ru

Подготовка к работе

Установка среды разработки

• Visual Studio 2017 Community (для Windows 7 — Windows 10)

Выберите только вариант «Разработка классических приложений на C++»

• Visual Studio 2010 (для Windows XP, но также рекомендуется, если вы не хотите выкачивать большие установочные файлы)

Создание проекта в Visual Studio

Создаём проект:

Меню Файл (File) → Создать (New) → Проект... (Project...) → слева выбираем Visual C++ → справа выбираем Пустой проект (Empty Project) → вводим имя проекта → OK.

Добавляем в проект новый файл:

Меню Проект (Project) → Добавить новый элемент... (Add New Item...) → Файл C++ (C++ File) → вводим имя файла → Добавить (Add).

Решение проблем

• Visual Studio не позволяет мне использовать scanf

Меню Проект (Project) → Свойства (Properties) → C/C++ → Проверки SDL (SDL Checks) → выбрать значение Нет (No) → OK.

Другой способ: скопировать в начало программы строку #define _CRT_SECURE_NO_WARNINGS

• При запуске появляется окно Следующий проект устарел. Выполнить его сборку? (This project is out of date. Would you like to build it?)

Поставьте галочку Больше не выводить это окно (Do not show this dialog again) и нажмите кнопку Да (Yes).

• Если программа содержит ошибки, при запуске появляется окно Возникли ошибки сборки. Продолжить и запустить последний успешно построенный вариант? (There were build errors. Would you like to continue and run the last successful build?)

Поставьте галочку Больше не выводить это окно (Do not show this dialog again) и нажмите кнопку Нет (No).

• Где посмотреть, какие у меня ошибки?

Меню Вид (View) → Список ошибок (Error List). В более старых версиях: View → Other Windows → Error List.

Вспомогательные материалы к занятиям

Функции

Определение функций

Определение функции в языке C++ имеет следующий вид (количество параметров может быть иным):

типВозвращаемогоЗначения имяФункции(типПараметра1 имяПараметра1, типПараметра2 имяПараметра2) {
    
}

Для возврата значения из функции используется ключевое слово return. При достижении строки с return функция немедленно завершается, а в место её вызова подставляется значение, записанное справа от return.

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

double rectangleArea(double width, double height) {
    return width * height;
}

double triangleArea(double a, double b, double c) {
    double p = (a + b + c) / 2;
    return sqrt(p * (p - a) * (p - b) * (p - c));
}

double circleArea(double radius) {
    double pi = acos(-1.0);
    return pi * radius * radius;
} 

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

double segmentLength(double ax, double ay, double dx, double by) {
    double dx = ax - bx;
    double dy = ay - by;
    return sqrt(dx * dx + dy * dy);
}

double triangleArea(double ax, double ay, double dx, double by, double cx, double cy) {
    double ab = segmentLength(ax, ay, bx, by);
    double ac = segmentLength(ax, ay, cx, cy);
    double bc = segmentLength(bx, by, cx, cy);
    double p = (ab + ac + bc) / 2;
    return sqrt(p * (p - ab) * (p - ac) * (p - bc));
}

int main() {
    printf("%lf", triangleArea(0, 0, 10, 0, 0, 10));
}

Функция может не иметь возвращаемого значения. Для обозначения такой функции используется ключевое слово void.

//функция, n раз выводящая символ c
void repeatSymbol(char c, int n) {
    for (int i = 0; i < n; i++)
        printf("%c", c);
}

Передача параметров в функцию

По умолчанию используется передача параметров по значению. Её особенности:

• Внутри функции создаются копии переданных переменных;
• Изменения, произошедшие с параметрами внутри функции, не сохранятся вне функции.

void swap(int a, int b) {
    int t = a;
    a = b;
    b = t;
}

int main() {
    int x = 10, y = 20;
    swap(x, y);
    printf("x=%d y=%d"); //будет выведено x=10 y=20
}

Старый способ сохранения сделанных внутри функции изменений — передача по указателю (вместо самих переменных передаются их адреса, см. функцию scanf).

Современный способ сохранения сделанных внутри функции изменений — передача по ссылке.

Добавление знака & перед именем параметра означает передачу по ссылке. Её особенности:

• Внутри функции используются непосредственно сами переданные переменные;
• Изменения, произошедшие с параметрами внутри функции, сохранятся вне функции;
• По ссылке невозможно передать константы.

void swap(int &a, int &b) {
    int t = a;
    a = b;
    b = t;
}

int main() {
    int x = 10, y = 20;
    swap(x, y);
    printf("x=%d y=%d"); //будет выведено x=20 y=10
}

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

int sum(int a[], int size) {
    int res = 0;
    for (int i = 0; i < size; i++)
        res += a[i];
    return res;
}

Символы и строки

Символы

Любое целое число в диапазоне от 0 до 127 может быть интерпретировано как символ с соответствующим кодом (кодировка ASCII):

int x = 65;
printf("%c", x); //будет выведено A

Для хранения символьных переменных (и маленьких целых чисел) целесообразно использовать 8-битовый целый тип char. Символьные константы заключаются в одинарные кавычки.

char symbol = '#';

Для ввода и вывода символов при помощи scanf и printf следует использовать спецификатор %c.

char x;
scanf(" %c", &x);
printf("symbol %c has code %d\n", x, x);

Важно, что если символы вводятся через пробелы, и эти пробелы требуется пропустить, в scanf перед спецификатором %c следует поставить пробел. Этот пробел предписывает scanf при вводе переставить каретку на следующий непробельный символ.

char a, b;
scanf("%c%c", &a, &b);   //ввод "X Y", результат: a == 'X', b == ' '
scanf(" %c %c", &a, &b); //ввод "X Y", результат: a == 'X', b == 'Y'

Полезные функции для работы с символами содержатся в заголовочном файле <ctype.h>. Наиболее часто используемые из них:

• isdigit(c) — возвращает true, если символ c является десятичной цифрой;
• islower(c) — возвращает true, если символ c является строчной латинской буквой;
• isupper(c) — возвращает true, если символ c является заглавной латинской буквой;
• isalpha(c) — возвращает true, если символ c является латинской буквой;
• tolower(c) — если символ c является заглавной латинской буквой, возвращает соответствующую строчную букву, иначе возвращает символ c;
• toupper(c) — если символ c является строчной латинской буквой, возвращает соответствующую заглавную букву, иначе возвращает символ c;

Строки в стиле C

В языке C для хранения строк используются массивы char. Чтобы обозначить конец строки, используется специальный символ '\0' (числовой код 0), поэтому при указании размера массива всегда требуется выделять на одну ячейку больше, чем максимально возможное количество символов в строке.

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

char message[6] = "Hello";
printf("%d %d %d", message[0], message[2], message[5]); //будет выведено 72 108 0

Строки можно считывать и выводить при помощи scanf и printf, используя спецификатор %s. Для пропуска пробелов и переводов строк перед %s можно поставить пробел (как и в случае с %c).

char name[30];
scanf(" %s", &name);
printf("Hello %s!", name);

Если в scanf использован спецификатор %s, строка считывается до первого пробельного символа. Если нужно прочитать строку с пробелами (до символа \n), следует использовать спецификатор %[^\n].

scanf(" %s", &text);     //ввод "programming is fun!", результат: text == "programming"
scanf(" %[^\n]", &text); //ввод "programming is fun!", результат: text == "programming is fun!"

Пройти по элементам строки можно при помощи цикла for:

for (int i = 0; s[i] != 0; i++) {
    //работа с элементом s[i]
}

Полезные функции для работы со строками содержатся в заголовочном файле <string.h>. Наиболее часто используемые из них:

• strlen(s) — возвращает длину строки s (без учёта завершающего нуля);
• strcpy(s1, s2) — копирует строку s2 в s1 (аналог несуществующей операции s1 = s2);
• strcat(s1, s2) — дописывает строку s2 к s1 (аналог несуществующей операции s1 += s2);
• strcmp(s1, s2) — возвращает 0, если строки s1 и s2 равны, отрицательное число, если s1 лексикографически меньше s2, либо положительное число, если s2 лексикографически больше s2 (аналог несуществующих операций s1 == s2, s1 < s2, s1 > s2);
• strchr(s, x) — возвращает указатель на первое вхождение символа x в строку s либо 0, если x не содержится в s. Чтобы получить индекс символа x в строке s, нужно записать int index = strchr(s, x) - s;
• strstr(s1, s2) — возвращает указатель на первое вхождение строки s2 в строку s1 либо 0, если s2 не содержится в s1. Чтобы получить индекс строки s2 в строке s1, нужно записать int index = strstr(s1, s2x) - s1;

Строки в стиле C++

В языке C++ для хранения строк используется специальный тип string. Чтобы получить к нему доступ, нужно подключить заголовочный файл <string> (не путать со <string.h>!) и пространство имён std.

#include <string>
using namespace std;

int main() {
    string s = "Hello!";
}

Строки типа string нельзя вводить при помощи scanf. Для ввода следует использовать одну из двух возможностей:

#include <stdio.h> #include <string> using namespace std; int main() { char buffer[100]; scanf(" %s", &buffer); string s = buffer; }

#include <iostream> #include <string> using namespace std; int main() { string s; cin >> s; }

Для вывода строки типа string с помощью printf необходимо предварительно вызвать у строки метод .c_str(), возвращающий аналог строки в старом стиле.

string s = "Hello";
printf("%s", s.c_str());

Возможности строк типа string:

• Индексация отдельных символов через квадратные скобки, как у массивов;
• Получение размера строки вызовом метода .size();
• Присваивание строк оператором =;
• Конкатенация строк операторами + и +=;
• Сравнение строк операторами ==, !=, <, >;
• Поиск символов и подстрок в строке вызовом метода .find() (возвращает индекс вхождения либо -1, если вхождение не найдено);
• Получение подстрок вызовом метода .substr().