Преподаватель: Денис Павлович Кириенко

Описание

Для выбравших специальность к двум школьным урокам информатики добавляется два часа специальности, и будет 4 урока информатики по отдельной программе.

Примерное содержание программы:

1. Программирование на языке C++.
2. Алгоритмы – двоичный поиск, динамическое программирование.
3. Обработка данных – словари, csv, электронные таблицы.

Для решения некоторых задач нужно будет использовать язык Python, т.е. иногда будут использоваться языки C++ и Python.

В основном можно ориентироваться на программу специализации в прошедшем учебном году?.

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

Правила отбора

Отбор на специализацию проводится по результатам контеста, который будет проходить с 2 сентября по 8 сентября, окончание контеста в 18:00. На контесте будет 21 задача по обычным правилам приёма задач (решение должно пройти все тесты, после автоматической проверки решение получает статус "Принято на проверку", затем проверяется преподавателем).

Задачи нужно будет решать на языке Python. Отбор – конкурсный, по результатам контеста будет отобрано необходимое количество учащихся, таблица результатов при этом не будет доступна, нужно показать всё, на что вы способны. Все задания должны быть выполнены самостоятельно.

Требования к решениям

В данных задачах вам как правило необходимо обработать последовательность из \(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)

В случае, если решения не будут соответствовать ожидаемому, могут быть добавлены тесты, изменены ограничения и проведено перетестирование всех решений.

Вход в контест

Учащихся школы используют свои школьные логины и пароли для входа в тестирующую систему.

Ура, я всё прочитал и хочу решать задачи!