Структуры данных

Несложная классическая задача на структуры данных, которая усложнена форматом входных данных. Читаем условие: Итак, первая сложность в этой задаче - как считать данные? Действительно, нет классического N - количества строк. А это значит, что надо считывать все строки до конца. Построчное считывание в Python можно организовать через следующую конструкцию: Такой цикл считает весь входной файл и сам разделит его на строки. Единственная особенность - в строках l будут находиться и символы переноса строки, поэтому при их обходе надо делать l...

Задача на структуры данных, которую можно решить каким-нибудь из деревьев или sqrt-декомпозицией. Я же хочу показать ещё один вариант sqrt-декомпозиции (как метода, а не структуры данных). Давайте читать условие: Простое решение заключается в том, чтобы каждый раз перестраивать индекс. Такое точно не пройдёт по времени. Идея sqrt-декомпозиции заключается в том, чтобы перестраивать индекс лишь каждые N шагов. А между перестройками хранить историю изменений и получать ответ, просматривая и индекс, и накопленную историю...

Несложная задача на структуры данных, но с некоторыми подводными камнями, которые могут помочь избегать ошибок в будущем. Читаем условие: Уже из приведённого примера следует, что надо складывать два самых маленьких числа. Это же следует и из логики: если большое число участвует в нескольких операциях сложения, то в каждой из них за это число надо будет заплатить. То есть надо стараться чаще использовать маленькие числа (ведь количество операций сложения всегда будет равно N - 1). Отсюда получаем,...

Осталась одна задача первого тура регионального этапа Всероссийской олимпиады школьников по информатике 2009 года, которая ещё не разобрана на этом канале. Давайте закроем и её: Довольно серьёзная сложность, приличные входные данные и интересная история. Первое, что необходимо понять, это как среди двух человек выбрать того, кто будет сидеть. Представим двух пассажиров Alice и Bob. Выгодно, чтобы Alice сидела, если выполняется следующее неравенство: С таким условием работать неудобно, потому что придётся сравнивать всех пассажиров попарно...

Эта задача на сайте acmp.ru с самого начала его существования, но четыре года назад были добавлены тесты (по сути, один особый случай), и почти все решения получили Wrong answer. Давайте разбираться. Важным моментом является то, что нам гарантируют, что положение прямоугольников можно однозначно определить. Это означает, что у каждого прямоугольника виден кусочек каждой из его сторон. Ведь если полностью покрыть какую-нибудь сторону, то не будет понятно, где именно она проходит. Таким образом получаем,...