Требуется написать программу, которая позволит решить эту сложную задачу.
Формат входных данных
Ввод состоит из одного или нескольких наборов тестовых данных, каждый из которых, в свою очередь, состоит из двух строк. В первой строке каждого набора содержится два целых числа NиK≤N(1≤K≤N≤ 50 000) —соответственно длина последовательности и количество подпоследовательностей.
Во второй строке набора входных данных записаны N целых чисел ai
(–1 000 000 000 ≤ ai ≤ 1 000 000 000).
Ввод завершается двумя нулями на месте значений N и К.
Гарантируется, что сумма значений N по всем тестовым наборам не превосходит 50 000.
Формат выходных данных
Выходные данные для каждого тестового набора должны содержать К строчек, i-я из которых содержит номера чисел i-ой подпоследовательности в порядке возрастания. Гарантируется, что ответ всегда существует. Если оптимальных ответов несколько, разрешается выводить любой из них. Вывод для различных тестовых наборов разделяется одной пустой строкой.
Пример
|
Система оценки
Решения, работающие при N, К, Σ N ≤ 5 000, будут оцениваться из 60 баллов.
Задача D. Пересекающиеся провода
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мебибайт
Танкист для питания танка использует квантовую систему преобразования энергии, питающую двигатель. В преобразователе у танкиста есть п контактов, расположенных по окружности в вершинах правильного n-угольника. Периодически танкист соединяет какие-то контакты из них проводами. Тем не менее, каким образом работает эта система, танкист не знает, потому решил промоделировать работу квантового преобразователя на бортовом компьютере.
Танкист знает, что мощность, выдаваемая преобразователем, напрямую зависит от числа пар пересекающихся проводов, причем провода считаются пересекающимися, только если они пересекаются в какой-либо внутренней своей точке. Кот решил упростить себе задачу и использует только прямые отрезки проводов для соединения контактов. Вам же требуется после каждой операции, производимой Котом, выяснять, сколько пар контактов пересекается в преобразователе. Если несколько пар контактов пересекаются в одной и той же точке, каждое из таких пересечений считается отдельно. Например, три провода, пересекающиеся в одной точке, создают три пересечения.
Формат входных данных
В первой строке ввода находятся два числа пит — количество контактов внутри преобразователя и количество выполняемых операций (1 ≤ п, т ≤ 50 000). Далее следует т строк — описания самих операций, выполненных танкистом. Строка «ADD X Y» обозначает соединение контакта X и контакта Y прямым отрезком провода, а строка «DELETE X Y» — удаление отрезка провода, соединяющего контакты X и Y (1 ≤ X, Y ≤ п). Гарантируется, что удаляемый отрезок провода будет сначала добавлен, а также никакие два контакта не будут соединены двумя проводами сразу и никакой контакт не будет соединен сам с собой.
Формат выходных данных
Выведите т строк, по одному числу в каждой — количество пар пересекающихся проводов после каждой операции танкиста.
Пример
|
Система оценки
Решения, работающие при п, т ≤ 100, будут оцениваться из 40 баллов. Решения, работающие при п, т ≤ 2000, будут оцениваться из 60 баллов.
9. Описание заданий для девятого интернет-тура
На девятом туре было предложено 4 задачи: задача A «Карточки», задача B «Игра «Пни монстров»», задача C «Принцесса и принц» и задача D «Простыни». Тексты задач представлены ниже.
Карточки
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мебибайт
На день рождения Вася подарил своему брату Пете набор из N карточек. Затем Вася и Петя написали по одному числу на каждой карточке: Вася с одной стороны карточки, а Петя — с другой. После этого братья разбросали карточки по комнате и убежали. Все это безобразие увидела их бабушка, Людмила Петровна. Она много лет работала бухгалтером, поэтому она решила вспомнить молодость и придумала игру: нужно некоторые карточки перевернуть стороной с записью Васи, а некоторые – с записью Пети, причем так, чтобы сумма чисел на них была максимально возможной.
Так как бабушка любит обоих внуков одинаково сильно, она добавила дополнительное условие: количество карточек, перевернутых стороной с записью Пети, должно отличаться от количества карточек, перевернутых стороной с записью Васи, не более чем на К.
Требуется написать программу, которая решает поставленную задачу.
Формат входных данных
В первой строке содержатся числа N и К (1 ≤ N ≤ 100 000,1 ≤ К ≤ N) —количество карточек. Далее в N строках содержатся описания карточек — на каждой строке два целых числа: первое число написано Васей на одной стороне карточки, второе написано Петей на другой стороне. Вася и Петя не знают чисел, которые по модулю превосходят 109.
Формат выходных данных
В первой строке выходного файла должно содержаться одно число — максимально возможная сумма. В следующей строке должны быть размещены N чисел — для каждой карточки это может быть либо 1, если она лежит Петиной стороной, и 0 – если она лежит Васиной стороной.
Примеры
Подзадача 1
Дополнительные упрощения: N ≤ 10.
Решение оценивается в 25 баллов.
Подзадача 2
Дополнительные упрощения: N ≤ 200.
Решение оценивается в 25 баллов.
Подзадача 3
Дополнительные упрощения: N ≤ 3000.
Решение оценивается в 25 баллов.
Подзадача 4
Дополнительные упрощения отсутствуют.
Решение оценивается в 25 баллов.
Игра «Пни монстров»
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мебибайт
Обучающий уровень компьютерной игры «Пни монстров» имеет крайне простой сценарий. Игроку, имеющему силу N, последовательно встречаются монстры силой 1, 2, 3 и так далее. Если текущая сила игрока не меньше силы монстра i, игрок устраняет его, однако и сам теряет i единиц силы. Иначе монстр считает игрока слишком слабым соперником и присоединяется к нему, увеличивая силу игрока на i.
Требуется написать программу, которая определяет силу игрока после К уровней.
Формат входных данных
В единственной строке входных данных записано два целых числа N и К
(1 ≤ N, К ≤ 10111) — исходная сила игрока и количество уровней, соответственно.
Формат выходных данных
Выведите единственное целое число — силу игрока после К уровней.
Подзадача 1
Дополнительное ограничение: N, K ≤ 108.
Решение этой подзадачи оценивается в 25 баллов.
Подзадача 2
Дополнительное ограничение: N, K ≤ 1011.
Решение этой подзадачи оценивается в 25 баллов.
Подзадача 3
Дополнительное ограничение: N, K ≤ 1018.
Решение этой подзадачи оценивается в 25 баллов.
Подзадача 4
Дополнительные ограничения отсутствуют.
Решение этой подзадачи оценивается в 25 баллов.
Пример
Принцесса и принц
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мебибайт
Принцесса и принц ходят по замку в поисках друг друга. Чтобы никто не заметил их перемещений, они ходят только по тем комнатам, в которых не горит свет. Всего в замке п комнат, из каждой есть односторонний переход ровно в одну (возможно, в ту же самую) и не существует двух комнат, из которых переход есть в одну и ту же комнату. При этом иногда по комнатам проходят слуги, гасят свет там, где он был зажжён, и зажигают там, где было темно. Известно, где горит свет изначально, а также в какие моменты времени и между какими комнатами будут проходить слуги.
Требуется написать программу, позволяющую определять, смогут ли принцесса и принц встретиться в заданный момент времени, если они находятся в заданных комнатах, и какое минимальное число переходов из комнаты в комнату нужно им в сумме пройти для этого.
Формат входных данных
В первой строке ввода заданы числа пик — число комнат в замке и количество запросов (1 ≤ п, к ≤ 100 000).
Во второй строке записано п чисел: для каждой комнаты число 0, если там темно, и число 1, если там горит свет.
В третьей строке записано п различных целых чисел от 1 до п — для каждой комнаты номер комнаты, в которую ведёт переход из неё.
В последующих к строках записаны запросы. Каждый запрос состоит из трёх целых чисел а, b и с. Если а = 0, то это значит, что слуги прошли из комнаты b в комнату с, изменив на своём пути освещённость всех комнат, включая b и с. Гарантируется, что у слуг есть возможность пройти этот путь. Если же a = 1, то нужно проверить, может ли принцесса встретиться с принцем, если она находится в комнате b, а он — в c.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 |
