Кружок «Олимпиадное программирование»

1. Кружок «Олимпиадное программирование»

Григорьева Анастасия Викторовна
Почта:[email protected]
Сообщения: https://vk.com/id969
Актуальные новости: https://vk.com/olymp_ag
Осень 2017
1

2. О преподавателе

В 2009 г. окончила с отличием мат-мех СПбГУ, в 2016 защитила кандидатскую
диссертацию(к.т.н.)
С 2009 по 2012 преподавала на мат-мехе курсы «Базы данных» и «Практика
программирования»
С 2015 в Академической гимназии им. Д.К. Фаддеева веду факультатив
«Олимпиадное программирование»
В 2017 году трое моих учеников стали призерами олимпиад по информатике из
«Перечня», и поступили без вступительных экзаменов в СПбГУ
С 2017 веду на мат-мехе «Практика программирования» и «Проектирование и
архитектура ПО»
Осень 2017
2

3. Что будет сегодня?

Синтаксис С++
Полезные ссылки
Hello, world
A+B
Немного об автоматическом тестировании
Разнообразные задачи
Осень 2017
3

4. Почему С++?

Когда попадаешь на заключительный этап
Всероссийской олимпиады школьников,
почему-то оказывается, что 95%
участников используют именно С++
Осень 2017
4

5. Краткий синтаксис С++

Тут собраны самые распространенные
операторы для начанающих:
https://docs.google.com/document/d/1fB68A
chuPRgxv2kd39e_r3YIiRfMpyc0YFR4ZqKDEZM
/edit?usp=sharing
Осень 2017
5

6. А именно…

Осень 2017
6

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

Сдавать задачи:
http://informatics.mccme.ru/
Зарегистрируйтесь там под настоящим именем
Он-лайн компилятор:
https://ideone.com/
Есть и другие. Этот кажется мне наиболее удобным
Осень 2017
7

8. Hello, world

Зайдите на https://ideone.com/
Выберите там С++
Осень 2017
8

9. Hello, world

Напишите код
Запустите
Осень 2017
9

10.

Если что-то забыли написать или
опечатались, компилятор вам подскажет
тут:
В данном случае мы забыли поставить
точку с запятой.
Ставим, запускаем снова.
Осень 2017
10

11. А+В

Теперь напишите самостоятельно
программу, принимающую на вход 2
целых числа (int a, b) и выводящую их
сумму
На вход скармливать числа тут:
Осень 2017
11

12. Автоматическое тестирование

Осень 2017
12

13. Плюсы

Беспристрастность
Ваше решение будет полноценно
проверено
Получить «полный балл» с первой
попытки приятно
Скорость проверки
Осень 2017
13

14. Группы тестов

Тесты минимальной размерности
(тривиальные)
Тесты на частные случаи
На точность вещественных вычислений
Выявляющие особенности использования
конкретных систем программирования
Общие тесты (случайные)
Тесты максимальной размерности
Осень 2017
14

15. Примечание

правильное , но неэффективное решение,
должно набирать ориентировочно 30-70%
баллов.
Если в условии задачи выделены
отдельные подзадачи, то баллы
начисляются только тогда, когда все
тесты для этой подзадачи успешно
завершились
Источник: Кирюхин В.М.
Осень 2017
15

16. Темы задач

комбинаторика
сортировка и поиск
обработка последовательностей
перебор вариантов и методы его
сокращения
алгоритмы на графах
динамическое программирование
элементы вычислительной геометрии
задачи на технику программирования
задачи на идею
Осень 2017
16

17. Задачи

Осень 2017
17

18. № 2837. Сокращаем перемены

Требуется подсчитать, на сколько раньше
будет заканчиваться k-й урок, если все
перемены сократить на 5 минут.
Входные данные
Вводится одно натуральное число k, не превосходящее 7.
Выходные данные
Вывести одно натуральное число — время в минутах.
Осень 2017
18

19. Где найти задачу по №

Осень 2017
19

20. № 2841. Наибольшее четное число

Вводятся три цифры. Требуется составить
из них наибольшее возможное четное
число.
Входные данные
Вводятся три цифры, разделенные пробелом.
Гарантируется, что хотя бы одна из них отлична
от нуля и хотя бы одна цифра четная.
Выходные данные
Вывести одно трехзначное число (без пробелов).
Число не может начинаться с нуля.
Осень 2017
20

21. Примечание

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

22. № 1083. Лифт

Чтобы поднять на N-й этаж M-этажного дома новый
холодильник, Витя вызвал бригаду грузчиков. Оплата работы
грузчиков производится так: за подъем холодильника на
один этаж требуется заплатить 200 рублей, за спуск на один
этаж — 100 рублей. За подъем и спуск на лифте плата не
взимается. Несмотря на то, что в Витином доме есть лифт,
ему возможно все же придется заплатить грузчикам,
поскольку лифт останавливается только на каждом K-м
этаже, начиная с первого (то есть на этажах с номерами 1,
K+1, 2K+1, 3K+1, …). Требуется вычислить, какой
минимальной суммы денег достаточно, чтобы грузчики
доставили холодильник с первого этажа на N-й.
Осень 2017
22

23. № 1083. Лифт

Формат входных данных
Во входном файле записаны три числа: M (2≤M≤100), N
(2≤N≤M) и K (2≤K≤M–1), разделенные пробелами.
Формат выходных данных
В выходной файл выведите одно число — минимальную
стоимость подъема холодильника.
Осень 2017
23

24. Литература

http://algolist.ru/olimp/sor_prb.php
«Московские олимпиады по информатике 2002-2009» Е.В.
Андреевой, В.М.Гуровица, В.А.Матюхина, Москва, 2009
«Методика проведения и подготовки к участию в
олимпиадах по информатике» В.М. Кирюхин, Москва, 2011
https://sites.google.com/site/kssmoks/home/planpraktikuma-po-kursu-algoritmy-i-struktury-dannyh/rekursia
Осень 2017
24