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