Программа на С++ — объявление/определение типов, операции над ними и завершение. Для олимпиадного программирования выделим одну из парадигм, которая упростит жизнь в написании кода - ООП, мы как бы определяем свои типы данных и операции над ними. Свой тип мы можем задать с помощью ключевых слов class или struct (эти способы отличаются немногим). Приведу пример определения через struct.
В теле структуры можно объявлять переменные, функции, using-и, другие структуры (нельзя expression-ы).
Поля — это переменные внутри структуры.
Методы — функции, которые мы объявляем в структуре.
Начиная с C++11 полям можно присваивать значения по умолчанию (иначе они будут проинициализированы рандомными значениями, обращение к ним UB).
Есть ключевое слово this, обозначающее указатель на текущий объект, к примеру
Методы можно объявлять внутри класса, а определять снаружи:
В ООП обычно выделяют 3 популярных принципа: инкапсуляция, наследование и полиморфизм. Одно из пониманий инкапсуляции: поля и методы (данные) хранятся в одной структуре (капсуле), другое - должно быть разграничение доступа, то есть к данным напрямую имеют доступ только методы работы с этими данными, а «внешние» имеют доступ только к методам, но не к данным напрямую (классический пример — интерфейс стиральной машинки, кнопочки — методы).
Существует 3 модификатора доступа: public, private, protected.
• private. Это значит не доступно никому, кроме моих методов и моих друзей.
• public. Это - доступно всем.
• protected. (Будет рассмотрен в следующих постах).
По умолчанию все поля у class - private, а у struct - public.
С освоением ООП вам будет проще реализовывать свои идеи, например существует отдельный тег задач - геометрия. Сложные геометрические задачи писать без структур очень неудобно и в процессе можно запутаться в коде и в количестве переменных.
struct MyClass {
// Поля
int x; char c; double d;
// Методы
void printSum(int y) {
std::cout << x + y; // x здесь будет взято из поля объекта класса от которого будет вызван метод
}
};
int main() {
MyClass t;
t.x = 4; //обращение к полю класса работает через точку, здесь мы задали новое значение для поля x
t.f(6); // ожидаемый вывод 10
}
В теле структуры можно объявлять переменные, функции, using-и, другие структуры (нельзя expression-ы).
Поля — это переменные внутри структуры.
Методы — функции, которые мы объявляем в структуре.
Начиная с C++11 полям можно присваивать значения по умолчанию (иначе они будут проинициализированы рандомными значениями, обращение к ним UB).
Есть ключевое слово this, обозначающее указатель на текущий объект, к примеру
struct MyClass{
int x = 1;
void f(int x) {
std::cout << this->x + x; // первый элемент будет взят из экземпляра структуры, второй - как аргумент функции
}
};
Методы можно объявлять внутри класса, а определять снаружи:
struct MyClass {
int x = 1;
void f(int);
};
void MyClass::f(int y) {
std::cout << x + y;
}
В ООП обычно выделяют 3 популярных принципа: инкапсуляция, наследование и полиморфизм. Одно из пониманий инкапсуляции: поля и методы (данные) хранятся в одной структуре (капсуле), другое - должно быть разграничение доступа, то есть к данным напрямую имеют доступ только методы работы с этими данными, а «внешние» имеют доступ только к методам, но не к данным напрямую (классический пример — интерфейс стиральной машинки, кнопочки — методы).
Существует 3 модификатора доступа: public, private, protected.
• private. Это значит не доступно никому, кроме моих методов и моих друзей.
• public. Это - доступно всем.
• protected. (Будет рассмотрен в следующих постах).
По умолчанию все поля у class - private, а у struct - public.
struct MyClass {
private:
int x = 1;
public:
int y = 1;
};
int main() {
MyClass e;
e.y; //здесь ошибки не будет
e.x; //ошибка компиляции, это поле доступно только внутри структуры.
}
С освоением ООП вам будет проще реализовывать свои идеи, например существует отдельный тег задач - геометрия. Сложные геометрические задачи писать без структур очень неудобно и в процессе можно запутаться в коде и в количестве переменных.
Камрады, кто не отобрался на все заклы, в ближайшие две недели пройдут отборы на следующие олимпиады. Не забываем про них и выигрываем.
Открытая олимпиада ИТМО по информатике, 11 класс (1 уровень):
5 - 11 февраля отбор в формате онлайн (в чате канала будут выложены задания одного из вариантов тура, вариантов будет много, так что не сильно надеемся на это).
Архив заданий заключительных и отборочных этапов прошлых лет можете найти здесь.
Небольшие рекомендации по подготовке к ИТМО и описание олимпиады:
Это отличная возможность получить 100 баллов по информатике на топовые факультеты сильнейших вузов, не упускайте эту возможность. Олимпиада в первую очередь не по программированию, а по информатике, если вы не знаете алгоритмов или вы пришли с олмата, то у вас по-прежнему будет возможность показать себя на этой олимпиаде. Минимальные знания по программированию, которые могут понадобиться - это знание базового синтаксиса языка и умение работать с табличками в excel (как альтернатива pandas в python) Идеальная подготовка к этой олимпиаде может выглядеть, как просто прорешка вариантов прошлых лет(разборы которых выложены в архиве). Не стоит делать большой упор на задачи по олпроге во время тренировок, обычно их в туре около двух из 8/9 и в основном это реализация или конструктив.
Индивидуальная олимпиада школьников по информатике и программированию 11 класс (1 уровень):
2 февраля в 15:00. Пройдёт первый отборочный тур.
Контесты заключительных этапов прошлых лет можете найти здесь, также есть контесты от той же команды авторов и отборочные этапы по этой ссылке.
Небольшие рекомендации по подготовке к ИТМО и описание олимпиады:
Олимпиада проводится в ioi формате и только для 11х классов, отличная возможность получить бви в топ вузы, так как заключительный этап проводится в конце сезона (многие ребята уже на этот момент будут иметь бви и возможно не пойдут писать эту олимпиаду + задачи легче, чем обычно на олимпиадах по программированию первого уровня).
Вузовско-академическая олимпиада по информатике (1 уровень):
3-9 февраля онлайн отбор (контест в виртуальном режиме).
Архивы задач прошлых лет можно найти на том же сайте.
Описание олимпиады:
Олимпиада с очень приятными задачами и зачастую новыми идеями. Небольшое количество участников финала (соответственно пулл дипломов около 60). Также проводится ближе к концу сезона, что является плюсом. С прошлого года заключительный этап начал проводиться онлайн (возможно что-то поменяется), за счёт этого появились сильные участники из многих регионов, ранее финалы писались в трёх городах, отдалённых от столицы.
МОШ 6-9:
9 февраля заключительный этап.
В этом посте можно найти раунды составленные по задачам с олимпиады.
Описание олимпиады:
Про мош 6-9 трудно сказать, что это олимпиада для начинающих, несмотря на юный возраст участников. Присутствуют сложные конструктивные задачи, но на призёра опытные олимпиадники могут набрать без труда необходимый балл, за счёт низких порогов(но не думаю, что здесь важно гнаться за дипломами, главное набраться опыта).
Всем успешных туров, лёгких задач и больше классных идей! Не ловите тильт после туров, олимпиад большое количество, вам точно найдётся местечко на БВИ!
Открытая олимпиада ИТМО по информатике, 11 класс (1 уровень):
5 - 11 февраля отбор в формате онлайн (в чате канала будут выложены задания одного из вариантов тура, вариантов будет много, так что не сильно надеемся на это).
Архив заданий заключительных и отборочных этапов прошлых лет можете найти здесь.
Небольшие рекомендации по подготовке к ИТМО и описание олимпиады:
Это отличная возможность получить 100 баллов по информатике на топовые факультеты сильнейших вузов, не упускайте эту возможность. Олимпиада в первую очередь не по программированию, а по информатике, если вы не знаете алгоритмов или вы пришли с олмата, то у вас по-прежнему будет возможность показать себя на этой олимпиаде. Минимальные знания по программированию, которые могут понадобиться - это знание базового синтаксиса языка и умение работать с табличками в excel (как альтернатива pandas в python) Идеальная подготовка к этой олимпиаде может выглядеть, как просто прорешка вариантов прошлых лет(разборы которых выложены в архиве). Не стоит делать большой упор на задачи по олпроге во время тренировок, обычно их в туре около двух из 8/9 и в основном это реализация или конструктив.
Индивидуальная олимпиада школьников по информатике и программированию 11 класс (1 уровень):
2 февраля в 15:00. Пройдёт первый отборочный тур.
Контесты заключительных этапов прошлых лет можете найти здесь, также есть контесты от той же команды авторов и отборочные этапы по этой ссылке.
Небольшие рекомендации по подготовке к ИТМО и описание олимпиады:
Олимпиада проводится в ioi формате и только для 11х классов, отличная возможность получить бви в топ вузы, так как заключительный этап проводится в конце сезона (многие ребята уже на этот момент будут иметь бви и возможно не пойдут писать эту олимпиаду + задачи легче, чем обычно на олимпиадах по программированию первого уровня).
Вузовско-академическая олимпиада по информатике (1 уровень):
3-9 февраля онлайн отбор (контест в виртуальном режиме).
Архивы задач прошлых лет можно найти на том же сайте.
Описание олимпиады:
Олимпиада с очень приятными задачами и зачастую новыми идеями. Небольшое количество участников финала (соответственно пулл дипломов около 60). Также проводится ближе к концу сезона, что является плюсом. С прошлого года заключительный этап начал проводиться онлайн (возможно что-то поменяется), за счёт этого появились сильные участники из многих регионов, ранее финалы писались в трёх городах, отдалённых от столицы.
МОШ 6-9:
9 февраля заключительный этап.
В этом посте можно найти раунды составленные по задачам с олимпиады.
Описание олимпиады:
Про мош 6-9 трудно сказать, что это олимпиада для начинающих, несмотря на юный возраст участников. Присутствуют сложные конструктивные задачи, но на призёра опытные олимпиадники могут набрать без труда необходимый балл, за счёт низких порогов(но не думаю, что здесь важно гнаться за дипломами, главное набраться опыта).
Всем успешных туров, лёгких задач и больше классных идей! Не ловите тильт после туров, олимпиад большое количество, вам точно найдётся местечко на БВИ!
Как мы ранее уже упоминали - результат олимпиад по программированию достаточно сильно может зависеть от того, насколько много задач видел участник до этого. Написание виртуальных туров является очень важным в подготовке, но развивать умение придумывать задачи лучше через спокойное прорешивание архивов, тематических туров.
Поэтому сегодня я хочу поговорить про то, как выбирать задачи для прорешки, чтобы наиболее эффективно готовиться к олимпиадам.
1. Стоит ли выбирать задачи случайной тематики или на конкретный прием/алгоритм?
Я считаю, что на начальном уровне лучше прорешать несколько подборок на конкретные алгоритмы, чтобы понять основные паттерны задач такого типажа. К примеру, умение придумать задачу на корневые оптимизации приходит многим после того, как они прорешали не одну подборку из таких задач. Но когда вы закрепили стандартные приемы нужно научиться их уже использовать в ситуации, когда у вас нет подсказки на что задача. Вы можете прорешать кучу подборок на графы, но это не поможет вам решить задачу, где тяжело понять, что графы вообще нужны. В таком случае гораздо полезнее опыт нарешивания задач без знания, что в ней требуется.
2. Какой сложности выбирать задачи?
Лучше всего решать задачи, которые немного выше вашего уровня. Не нужно замахиваться на слишком сложные задачи, потому что скорее всего вы потратите кучу времени безрезультативно. Решать простые задачи тоже не имеет смысла, потому что так идейно вы особо не развиваетесь. Есть хороший пост, как выбирать задачи на платформе codeforces исходя из вашего рейтинга.
3. После каждого написанного виртуального тура стоит смотреть разбор задач, но некоторые можно себе оставлять для самостоятельного обдумывания. Например, если вы решали тур сложности региона, и ваша цель научиться решать задачи сложности С, то лучше не сразу смотреть разбор таких задач, а попытаться после тура их решить самому.
Поэтому сегодня я хочу поговорить про то, как выбирать задачи для прорешки, чтобы наиболее эффективно готовиться к олимпиадам.
1. Стоит ли выбирать задачи случайной тематики или на конкретный прием/алгоритм?
Я считаю, что на начальном уровне лучше прорешать несколько подборок на конкретные алгоритмы, чтобы понять основные паттерны задач такого типажа. К примеру, умение придумать задачу на корневые оптимизации приходит многим после того, как они прорешали не одну подборку из таких задач. Но когда вы закрепили стандартные приемы нужно научиться их уже использовать в ситуации, когда у вас нет подсказки на что задача. Вы можете прорешать кучу подборок на графы, но это не поможет вам решить задачу, где тяжело понять, что графы вообще нужны. В таком случае гораздо полезнее опыт нарешивания задач без знания, что в ней требуется.
2. Какой сложности выбирать задачи?
Лучше всего решать задачи, которые немного выше вашего уровня. Не нужно замахиваться на слишком сложные задачи, потому что скорее всего вы потратите кучу времени безрезультативно. Решать простые задачи тоже не имеет смысла, потому что так идейно вы особо не развиваетесь. Есть хороший пост, как выбирать задачи на платформе codeforces исходя из вашего рейтинга.
3. После каждого написанного виртуального тура стоит смотреть разбор задач, но некоторые можно себе оставлять для самостоятельного обдумывания. Например, если вы решали тур сложности региона, и ваша цель научиться решать задачи сложности С, то лучше не сразу смотреть разбор таких задач, а попытаться после тура их решить самому.
Сегодня мы поговорим про самую важную часть олимпиадного программирования: big O оценка асимптотики кода. Основной таргет любой задачи на олмпиаде заключается в написании эффективного алгоритма, который уложится в ограничения по времени и по памяти.
Что такое big O?
Для оценки сложности алгоритма применим концепт big O, схожая с асимптотической сложностью функций в математическом анализе. Что же означает запись f(x) ∈ O(g(x)). O(g(x)) - это класс функций, которые удовлетворяют следующим условиям: ∃(C > 0), N : ∀(n > N) f (n) ≤ C * g(n). Как мы будем пользоваться таким концептом в теории алгоритмов? Любое простейшее вычисление (например сложение, вычитание, умножение и т.п.) примем за константу, то есть O(1). Примем за n, параметр дающийся в качестве входных данных алгоритма, тогда если наш алгоритм будет выглядеть, как n простейших операций, то временная сложность такого алгоритма уже будет выглядеть, как O(n). Аналогично и с подсчётом памяти - если алгоритм будет в run time хранить структуру на n элементов, то и память будет оцениваться, как O(n).
Как ограничения могут подсказать к решению?
К каждой задаче заданы ограничения на входные данные, по которым можно примерно понять, что от тебя ожидается в ней. Пример рассуждения: в задаче на динамику на достаточно большой балл ожидается n <= 300, значит асимптотика решения здесь будет O(n^3), на полный же балл n <= 3000- O(n^2). Из чего вы можете сделать вывод, что если не придумалось сразу решение на полный балл, то вначале стоит придумать динамику за куб и потом пытаться с оптимизировать решение на полный балл (вполне вероятно даже сможете угадать трюк, с помощью которого ожидается оптимизация, в данной ситуации быть может подошла оптимизация преффсуммами в динамике). Или же если вы видите ограничения n<=10^7, то сразу становится понятным, что асимптотика ожидаемого решения будет O(n). Таких ситуаций очень много, так что ограничения на задачу является полноценной частью условия и не забывайте также обращать внимание на это.
Потренируемся оценивать асимптотику:
Коды будут описаны на псевдокоде, также не стоит вникать в смысловую нагрузку кода, это в данной ситуации неважно.
Задача 1:
Ответ:O(1)
Задача 2:
Ответ:O(log(n))
Задача 3:
do() - функция работающая за O(1)
Ответ:O(2^n)
Задача 4:
f(n) - Функция работающая за O(1)
Ответ:O(n * log(n))
Что такое big O?
Для оценки сложности алгоритма применим концепт big O, схожая с асимптотической сложностью функций в математическом анализе. Что же означает запись f(x) ∈ O(g(x)). O(g(x)) - это класс функций, которые удовлетворяют следующим условиям: ∃(C > 0), N : ∀(n > N) f (n) ≤ C * g(n). Как мы будем пользоваться таким концептом в теории алгоритмов? Любое простейшее вычисление (например сложение, вычитание, умножение и т.п.) примем за константу, то есть O(1). Примем за n, параметр дающийся в качестве входных данных алгоритма, тогда если наш алгоритм будет выглядеть, как n простейших операций, то временная сложность такого алгоритма уже будет выглядеть, как O(n). Аналогично и с подсчётом памяти - если алгоритм будет в run time хранить структуру на n элементов, то и память будет оцениваться, как O(n).
Как ограничения могут подсказать к решению?
К каждой задаче заданы ограничения на входные данные, по которым можно примерно понять, что от тебя ожидается в ней. Пример рассуждения: в задаче на динамику на достаточно большой балл ожидается n <= 300, значит асимптотика решения здесь будет O(n^3), на полный же балл n <= 3000- O(n^2). Из чего вы можете сделать вывод, что если не придумалось сразу решение на полный балл, то вначале стоит придумать динамику за куб и потом пытаться с оптимизировать решение на полный балл (вполне вероятно даже сможете угадать трюк, с помощью которого ожидается оптимизация, в данной ситуации быть может подошла оптимизация преффсуммами в динамике). Или же если вы видите ограничения n<=10^7, то сразу становится понятным, что асимптотика ожидаемого решения будет O(n). Таких ситуаций очень много, так что ограничения на задачу является полноценной частью условия и не забывайте также обращать внимание на это.
Потренируемся оценивать асимптотику:
Коды будут описаны на псевдокоде, также не стоит вникать в смысловую нагрузку кода, это в данной ситуации неважно.
Задача 1:
a = 1
b = 2
print a + b
Ответ:
Задача 2:
def f(n):
if n > 0: f( n / 2 )
f(abs(n))
Ответ:
Задача 3:
do() - функция работающая за O(1)
def f(n, dep, el):
if (n == dep) do()
else: do(), f(n, dep + 1, 0), f(n, dep + 1, 1)
Ответ:
Задача 4:
f(n) - Функция работающая за O(1)
for i in range(1, n):
j = i
while j < n:
j += i
f(j)
Ответ:
tasks&solutionITMO.pdf
12.9 MB
Товарищи, направляю вам гуманитарную помощь!
Олимпиада ИТМО по информатике завершается уже сегодня в 23:59. Мы постарались и сделали разбор (в файле разбор и условие) одного варианта для 11х классов, изменения между вариантами по задачам должны быть минимальны, поэтому прикрепили решения и коды, которые нужно будет немного видоизменить, если вдруг у вас выпадет другая задача. Берите идеи решения из разбора, советую перепроверять ответы. В последний день задания точно не поменяются, так что настраивайтесь на тот же типаж задач, что и в файле. Ваша цель набрать ~10-11 баллов за два тура, но всё равно старайтесь набрать свой максимум, не потеряйте шанс взять простейший диплом олимпиады 1го уровня по инфе.
P. S. В 6 задаче опечатка в техе в самом начале\root\output.txt -> /root/output.txt
Также недавно открылась регистрация на мош 10-11, регистрируемся на отбор!
Еще больше разборов и контента найдете на нашем канале
Олимпиада ИТМО по информатике завершается уже сегодня в 23:59. Мы постарались и сделали разбор (в файле разбор и условие) одного варианта для 11х классов, изменения между вариантами по задачам должны быть минимальны, поэтому прикрепили решения и коды, которые нужно будет немного видоизменить, если вдруг у вас выпадет другая задача. Берите идеи решения из разбора, советую перепроверять ответы. В последний день задания точно не поменяются, так что настраивайтесь на тот же типаж задач, что и в файле. Ваша цель набрать ~10-11 баллов за два тура, но всё равно старайтесь набрать свой максимум, не потеряйте шанс взять простейший диплом олимпиады 1го уровня по инфе.
P. S. В 6 задаче опечатка в техе в самом начале
Также недавно открылась регистрация на мош 10-11, регистрируемся на отбор!
Еще больше разборов и контента найдете на нашем канале
Postupashki_Task.pdf
83.8 KB
Доброе утро, камрады! Сегодня публикуем авторскую задачу, а тот, кто первый её решит, получит купон на выбор: скидка 50% на любой курс поступашек/поступашек ШАД или скидка 100% на будущие курсы от поступашки-информатика!
Формат сдачи следующий: вы оформляете решение в latex/word, пишите тег #ПоступашкиИнформатикаКонтест1 кидаете pdf нам в личку @postupashkaProg (важно строго доказать любое из утверждений и асимптотику полученного решения, не принимаются доказательства вида: "ну в плане, очевидно"). Решения, нарушившие правила отправки, останутся без проверки.
Вердикты после проверки:
1. 👍 - Если вы решили и мы отписали вам, то вы выиграли.
2. 🤔 - Присутствуют неточности/недоказанные вещи в решении. (Штраф: 5 часов).
3.👎 - Ошибочное решение (Штраф: 10 часов).
Время сдачи=время отправки+общий штраф. Проверять будем по мере возможности, победителя объявим в конце недели и опубликуем авторское решение. Всем успехов!
UPD:
В рамках задачи будем считать, что операции над числами работают за O(1).
Формат сдачи следующий: вы оформляете решение в latex/word, пишите тег #ПоступашкиИнформатикаКонтест1 кидаете pdf нам в личку @postupashkaProg (важно строго доказать любое из утверждений и асимптотику полученного решения, не принимаются доказательства вида: "ну в плане, очевидно"). Решения, нарушившие правила отправки, останутся без проверки.
Вердикты после проверки:
1. 👍 - Если вы решили и мы отписали вам, то вы выиграли.
2. 🤔 - Присутствуют неточности/недоказанные вещи в решении. (Штраф: 5 часов).
3.👎 - Ошибочное решение (Штраф: 10 часов).
Время сдачи=время отправки+общий штраф. Проверять будем по мере возможности, победителя объявим в конце недели и опубликуем авторское решение. Всем успехов!
UPD:
В рамках задачи будем считать, что операции над числами работают за O(1).
Друзья, в нашем сообществе теперь новая рубрика, открываем сезон контестов с разборами. Будем публиковать раз в неделю контесты из 6 задач, затем по прошествии недели, будем проводить видеоразбор всех задач!
Первый контест уже доступен по ссылке.
Первый контест уже доступен по ссылке.
Товарищи, сегодня продолжим рубрику с интересными аспектами языка c++. На повестке дня у нас: конструкторы и деструкторы класса (Часть 1).
Ну что же давайте разберёмся с этим. Ранее мы уже узнали о том, что у класса есть методы, теперь же поговорим о таких методах, которые создают экземпляр класса из переданных параметров (например: вот именно те загадочные круглые скобочки при создании вектора, куда мы можем передать размерность, значение которым можем заполнить и более сложные вещи, которые мы узнаем впоследствии).
Приведём примеры вызовов конструкторов:
Про инициализацию с помощью std::initializer_list, можете глянуть здесь.
А здесь мы поговорим про первый вид инициализации, на самом то деле мы здесь выполнили присвоение уже созданных объектов. Так как когда идёт чтение кода из тела конструктора, все переменные уже созданы и проинициализированы значениями взятыми при объявлении полей, нам же не хочется чтобы не выполнялось лишнее присвоение в теле конструктора, поэтому существует синтаксис Member initializer list, который позволит сразу вызывать конструкторы у объектов полей с нужными параметрами.
В идеале пользоваться телом конструктора нужно для более сложных операций.
Важно уточнить, что порядок инициализации нельзя задать порядком написания в этом листе (то есть на момент исполнения y_(y), нельзя гарантировать, что все предыдущие члены уже сконструированы), фактически есть правила, по которым выстраивается эта последовательность (можно глянуть в разделе initializer order, но это не так важно и легче просто пользоваться в этом листе только аргументами конструктора, чтобы не словить UB).
Перед познанием деструкторов обсудим элементарные идеи. У каждой переменной есть свой lifetime, который задаётся с момента создания экземпляра и заканчивается моментом уничтожения, также существует область видимости переменной (думаю вы слышали такие слова, как глобальная переменная, локальная и т.п.). Область видимости - это подмножество программы, в которой будет жить переменная (обычно область видимости ограничена фигурными скобками).
Теперь определим понятие деструктора:
Деструктор - то, что вызывается в конце lifetime объекта и удаляет объект из памяти. Деструкторы будут вызываться в обратном порядке объявленных полей (кстати именно поэтому порядок member initializer list невозможно задать порядком написания, это как раз нарушит работу деструктора).
Фактически вам очень редко нужно будет писать собственный деструктор, так как компилятор автоматически генерирует их, но вот один из примеров.
Ну что же давайте разберёмся с этим. Ранее мы уже узнали о том, что у класса есть методы, теперь же поговорим о таких методах, которые создают экземпляр класса из переданных параметров (например: вот именно те загадочные круглые скобочки при создании вектора, куда мы можем передать размерность, значение которым можем заполнить и более сложные вещи, которые мы узнаем впоследствии).
Приведём примеры вызовов конструкторов:
class Point {
private:
int x_ = 0;
int y_ = 0;
int dim_ = 2;
public:
Point(int x, int y) {
x_ = x;
y_ = y;
}
Point(int x){
dim_ = 1;
x_ = x;
}
}
int main() {
Point vec(1, 2);
Point vec{1, 2};
Point vec = {1, 2};
}
Про инициализацию с помощью std::initializer_list, можете глянуть здесь.
А здесь мы поговорим про первый вид инициализации, на самом то деле мы здесь выполнили присвоение уже созданных объектов. Так как когда идёт чтение кода из тела конструктора, все переменные уже созданы и проинициализированы значениями взятыми при объявлении полей, нам же не хочется чтобы не выполнялось лишнее присвоение в теле конструктора, поэтому существует синтаксис Member initializer list, который позволит сразу вызывать конструкторы у объектов полей с нужными параметрами.
Point(int x, int y): x_(x), y_(y) {}
В идеале пользоваться телом конструктора нужно для более сложных операций.
Важно уточнить, что порядок инициализации нельзя задать порядком написания в этом листе (то есть на момент исполнения y_(y), нельзя гарантировать, что все предыдущие члены уже сконструированы), фактически есть правила, по которым выстраивается эта последовательность (можно глянуть в разделе initializer order, но это не так важно и легче просто пользоваться в этом листе только аргументами конструктора, чтобы не словить UB).
Перед познанием деструкторов обсудим элементарные идеи. У каждой переменной есть свой lifetime, который задаётся с момента создания экземпляра и заканчивается моментом уничтожения, также существует область видимости переменной (думаю вы слышали такие слова, как глобальная переменная, локальная и т.п.). Область видимости - это подмножество программы, в которой будет жить переменная (обычно область видимости ограничена фигурными скобками).
Теперь определим понятие деструктора:
Деструктор - то, что вызывается в конце lifetime объекта и удаляет объект из памяти. Деструкторы будут вызываться в обратном порядке объявленных полей (кстати именно поэтому порядок member initializer list невозможно задать порядком написания, это как раз нарушит работу деструктора).
Фактически вам очень редко нужно будет писать собственный деструктор, так как компилятор автоматически генерирует их, но вот один из примеров.
class Vector {
private:
//где-то здесь различные поля, включая объявления массива buf_
public:
~Vector() {
delete[] buf_;
}
}
SolutionPostupashki.pdf
135.6 KB
Добрый вечер, камрады!
Публикуем письменное решение авторской задачи, а также напоминаем про наш контест, который до сих пор идёт.
Поздравляем @andreydezol, забравшего призы! Однако мы надеемся, что люди, пытавшиеся ее решить, но которым не получилось додумать ее, также получили удовольствие от процесса размышлений.
Также прикладываем полезные материалы, связанные с данной задачей:
📌 Идея 3 из ссылки для поддержания gcd, а также стандартные приемы, не связанные с задачей.
📌 Задача, использующая битовый бор и спуск, нужные в исходной задаче
📌 Пример просто применения метода small-to-large, а также набор полезных учебных задач на эту тему.
#ПоступашкиИнформатикаКонтест1
Публикуем письменное решение авторской задачи, а также напоминаем про наш контест, который до сих пор идёт.
Поздравляем @andreydezol, забравшего призы! Однако мы надеемся, что люди, пытавшиеся ее решить, но которым не получилось додумать ее, также получили удовольствие от процесса размышлений.
Также прикладываем полезные материалы, связанные с данной задачей:
📌 Идея 3 из ссылки для поддержания gcd, а также стандартные приемы, не связанные с задачей.
📌 Задача, использующая битовый бор и спуск, нужные в исходной задаче
📌 Пример просто применения метода small-to-large, а также набор полезных учебных задач на эту тему.
#ПоступашкиИнформатикаКонтест1
Media is too big
VIEW IN TELEGRAM
Товарищи, публикуем разбор первого контеста, надеюсь всем понравилась подборка задач и вы сдадите оставшиеся в дорешку! Не пропускайте следующие анонсы!
Товарищи, второй контест поступашек по информатике уже ждёт вас по этой ссылке. Тренируйтесь и становитесь лучше! А также делитесь идеями решений и впечатлениями от подборки в комментариях или нашем чатике. Желаем всем успешных туров и плодотворной работы!
Товарищи, на повестке дня рубрика с интересными аспектами языка c++. Сегодня будет продолжение постов про конструкторы и деструкторы класса (Часть 2).
📌 Делегирующие конструкторы.
Это фича пришла в C++11, оно позволяет проводить"инкапсуляцию" кода более лёгким образом. Давайте рассмотрим на примере простейшей реализации String. В данной реализации наиболее удобно будет определить конструктор от n, который выделит память на n символов, а остальные можно реализовать с помощью делегирования этого конструктора.
📌 Ключевые слова default и delete.
Эти слова позволяют в явном виде указать свои намерения компиляторы.
default - используется когда требуется явно указать о том, что данный метод будет использовать реализацию по умолчанию, когда существуют пользовательские конструкторы, но нужно использовать методы по умолчанию для других специальных методов.
Пример:
delete - используется для того чтобы явно запретить вызов конкретного метода. (Например если вы хотите заблокировать копирующий конструктор)
Copy constructor - требуется для создания объекта от другого объекта того же типа
Assignment operator - нужен для присвоения объекта того же типа.
(Подробнее про правило трёх и конструторы копирования расскажем в следующей рубрике)
📌 Делегирующие конструкторы.
Это фича пришла в C++11, оно позволяет проводить"инкапсуляцию" кода более лёгким образом. Давайте рассмотрим на примере простейшей реализации String. В данной реализации наиболее удобно будет определить конструктор от n, который выделит память на n символов, а остальные можно реализовать с помощью делегирования этого конструктора.
class String {
private:
char* arr_ = nullptr
size_t sz_ = 0;
size_t capacity_ = 0;
String(size_t n) : arr_(new char[n + 1]), sz_(n), cap(n + 1) {
arr_[sz] = '\0';
}
public;
String() = default;
String(size_t n, char c): String(n) {
std::fill(arr_, arr_ + sz_, c);
}
String(std::initializer_list<char> list): String(list.size()) {
std::copy(list.begin(), list.begin() + sz_, arr_);
}
};
📌 Ключевые слова default и delete.
Эти слова позволяют в явном виде указать свои намерения компиляторы.
default - используется когда требуется явно указать о том, что данный метод будет использовать реализацию по умолчанию, когда существуют пользовательские конструкторы, но нужно использовать методы по умолчанию для других специальных методов.
Пример:
class Point {
public:
Point() = default; //default constructor
Point(const Point&) = default; //default copy constructor
Point& operator=(const Point&) = default; //default assignment operator
~Point() = default; //default destructor
//user constructor
Point(int x, int y) : x_(x), y_(y) {}
private:
int32_t x_;
int32_t y_;
};
delete - используется для того чтобы явно запретить вызов конкретного метода. (Например если вы хотите заблокировать копирующий конструктор)
class Point {
public:
Point() = default; //default constructor
Point(const Point&) = delete; //del copy constructor
Point(int x, int y) : x_(x), y_(y) {}
private:
int32_t x_;
int32_t y_;
};
int main() {
Point a(1, 2);
Point b = a; // CE
}
Copy constructor - требуется для создания объекта от другого объекта того же типа
Assignment operator - нужен для присвоения объекта того же типа.
(Подробнее про правило трёх и конструторы копирования расскажем в следующей рубрике)
Товарищи, продолжим посты про C++. Сегодня покажем полезные функции из стандартной библиотеки, которые могут сильно упростить написание кода в олимпиадных задачах. Знание таких функций знание уменьшит число багов в ваших программах.
📌 min_element и max_element:
Эти функции находят итератор на минимальный и максимальный элемент в диапазоне. Асимптотически эти функции работают за размер диапазона. Функции лежит в библиотеке <algorithm>.
Пример:
📌 count:
Считает количество вхождений элемента в диапазоне. Также лежит в библиотеке <algorithm>.
Пример:
📌 iota:
Заполняет диапазон последовательными значениями, начиная с заданного числа. Лежит в библиотеке <numeric>. Его удобно использовать, как заполнение тождественной перестановки.
Пример:
📌 next_permutation:
Генерирует следующую лексикографическую перестановку диапазона. Возвращает false, если перестановок больше нет. Следующая перестановка запишется в тот вектор, который вы передаете. Удобнее всего использовать эту функцию для перебора всех перестановок. Лежит в <algorithm>
Пример:
📌 accumulate:
Суммирует элементы диапазона (или применяет пользовательскую операцию). Первые два аргумента задают диапазон. Третий аргумент изначальное значение суммирование. Последний аргумент опциональный и нужен для пользовательской операции. В примере используется оператор умножение int. Лежит в <numeric>. Обратите внимание на переполнение. Если сумма может переполниться в int, то третий аргумент должен быть типа long long. (0ll)
Пример:
📌 lower_bound:
Находит первый элемент в отсортированном диапазоне, который не меньше заданного значения. Если такого нет, то возвращает итератор на конец диапазона. Работает за O(log(n)), где n - длина диапазона. Лежит в <algorithm>.
Пример:
📌 min_element и max_element:
Эти функции находят итератор на минимальный и максимальный элемент в диапазоне. Асимптотически эти функции работают за размер диапазона. Функции лежит в библиотеке <algorithm>.
Пример:
vector<int> v = {5, 3, 8, 1, 4};
auto min_it = min_element(v.begin(), v.end()); // min_it указывает на 1
auto max_it = max_element(v.begin(), v.end()); // max_it указывает на 8
cout << *min_it << " " << *max_it; // Вывод: 1 8
📌 count:
Считает количество вхождений элемента в диапазоне. Также лежит в библиотеке <algorithm>.
Пример:
vector<int> arr = {2, 5, 2, 7, 2};
int cnt = count(arr.begin(), arr.end(), 2); // cnt = 3
📌 iota:
Заполняет диапазон последовательными значениями, начиная с заданного числа. Лежит в библиотеке <numeric>. Его удобно использовать, как заполнение тождественной перестановки.
Пример:
vector<int> indices(5);
iota(indices.begin(), indices.end(), 3); // Результат: {3, 4, 5, 6, 7}
📌 next_permutation:
Генерирует следующую лексикографическую перестановку диапазона. Возвращает false, если перестановок больше нет. Следующая перестановка запишется в тот вектор, который вы передаете. Удобнее всего использовать эту функцию для перебора всех перестановок. Лежит в <algorithm>
Пример:
vector<int> arr = {1, 2, 3};
do {
// Перебор всех 6 перестановок в лексиграфическом порядке: 123, 132, 213, ...
} while (next_permutation(arr.begin(), arr.end()));
📌 accumulate:
Суммирует элементы диапазона (или применяет пользовательскую операцию). Первые два аргумента задают диапазон. Третий аргумент изначальное значение суммирование. Последний аргумент опциональный и нужен для пользовательской операции. В примере используется оператор умножение int. Лежит в <numeric>. Обратите внимание на переполнение. Если сумма может переполниться в int, то третий аргумент должен быть типа long long. (0ll)
Пример:
vector<int> v = {1, 2, 3, 4};
int sum = accumulate(v.begin(), v.end(), 0); // Сумма = 10
int product = accumulate(v.begin(), v.end(), 1, multiplies<int>()); // Произведение = 24
📌 lower_bound:
Находит первый элемент в отсортированном диапазоне, который не меньше заданного значения. Если такого нет, то возвращает итератор на конец диапазона. Работает за O(log(n)), где n - длина диапазона. Лежит в <algorithm>.
Пример:
vector<int> v = {1, 2, 4, 5};
auto it = lower_bound(v.begin(), v.end(), 3); // *it = 4
Дорогие друзья! Завтра, некоторых из вас, ждёт первый тур одного из главных событий олимпиадного сезона по олимпиадной информатике - заключительный этап всош.
Шлём вам лучи поддержки и даем главное напутствие: не волнуйтесь, настройте себя на то, чтобы просто прийти и порешать интересные задачи, разработайте перед туром себе чёткий план действий, на любую из ситуаций, в которой вы окажетесь, верно оцените свои силы над каждой из задач, с таким подходом вам будет намного легче, и вы не будете теряться во время тура. Помните, ваша задача выложиться по максимуму и у вас на туре не будет времени на эмоции и разочарования, так что делайте акцент на результат. Вы прошли долгий путь до заключительного этапа, что бы ни случилось, вы большие молодцы!😎
Наша команда будет за всех вас держать кулачки✊ и наблюдать на трансляции за вами!
Шлём вам лучи поддержки и даем главное напутствие: не волнуйтесь, настройте себя на то, чтобы просто прийти и порешать интересные задачи, разработайте перед туром себе чёткий план действий, на любую из ситуаций, в которой вы окажетесь, верно оцените свои силы над каждой из задач, с таким подходом вам будет намного легче, и вы не будете теряться во время тура. Помните, ваша задача выложиться по максимуму и у вас на туре не будет времени на эмоции и разочарования, так что делайте акцент на результат. Вы прошли долгий путь до заключительного этапа, что бы ни случилось, вы большие молодцы!😎
Наша команда будет за всех вас держать кулачки✊ и наблюдать на трансляции за вами!
Скоро будет заключительная олимпиада в сезоне, по информатике, её особенности в том, что там нужно решать NP - задачи с достаточно большими ограничениями, вычисления требуется производить у себя локально. Под такие запросы существуют недетерминированные ("неточные") алгоритмы, позволяющее решать эти задачи довольно быстро, но с точностью отличной от 100%. В олимпиадной пространстве очень популярен отжиг, но помимо него существует кучу других несложных неточек. В этом посте речь пойдёт про генетический алгоритм.
📌 Рациональность
Для начала постараемся изложить рациональность его изучения, где и когда он лучше отжига. Чёткой таблички нет, но при должной реализации, генетика возможно будет лучше работать на графах(например tsp), в группировках(по какому-либо признаку), оптимизации функций.
📌 Как это работает?
Сам алгоритм пришел к нам из природы, в реализацию его мы будем симулировать эволюцию решений (иначе говоря из старых "сильных" решений будем путём их скрещивания получать новоё потомство, возможно дающее даже лучшие результаты).
📌 Этапы
1. Порождение популяции.
Здесь просто создадим некоторое количество ответов случайным образом (можно и не случайным, например заведомо какие-то неправильные жадные решения).
2. Скрещивание
Здесь вам нужно будет придумать алгоритм, который случайным образом скрещивает некоторое количество представителей популяции.
3. Мутация
Этот этап нужен, чтобы не всё зависло от начальной популяции. Выбирается некоторые представители и мутируют (то есть видоизменяется случайным образом)
4. Отбор
На этом этапе вычисляется у каждого представителя нынешней популяции целевую метрику (то есть некий критерий его силы), отбирается процент сильных (как и в любом этапе здесь допустимо любое ваше творчество и можно даже оставлять некоторых слабых представителей, потому что не факт что именно из двух сильных получится главный представитель)
Этот код был написан под задачу (в нём подсчет метрики можно с оптимизировать, но в контексте наших целей это не так важно) - Отожги мирных ферзей!
Вы можете попрактиковаться в реализации на этой задаче, либо на архиве моша прошлых лет.
📌 Рациональность
Для начала постараемся изложить рациональность его изучения, где и когда он лучше отжига. Чёткой таблички нет, но при должной реализации, генетика возможно будет лучше работать на графах(например tsp), в группировках(по какому-либо признаку), оптимизации функций.
📌 Как это работает?
Сам алгоритм пришел к нам из природы, в реализацию его мы будем симулировать эволюцию решений (иначе говоря из старых "сильных" решений будем путём их скрещивания получать новоё потомство, возможно дающее даже лучшие результаты).
📌 Этапы
1. Порождение популяции.
Здесь просто создадим некоторое количество ответов случайным образом (можно и не случайным, например заведомо какие-то неправильные жадные решения).
2. Скрещивание
Здесь вам нужно будет придумать алгоритм, который случайным образом скрещивает некоторое количество представителей популяции.
3. Мутация
Этот этап нужен, чтобы не всё зависло от начальной популяции. Выбирается некоторые представители и мутируют (то есть видоизменяется случайным образом)
4. Отбор
На этом этапе вычисляется у каждого представителя нынешней популяции целевую метрику (то есть некий критерий его силы), отбирается процент сильных (как и в любом этапе здесь допустимо любое ваше творчество и можно даже оставлять некоторых слабых представителей, потому что не факт что именно из двух сильных получится главный представитель)
Пример
реализации:Этот код был написан под задачу (в нём подсчет метрики можно с оптимизировать, но в контексте наших целей это не так важно) - Отожги мирных ферзей!
Вы можете попрактиковаться в реализации на этой задаче, либо на архиве моша прошлых лет.
Сегодня в преддверии МОШ по информатике разберём не очень популярный на школьных олимпиадах эвристический алгоритм - A*.
📌 Применение
Нахождение минимального пути от вершины s до вершины t в графе с неотрицательными рёбрами
📌 Как это работает?
На самом деле это всё тот же алгоритм дейкстры, только теперь мы в куче сортируем вершины по следующему значению (g(v) + h(v), где g(v) - наилучшее расстояние до вершины v от s, h(v) - эвристика, некоторая функция, которая оценивает значение пути от вершины v до t).
📌 Псевдокод
📌 Как выбирать эвристику?
Сначала поговорим о корнер-кейсах алгоритма A*.
1) Eсли выбрать такую h, что ∀ v : h(v)=0, то у нас получится обычный алгоритм дейкстры и очевидно, что при такой эвристике алгоритм работает корректно.
2) Если как-то угадать идеальную эвристику (т. е. ∀ v : h(v) = dist(v, t)), то алгоритм будет работать корректно и более того, он пройдётся лишь по тем вершинам, что лежат на оптимальном пути (если их несколько, то алгоритм точно не будет перебирать заведомо худшие варианты).
Давайте попробуем определить критерий, по которому можно будет отбирать эвристики, назовём эвристику допустимой ∀ v : h(v) <= dist(v, t) (следствие h(t) = 0). (не стоит при выборе метрики отталкиваться исключительно от допустимых метрик, недопустимыми можно добиться большим процентном корректности и при этом ускорить работу алгоритма в разы). Добавим ещё более сильный критерий: эвристика является монотонной если∀(u, v) ∈ E (E - множество рёбер) : h(u) <= h(v) +dist(u, v). Далее можно доказать, что любая монотонная является допустимой. Теперь из этих двух критериев можно сформулировать теорему:
th. Если эвристика h является монотонной, то алгоритм A* найдёт точный оптимальный путь и при этом, каждая вершина будет посещена не более одного раза.
Эта теорема остаётся на упражнение читателю, ждём доказательства в комментариях!
📌 Примеры
А теперь посмотрим примеры эвристик:
1) Нахождение гамильтоново пути, в этой задаче можно для некоторых случаев решать довольно быстро с помощью алгоритма A* (просто будем поддерживать посещённые вершины и последнюю в паре в куче) в качестве эвристики возьмём вес минимального остова на оставшихся вершинах, A* позволит в таком случае оптимизировать количество рассмотренных вариантов путей и соответственно сложность алгоритма.
2) Если граф представляет собой подмножество сетки (степень у каждой вершины <= 4) , то в качестве эвристики можно взять Манхэттенское расстояние: h(v) = |v.x−t.x|+|v.y −t.y| (положим граф на плоскость и возьмём координаты у каждой вершины при вычислении метрики).
3) Если в графе еще можно ходить по диагонали, то в качестве эвристики можно использовать h(v) = max{|v.x−t.x|,|v.y −t.y|}
4) Если у вас задача на плоскости и доступны любые направления, то подойдёт евклидово расстояние h(v) = sqrt((v.x - t.x)^2 + (v.y - t.y)^2)
Одну из задач на этот алгоритм вы можете сдать здесь. А так реализация этого алгоритма простая, всё заключается в правильном подборе эвристики. Всем успехов на олимпиаде и достойного завершения олимпиадного сезона!
📌 Применение
Нахождение минимального пути от вершины s до вершины t в графе с неотрицательными рёбрами
📌 Как это работает?
На самом деле это всё тот же алгоритм дейкстры, только теперь мы в куче сортируем вершины по следующему значению (g(v) + h(v), где g(v) - наилучшее расстояние до вершины v от s, h(v) - эвристика, некоторая функция, которая оценивает значение пути от вершины v до t).
📌 Псевдокод
q.push(start)
while (!q.empty()) {
v = q.top()
q.pop()
for u, cost : graph[v] {
func = dist[v] + cost + heuristic(u)
if (func < f[u]) {
if (u in q) {
// изменим значение функции у вершины u в куче
} else {
// добавим u в кучу
}
}
}
}
📌 Как выбирать эвристику?
Сначала поговорим о корнер-кейсах алгоритма A*.
1) Eсли выбрать такую h, что ∀ v : h(v)=0, то у нас получится обычный алгоритм дейкстры и очевидно, что при такой эвристике алгоритм работает корректно.
2) Если как-то угадать идеальную эвристику (т. е. ∀ v : h(v) = dist(v, t)), то алгоритм будет работать корректно и более того, он пройдётся лишь по тем вершинам, что лежат на оптимальном пути (если их несколько, то алгоритм точно не будет перебирать заведомо худшие варианты).
Давайте попробуем определить критерий, по которому можно будет отбирать эвристики, назовём эвристику допустимой ∀ v : h(v) <= dist(v, t) (следствие h(t) = 0). (не стоит при выборе метрики отталкиваться исключительно от допустимых метрик, недопустимыми можно добиться большим процентном корректности и при этом ускорить работу алгоритма в разы). Добавим ещё более сильный критерий: эвристика является монотонной если∀(u, v) ∈ E (E - множество рёбер) : h(u) <= h(v) +dist(u, v). Далее можно доказать, что любая монотонная является допустимой. Теперь из этих двух критериев можно сформулировать теорему:
th. Если эвристика h является монотонной, то алгоритм A* найдёт точный оптимальный путь и при этом, каждая вершина будет посещена не более одного раза.
Эта теорема остаётся на упражнение читателю, ждём доказательства в комментариях!
📌 Примеры
А теперь посмотрим примеры эвристик:
1) Нахождение гамильтоново пути, в этой задаче можно для некоторых случаев решать довольно быстро с помощью алгоритма A* (просто будем поддерживать посещённые вершины и последнюю в паре в куче) в качестве эвристики возьмём вес минимального остова на оставшихся вершинах, A* позволит в таком случае оптимизировать количество рассмотренных вариантов путей и соответственно сложность алгоритма.
2) Если граф представляет собой подмножество сетки (степень у каждой вершины <= 4) , то в качестве эвристики можно взять Манхэттенское расстояние: h(v) = |v.x−t.x|+|v.y −t.y| (положим граф на плоскость и возьмём координаты у каждой вершины при вычислении метрики).
3) Если в графе еще можно ходить по диагонали, то в качестве эвристики можно использовать h(v) = max{|v.x−t.x|,|v.y −t.y|}
4) Если у вас задача на плоскости и доступны любые направления, то подойдёт евклидово расстояние h(v) = sqrt((v.x - t.x)^2 + (v.y - t.y)^2)
Одну из задач на этот алгоритм вы можете сдать здесь. А так реализация этого алгоритма простая, всё заключается в правильном подборе эвристики. Всем успехов на олимпиаде и достойного завершения олимпиадного сезона!
Свершилось! Поступашки открывают набор на ЕГЭшные курсы по информатике 🎓
Олимпиадный сезон подошёл к концу, поэтому начинаем готовиться к ЕГЭ, чтобы подтевердить дипломы. Мы проанализировали статистику решаемости номеров ЕГЭ по информатике прошлых лет и собрали в курсе самые сложные задачи. В команде курса стобальники ЕГЭ по информатике и опытные олимпиадные тренеры, также студенты МФТИ ФПМИ ПМИ.
🔨 Программа курса
23, 24 задачи
25 задача
26 задача (жадные алгоритмы + дп + префиксные суммы + два указателя)
27 задача
+
доп. лекция по питону🎁
Мы не просто отрешаем все задачи прошлых лет, как делают в большинстве онлайн-школ, а научим вас думать, научим чувствовать задачи и сюжеты, чтобы вы смогли решить даже самый завальный вариант ЕГЭ на сотку! В 26 задаче мы дадим джентельменский набор для решения любой встретившейся задачи на ЕГЭ, а также в течение всего курса будут даны конструктивные задачи для набития руки на программирование.
Начинаем 20 апреля. Будут проходить семинары, на них задачи и подходы к их решению разбирают вместе с вами: на уроке разговаривают с каждым учеником, оценивают его решения + к этому лекции, домашки, разборы и пробники!
📊 По цене курса - 8500 р (получается всего лишь где-то 1500 за один номер, что дешевле, чем у любых репетиторов). Также действует специальное предложение: если ты приведёшь друга, то цена для каждого будет 6000. А если у тебя есть диплом РСОШ, то бери курс за 5000.
📎 Для вопросов и покупок пишем администратору и не тянем с этим: на курсе количество мест ограничено!
Олимпиадный сезон подошёл к концу, поэтому начинаем готовиться к ЕГЭ, чтобы подтевердить дипломы. Мы проанализировали статистику решаемости номеров ЕГЭ по информатике прошлых лет и собрали в курсе самые сложные задачи. В команде курса стобальники ЕГЭ по информатике и опытные олимпиадные тренеры, также студенты МФТИ ФПМИ ПМИ.
23, 24 задачи
25 задача
26 задача (жадные алгоритмы + дп + префиксные суммы + два указателя)
27 задача
+
доп. лекция по питону
Мы не просто отрешаем все задачи прошлых лет, как делают в большинстве онлайн-школ, а научим вас думать, научим чувствовать задачи и сюжеты, чтобы вы смогли решить даже самый завальный вариант ЕГЭ на сотку! В 26 задаче мы дадим джентельменский набор для решения любой встретившейся задачи на ЕГЭ, а также в течение всего курса будут даны конструктивные задачи для набития руки на программирование.
Начинаем 20 апреля. Будут проходить семинары, на них задачи и подходы к их решению разбирают вместе с вами: на уроке разговаривают с каждым учеником, оценивают его решения + к этому лекции, домашки, разборы и пробники!
Please open Telegram to view this post
VIEW IN TELEGRAM
Товарищи, сегодня продолжим говорить про полезные функции в C++, которые можно использовать в олимпиадных задачах. В этот раз остановимся на битовых операциях, которые позволят не только аккуратно реализовать вашу идею, но и значительно ускорить код, так как компилятор оптимизирует эти функции.
Начнем со стандартных функций, задающие стандартные операции над числами в битовом представлении.
📌 & (AND) – побитовое И:
📌 | (OR) – побитовое ИЛИ:
📌 ^ (XOR) – исключающее ИЛИ:
📌 << (LEFT SHIFT) – сдвиг влево (умножение на 2ⁿ):
📌 >> (RIGHT SHIFT) – сдвиг вправо (деление на 2ⁿ нацело):
А теперь рассмотрим функции, которые реализованы не во всех компиляторах и имеют страшные названия, но которые все еще могут оказаться очень полезными.
📌 __builtin_popcount(x) – считает количество единичных битов в числе:
Обратите внимание, что если x 8-ми байтовая переменная, то требуется использовать __builtin_popcountll.
📌 __builtin_clz(x) (Count Leading Zeros) – считает число ведущих нулей:
Также есть метод __builtin_clzll. Для x = 0 результат не определён.
📌 __builtin_ctz(x) (Count Trailing Zeros) – считает число младших нулей:
Не забываем про необходимость использования __builtin_ctzll для больших чисел и для x = 0 результат не определен.
Использование последних функций значительно быстрее чем побитовое вычисление явно в вашей программе.
Рассмотрим следующую тривиальную программу:
Сделаем запуск на codeforces на GNU G++23. Выполнение этой программы заняло 1874 мс.
Поменяем slow_popcount:
Запустим на том же компиляторе на codeforces. И увидим 280 мс.
То есть первая программа почти в 7 раз дольше!
Оффтоп:
Пожалуй, самое известное применение битовых операций было в игре Quake. Где считался обратный корень быстро с помощью них. Подробнее можно почитать об этом здесь.
Начнем со стандартных функций, задающие стандартные операции над числами в битовом представлении.
📌 & (AND) – побитовое И:
int a = 5; // 0101
int b = 3; // 0011
int c = a & b; // 0001
📌 | (OR) – побитовое ИЛИ:
int a = 5; // 0101
int b = 3; // 0011
int c = a & b; // 0001
📌 ^ (XOR) – исключающее ИЛИ:
int a = 5; // 0101
int b = 3; // 0011
int c = a ^ b; // 0110
📌 << (LEFT SHIFT) – сдвиг влево (умножение на 2ⁿ):
int a = 5; // 0101
int b = a << 1; // 1010
📌 >> (RIGHT SHIFT) – сдвиг вправо (деление на 2ⁿ нацело):
int a = 5; // 0101
int b = a >> 1; // 0010
А теперь рассмотрим функции, которые реализованы не во всех компиляторах и имеют страшные названия, но которые все еще могут оказаться очень полезными.
📌 __builtin_popcount(x) – считает количество единичных битов в числе:
int x = 7; // 0111
int ones = __builtin_popcount(x); // 3
Обратите внимание, что если x 8-ми байтовая переменная, то требуется использовать __builtin_popcountll.
📌 __builtin_clz(x) (Count Leading Zeros) – считает число ведущих нулей:
int x = 1 << 30; // 0010...0
int leading_zeros = __builtin_clz(x); // 2
Также есть метод __builtin_clzll. Для x = 0 результат не определён.
📌 __builtin_ctz(x) (Count Trailing Zeros) – считает число младших нулей:
int x = 1 << 3; // 01000
int trailing_zeros = __builtin_ctz(x); // 3
Не забываем про необходимость использования __builtin_ctzll для больших чисел и для x = 0 результат не определен.
Использование последних функций значительно быстрее чем побитовое вычисление явно в вашей программе.
Рассмотрим следующую тривиальную программу:
#include <bits/stdc++.h>
using namespace std;
const int LOG = 30;
int slow_popcount(int x) {
int count = 0;
for (int i = 0; i < LOG; ++i) {
if (x & (1 << i)) {
++count;
}
}
return count;
}
int main() {
int n = 10000;
int sm = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
sm += slow_popcount(i ^ j);
}
}
cout << sm << '\n';
}
Сделаем запуск на codeforces на GNU G++23. Выполнение этой программы заняло 1874 мс.
Поменяем slow_popcount:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 10000;
int sm = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
sm += __builtin_popcount(i ^ j);
}
}
cout << sm << '\n';
}
Запустим на том же компиляторе на codeforces. И увидим 280 мс.
То есть первая программа почти в 7 раз дольше!
Оффтоп:
Пожалуй, самое известное применение битовых операций было в игре Quake. Где считался обратный корень быстро с помощью них. Подробнее можно почитать об этом здесь.
17.txt
10.9 MB
Товарищи, самое время начать готовиться к ЕГЭ по информатике рано, можно и подождать ещё , это один из самых простейших экзаменов, большинство номеров здесь максимально шаблонные и не требует глубоких познаний программирования и информатики. Запускаем серию постов, посвященных номерам ЕГЭ. 17 номер является довольно простым номером, но несмотря на это, успеха в этом номере добиваются лишь 36% абитуриентов. Вам будет предложена задача, затем, через два дня, будет выложен разбор задачи и материалы для подготовки к 17 номеру.
❓ Задача:
В файле содержится последовательность натуральных чисел, каждое число до 10^18, найдите количество таких чисел, что сумма их цифр простая. В ответ выпишите сначала количество таких чисел, а затем сумму цифр таких чисел в троичной системе исчисления.
Эта задачка немного сложнее, чем будет на экзаменах, но как говориться тяжело в учении, легко в бою!
🎁 Первый, кто напишет в комментариях правильный ответ, получит скидку в 10% на курсу ЕГЭ по информатике от поступашек.
🔄 Также у нас upd по курсу, мы решили ввести дополнительную тему по 26 номеру - "бинпоиск". В начале года был слух, что он может там появиться, переходите по ссылочке и смотрите программу.
В файле содержится последовательность натуральных чисел, каждое число до 10^18, найдите количество таких чисел, что сумма их цифр простая. В ответ выпишите сначала количество таких чисел, а затем сумму цифр таких чисел в троичной системе исчисления.
Эта задачка немного сложнее, чем будет на экзаменах, но как говориться тяжело в учении, легко в бою!
Please open Telegram to view this post
VIEW IN TELEGRAM
Товорищи, а вот разбор 17 номера из прошлого поста.
В этой задаче можно было по-разному понять условия (в принципе на самом в ЕГЭ эта ситуация далеко не редкая, к сожалению, на самом экзамене придётся тщательно вникать в условие и гадать, что было на уме у автора). Ниже разберём решение с комментариями на python для следующей трактовки задачи: сначала переведём числа в троичную систему, а затем найдём сумму этих значений.
Желаем успешной подготовки всем!😎 Если хотите готовиться вместе с нами, то уже 23го апреля будет первый семинар на курсе.
В этой задаче можно было по-разному понять условия (в принципе на самом в ЕГЭ эта ситуация далеко не редкая, к сожалению, на самом экзамене придётся тщательно вникать в условие и гадать, что было на уме у автора). Ниже разберём решение с комментариями на python для следующей трактовки задачи: сначала переведём числа в троичную систему, а затем найдём сумму этих значений.
import math # билиотека для корня
def is_prime(n):
"""Проверяет, является ли число n простым."""
if n < 2:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
def sum_digits_in_base(number, base):
"""Считает сумму цифр числа в заданной системе счисления (base)."""
total = 0
while number > 0:
total += number % base
number = number // base
return total
# Чтение чисел из файла (предполагаем, что файл называется 'numbers.txt')
file = open('17.txt', 'r')
numbers = list(map(int, file.read().split()))
count = 0
total_ternary_sum = 0
for num in numbers:
# Сумма цифр в десятичной системе
decimal_sum = sum_digits_in_base(num, 10)
if is_prime(decimal_sum):
count += 1
# Сумма цифр этого числа в троичной системе
ternary_sum = sum_digits_in_base(num, 3)
total_ternary_sum += ternary_sum
print(count, total_ternary_sum)
Желаем успешной подготовки всем!😎 Если хотите готовиться вместе с нами, то уже 23го апреля будет первый семинар на курсе.