Мастер-класс
"Решение олимпиадных задач
по программированию"
Осенняя сессия "Шаг в профессию"
Для школьников задача #1 - хорошо сдать ЕГЭ и стать победителями или призерами в олимпиадах, дающих льготы при поступлении в вузы.
Список по информатике доступен на многих ресурсах:
Каждая олимпиада имеет определённый уровень: первый, второй или третий. Уровни олимпиад фиксируются в Перечне. Чем выше уровень олимпиады, тем более весомые льготы имеют её победители и призёры. Уровень, которым обладает та или иная олимпиада, не связан напрямую со сложностью её выигрывания (а с чем именно связан — дело тонкое) и может меняться от года к году.
Льготы, предоставляемые вузами, бывают трёх видов:
Например,
Организаторы : МФТИ, mail.ru GROUP, МГТУ им. Н.Э.Баумана
1 | СПб, ФМЛ 239 + ФТШ + ЮМШ: Команда кулинарного техникума |
2 | Челябинск, Лицей 31: Морс из 182 ягодок брусники |
3 | СПб, ФМЛ 239: Фанаты Вадимыча |
9-10 декабря 2017 года состоялась Восемнадцатая ВКОШП
5 сентября стали известны результаты 29-й Международной олимпиады по информатике (International Olympiad in Informatics – IOI), которая проходила в Цукубе (Япония). Российская сборная в составе 4-х человек завоевала две золотые и две серебряные медали. Всего за призовые места на IOI-2018 состязались более 900 школьников из 85 стран мира.
Руководителем сборной выступил А. В. Малеев, проректор по международным программам и технологическому предпринимательству Московского физико-технического института. Главными тренерами сборной стали М. Тихомиров и А. Станкевич.
https://olympic.nsu.ru/ - 1 уровень
Всесибирская открытая олимпиада в 2017 году вошла в перечень международных олимпиад школьников, утвержденных Распоряжением Министерства образования и науки Российской Федерации, иностранным призерам и победителям которых были выделены 500 мест для обучения в вузах Российской Федерации.
https://olympiads.ru/zaoch - 1 уровень
Центр педагогического мастерства, Московский центр непрерывного математического образования, Московский физико-технический институт, Московский государственный университет им.М.В.Ломоносова,
https://olymp.innopolis.ru/ooui/
МГУ им. Ломоносова
http://neerc.ifmo.ru/school/ioip/index.html
Чтобы победить, надо тренироваться
ДАЕТ ВОЗМОЖНОСТИ:
Codeforces Round #519 by Botan Investments | 02:00 | До начала 31:33:31 | До регистрации 07:33:31 | ||
Lyft Level 5 Challenge 2018 - Final Round | | 02:00 | До начала 8 дней | До регистрации 7 дней | |
Mail.Ru Cup 2018 Раунд 2 | | 02:30 | До начала 2 недели | До регистрации 13 дней | |
Codeforces Round #520 (div. 2) | | 02:00 | До начала 3 недели | До регистрации 2 недели | |
Технокубок 2019 - Ознакомительный Раунд 3 | | 2:00:00 | До начала 3 недели | До регистрации 3 недели | |
Технокубок 2019 - Отборочный Раунд 3 | | 02:00 | До начала 3 недели | До регистрации 3 недели | |
Codeforces Round #TBA (div. 2) | | 02:00 | До начала 4 недели | До регистрации 4 недели | |
Mail.Ru Cup 2018 Раунд 3 | | 02:30 | До начала 4 недели | До регистрации 4 недели |
ПОДДЕРЖИВАЕТ
и даже подготовку к ЕГЭ!
Также организаторы сайта запустили 4 (бесплатных) онлайн-курса олимпиадной подготовки по информатике разного уровня: с видеолекциями каждую неделю, задачами в тестирующей системе и ежемесячными живыми вебинарами с разборами задач и ответами на вопросы. Присоединяйтесь! https://letovo.ru/personal/enrollee/onlain-kruzhok-po-informatike/
Совмещение отдыха и учебы
Существуют летние и зимние школы программирования. Самая известная, конечно, ЛКШ - летняя компьютерная школа для школьников до 10 класса включительно https://lksh.ru/ .
Школы, как правило, платные и при этом есть конкурс желающих.
Подсуетитесь - набор в самые популярные школы
заканчивается уже в мае.
Список для школьников https://rb.ru/longread/summer-camps/
Актуально! Зимняя компьютерная школа МФТИ . С 2019 года проект
будет называться Moscow Workshops Juniors. Это тренировочные сборы по
программированию, на которых старшеклассники пройдут усиленную подготовку к
национальным олимпиадам с 25 февраля по 6 марта 2019 года.
Онлайн-компиляторы
Интересные ресурсы
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ.
Образовательные платформы
По математике:
Математика для олимпиад по программированию
https://stepik.org/course/4603/
1. Комбинаторика 2. Теория чисел 3. Геометрия 4. Инварианты и полуинварианты 5. Теория игр
Чемпионат в СГУ
проходит в вычислительных лабораториях 1 корпуса и собирает участников из школ, лицеев, гимназий и, конечно, из университета.
Детали в блоге: http://nkpopova.blogspot.ru.
В этом году в рамках проекта
«Развитие сетевого взаимодействия в области математики, физики, информатики и робототехники между образовательными организациями финно-угорских республик Российской Федерации»
был проведен интернет-тур.
Студенческий чемпионат мира известен также как студенческая командная олимпиада по программированию.
В английском языке принято сокращение ACM/ICPC или просто ICPC.
Официальный сайт чемпионата https://icpc.baylor.edu/
Официальный сайт https://icpc.baylor.edu/
А после школы?..
46381 студентов
со всего мира боролись за право попасть на финальные соревнования,
прошедшие в Южной Дакоте в 2017 году.
Официальный сайт https://icpc.baylor.edu/
133 команды пробились в финал
Чемпионат мира по программированию: что, где, когда?
Этапы сезона 2018-2019 для Уральского подрегиона:
https://icpc.baylor.edu/regionals/finder/Urals-Regional-2018
Квалификация,
регионы, 6 октября 2018
Полуфинал,
(1-2 декабря 2018, г. Санкт-Петербург )
Финал,
(31 марта - 5 апреля 2019, Порту)
Четверть финал,
(27 октября 2018, Екатеринбург)
Четвертьфинал мира по программированию
Уже четыре года Уральский федеральный университет проводит отбор на четвертьфинал мира по программированию на площадках вузов. В том числе и на нашей площадке. О том, как это происходит, смотрите в блоге http://nkpopova.blogspot.ru. И планируйте свое участие следующей осенью.
Четвертьфинал мира по программированию
27 октября проходят несколько отборочных четвертьфинальных туров Северного Евразийского региона сезона 2018/19. Свой шаг к финалу ICPC2019 в Порту уже сделали команды Московского и Южного подрегионов, сегодня же мы узнаем, с кем из Северного, Уральского, Казахстанского, Азербайджанского, Армянского, Грузинского и Таврического подрегионов они поборются в полуфинале.
Наша команда (Syktyvkar SU: Brothers (Durkin, Ichshuk, Vanuta):
В. Ищук, А. Дуркин, В. Лапшин
на фото: В. Ищук, А. Дуркин
Наивысшее достижение студентов СГУ – диплом третьей степени на полуфинале 2004 года. Команду DWED составили Ключников Евгений, Спеськов Александр и Попов Дмитрий. Запасным в команде был Шеринга Александр. В центре - Владимир Леонидович Никитенков - душа и организатор Открытого чемпионата СГУ по программированию.
Попов Д., Спеськов А., Никитенков В.Л., Шеринга А., Ключников Е.
Удачи на соревнованиях!
Чемпионом 2018 г. в Пекине стала команда МГУ им. Ломоносова
Сортировка и поиск
Темы:
Сортировка и поиск в массиве с n элементами
n<=10000
Квадратичная сортировка (например, пузырьком)
Линейный поиск в массиве
for (i = 0; i <= n – 1; i++)
if (a[i]==x) {
index = i;
break;
}
for (i = 0; i <= n - 2; i++)
for (j = 0; j <= n - i - 2; j++)
if (a[j] > a[j + 1])
swap(a[j], a[j + 1]);
Сортировка и поиск в массиве с n элементами
#include <algorithm>
using namespace std;
int A[100000];
int main(){
cin >> n; cin >> val;
...
sort(A, A + n);
bool result = binary_search(A, A+n, val);
int index = lower_bound(A, A+n, val)-A;
…
}
n >=100000
Сортировка подсчетом
Пример. Пусть имеется последовательность неотрицательных целых чисел, каждое из которых не больше 10. Подсчитать, сколько раз встретилось каждое.
int s[11] ;
int main(){
int x;
while (cin >> x)
{
s[x]++;
}
for (int i = 0; i <= 10; i++)
cout << i << ” “ << s[i] << “\n”;
}
Двоичный поиск по ответу
Пусть в задаче необходимо выдать минимальное (целое) число, удовлетворяющее заданным условиям. Чтобы найти это минимальное число, можно применить двоичный поиск по ответу, а именно определить верхнюю и нижнюю границы left, right , между которыми будет находиться ответ. Тогда чтобы найти ответ на задачу, нужно делить диапазон [left, right], в котором находится ответ, напополам, и если middle=(left+right)/2 удовлетворяет заданным условиям, то ответ на задачу будет находиться в левой половине [left, middle], иначе ответ на задачу находится в правой половине [middle+1, right]. Деление диапазона происходит до тех пор, пока диапазон является непустым.
left=…
right=…
while (left < right){
middle = (left+right)/2;
if (middle удовлетворяет условиям задачи)
right=middle;
else left=middle+1;
}
cout << left;
Примеры. Задачи на сортировку и поиск informatics
Задача №3207. Чемпионат по стрельбе
Задача №1209. Клавиатура
Задача №4. Двоичный поиск
Задача №3161. Шеренга
Задача №112041. Кондиционеры
Задача №490. Очень Легкая Задача
Задача №1923. Дипломы
Мастер-класс
"Решение олимпиадных задач
по программированию"