Программирование
Преподаватель: Денис Павлович Кириенко.
Описание
Для выбравших спецкурс к двум школьным урокам информатики добавляется два часа специальности, и будет 4 урока информатики по отдельной программе.
Примерное содержание программы:
- Программирование на языке C++.
- Алгоритмы – двоичный поиск, динамическое программирование, перебор, комбинаторика, Meet-in-the-middle.
- Обработка данных – словари, csv, электронные таблицы.
- Прикладное программирование – работа с файловой системой, обработка изображений, боты для telegram, разработка GUI.
Для решения некоторых задач нужно будет использовать язык Python, т.е. иногда будут использоваться языки C++ и Python.
В основном можно ориентироваться на программу специализации в прошлые годы.
Для учащихся, не выбравших специальность "Программирование", будет два урока информатики в неделю, будет использоваться язык Python.
Правила отбора
Отбор состоит из двух туров – квалификационном и отборочном.
Квалификационный раунд проходит с 1 по 11 сентября. В квалификационном раунде вам нужно решить не менее 10 задачи из 15.
Отборочный раунд будет проходить в школе очно, в пятницу, 12 сентября, после 15:00.
И в квалификационном, и в отборочном раунде запрещено использовать нейросети для решения задач и сдавать чужие решения.
Требования к решениям задач квалификационного и отборочного раунда
В данных задачах вам как правило необходимо обработать последовательность из \(n\) целых чисел. Типичные ограничения для задач будут такие – \(n\le 10^6\), ограничение по времени 2-3 секунды, ограничение по памяти – 11 мегабайт. Эти ограничения означают, что вам необходимо написать решение сложности \(O(n)\), но вы не сможете сохранить все входные данные в массиве или иной структуре данных. Иными словами, решение должно использовать \(O(1)\) памяти: вы можете создавать переменные, массивы небольшого размера, не зависящего от \(n\).
В отдельных задачах ограничения могут отличаться, в некоторых задачах вам можно сохранять часть входных данных (но не все) в массиве.
Если ваше решение попробует использовать более 11 мегабайт памяти, вы получите вердикт "Ошибка выполнения" на тесте. Такие тесты (с большим значением \(n\)) должны идти в конце.
Поскольку размер входных данных будет довольно велик, вам нельзя использовать функцию input() для считывания данных, так как она работает медленно. Вместо неё необходимо использовать более быструю функцию sys.stdin.readline(), которая делает примерно то же самое, но гораздо быстрее. Для использования этой функции вам необходимо подключить модуль sys.
Если вы попробуете использовать функцию input() в решении, вы получите вердикт "Нарушение правил оформления программ", т.к. функция input() внесена в стоп-лист в этом контесте.
В начале контеста идёт нулевая задача, в которой нужно посчитать сумму \(n\) чисел. В этой задаче два теста – первый тест из условия, а во втором тесте \(n=10^6\). Вы можете использовать эту задачу для изучения поведения тестирующей системы в таких ограничениях. Вот пример правильного решения первой задачи:
import sys s = 0 n = int(sys.stdin.readline()) for i in range(n): s += int(sys.stdin.readline()) print(s)
В случае, если решения не будут соответствовать ожидаемому, могут быть добавлены тесты, изменены ограничения и проведено перетестирование всех решений.
Вход в контест квалификационного раунда
Учащихся школы используют свои школьные логины и пароли для входа в тестирующую систему.