Олимпиадные задачи по информатике для 10 класса
В десятом классе задача перестаёт решаться прямым перебором: её нужно свести к приёму, который считает ответ за один или два прохода по данным. Ниже двенадцать задач нашего банка третьего уровня сложности — префиксные суммы, два указателя, сортировка с обменным рассуждением и разбор интервалов. Ни одна из них не повторяет список девятого класса, и дело не только в другом наборе задач: здесь наивное решение уже не укладывается в ограничение по времени.
Начать можно прямо с первой — Маршруты с круглой суммой: условие, окно для кода и проверка на тестах на одной странице.
Двенадцать задач для 10 класса
Темы: префиксные суммы, два указателя, сортировка с обменным рассуждением, интервалы и расписание. Сложность — третий уровень сложности; порядок от простой к сложной.
- Маршруты с круглой суммой
В городе Ровномайске вдоль одной длинной улицы стоят датчики. Каждый датчик за день собрал некоторое число «единиц шума».
- Самая короткая «сытая» серия перекусов
После школы ты заходишь в магазин несколько раз подряд. В i-й заход ты покупаешь перекусы на сумму a i.
- Очередь в столовой и «хаос»
В школьной столовой стоят в очереди с подносами. Каждый хочет, чтобы впереди были только те, кто пришёл раньше с меньшим номером талона. Но очередь уже перемешалась.
- Сколько аудиторий нужно кружкам
В школе в один день проходит много занятий кружков. Для каждого занятия известно время начала и время конца в минутах от 0 до 1 000 000.
- Лучшая серия по среднему баллу
В электронном дневнике за каждый день стоит число — сколько баллов вы набрали в школьной игре.
- Совпали по шагам
В школьном чате ребята сравнивают, сколько шагов за день показал их браслет.
- Парные рейсы: минимизировать худший перегруз
В городе после фестиваля нужно развезти жителей по районам. Для каждого из 2n районов известен прогноз пассажиропотока целое число.
- Стрелы по шарам
В игре на фестивале по всей карте висят магические шары.
- Самый короткий маршрут с точным бюджетом
В городе Нумероград дежурный дрон летит вдоль одной прямой улицы, где подряд стоят n кварталов.
- Тихая улица по датчикам
В городе вдоль одной длинной улицы стоят датчики шума — по одному на каждый квартал.
- Баланс по чекам
После походов в магазин у тебя есть список дневных изменений баланса: где-то деньги потратил отрицательное число, где-то вернули сдачу или пришёл кэшбэк положительное…
- Тройной перекус
В школьном буфете есть n видов перекусов. У каждого вида есть «вес» например, калории.
А дальше
Готовиться к туру по шагам — подготовка к школьному этапу, 9–11 класс. Начать с нуля, если программирования ещё не было, — «С нуля до олимпиады». Весь банк — каталог задач, соседние классы — 7 класс, 8 класс, 9 класс, 11 класс.
Частые вопросы
Какие задачи дают на олимпиаде по информатике в 10 классе?
В десятом классе задача перестаёт решаться прямым перебором: её нужно свести к приёму, который считает ответ за один или два прохода по данным. Ниже двенадцать задач нашего банка третьего уровня сложности — префиксные суммы, два указателя, сортировка с обменным рассуждением и разбор интервалов. Ни одна из них не повторяет список девятого класса, и дело не только в другом наборе задач: здесь наивное решение уже не укладывается в ограничение по времени. Все двенадцать задач списка открыты и решаются в браузере.
Нужны ли готовые ответы?
Ответ здесь засчитывается запуском решения на скрытых тестах, поэтому список правильных ответов ничего не даёт: проверяется программа, а не переписанный итог.
На каком языке решать?
Python 3, и мы даём только его. На третьем уровне сложности ограничение по времени уже чувствуется, поэтому решение приходится писать без лишних проходов по данным: считывать ввод целиком, а не по одной строке, и не собирать строки сложением в цикле. Все двенадцать задач списка проходят на Python в пределах ограничения.