--->
39 задач
<---
Источники
#1207
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Региональный этап,
2009,
1 день,
Задача C
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
С окраины в центр города каждое утро по одному маршруту едут в трамвае N человек. За долгое время поездок они достаточно хорошо узнали друг друга. Чтобы никому не было обидно, они захотели решить, кто из них и между какими остановками маршрута должен сидеть, а кто должен стоять. Все остановки пронумерованы от 1 до P.
Один из пассажиров оказался знатоком теории математического моделирования. Он предложил рассмотреть значение суммарного удовлетворения пассажиров. Для каждого i-го пассажира он оценил две величины — ai и bi. Если в течение одного переезда между остановками пассажир сидит, то к суммарному удовлетворению прибавляется ai, если же он стоит, то прибавляется bi.
Всего в трамвае M сидячих мест. Вставать и садиться пассажиры могут мгновенно на любой остановке. Кроме того, некоторые пассажиры предпочитают ехать стоя, даже если в трамвае есть свободные места (для них ai < bi).
Требуется написать программу, которая вычисляет значение максимально достижимого суммарного удовлетворения, если для каждого i-го пассажира известны величины ai и bi, а также номера остановок, на которых он садится и выходит из трамвая.
Входные данные
Первая строка входного файла содержит разделенные пробелом три целых числа N, M и P — число пассажиров, число сидячих мест и число остановок на маршруте соответственно (1 ≤ N, M, P ≤ 100 000; 2 ≤ P).
Каждая из следующих N строк содержит информацию об очередном пассажире в виде четырех целых чисел ai, bi, ci, di:, где первые два числа определяют вклад в параметр счастья, третье – номер остановки, на которой пассажир садится в трамвай, и последнее – номер остановки, на которой он выходит из трамвая (−106 ≤ ai, bi ≤ 106; 1 ≤ ci < di ≤ P).
Выходные данные
В выходной файл необходимо вывести одно целое число — максимальное суммарное удовлетворение, которого могут добиться пассажиры.
Комментарий к примеру тестов
Максимальное суммарное довольство достигается следующим образом:
На первой остановке входят и садятся второй и третий пассажиры;
На второй остановке входят первый и четвертый пассажиры, второй уступает место первому;
На третьей остановке встают и выходят первый и третий пассажиры, второй и четвертый садятся на их места;
На четвертой остановке выходят второй и четвертый пассажиры.
Разбалловка для личной олимпиады
Тест 1 — из условия. Оценивается в 0 баллов.
Тесты 2-31 — числа M, N, P не превосходят 100. Группа тестов оценивается в 60 баллов.
Тесты 32-41 — число P не превосходит 100. Группа тестов оценивается в 20 баллов (вместе с предыдущей группой — 80 баллов).
Тесты 42-51 — дополнительных ограничений нет. Группа тестов оценивается в 20 баллов (вместе с предыдущими группами — 100 баллов).
Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп.
Примеры
Входные данные
4 2 4 10 -10 2 3 -1 -3 1 4 6 -6 1 3 7 4 2 4
Выходные данные
28
#1217
Темы:
[Сканирующая прямая]
[Быстрая сортировка]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2008,
1 день,
Задача B
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
В известном городе Санкт-Тверь решили построить новый микрорайон, представляющий в плане прямоугольную область. Границы микрорайона и его улицы по проекту ориентированы строго по сторонам света, причем улицы разбивают микрорайон на кварталы размером 1 км × 1 км.
Во время привязки исходного проекта к местности выяснилось, что некоторые кварталы по проекту микрорайона оказываются полностью или частично расположенными на топком болоте. Область, занимаемая болотом, связна и со всех сторон окружена подлежащими застройке кварталами микрорайона (область связна, если из любой ее точки можно добраться в любую другую, не выходя за пределы области).
Для сохранения экологии местности и обеспечения безопасности жителей занятую болотом область решили оградить стеклянным забором. Забор должен проходить только по границам кварталов проектируемого микрорайона, отделяя болото, и, возможно, некоторые кварталы проекта, не занятые болотом, от остальной части микрорайона.
Для экономии строительных материалов забор должен иметь минимальную длину. Среди всех заборов минимальной длины нужно выбрать тот, для которого площадь части микрорайона, попадающей внутрь забора, минимальна.
Требуется написать программу, которая спроектирует забор с заданными выше свойствами.
Входные данные
Входные данные содержат описание многоугольника — границы области, состоящей только из кварталов c заболоченными участками. Стороны многоугольника параллельны осям координат.
В первой строке задано целое число n — количество вершин в многоугольнике (4 ≤ n ≤ 100 000, n четное). В каждой из следующих n строк заданы два целых числа — координаты очередной вершины при обходе этого многоугольника против часовой стрелки. Все числа не превосходят 109 по абсолютной величине. Никакие три последовательные вершины границы не лежат на одной прямой. Граница многоугольника не содержит самопересечений и самокасаний.
Выходные данные
Вывод программы на стандартный поток должен содержать описание многоугольника, определяющего искомый забор. Формат описания многоугольника тот же, что и для входных данных. Никакие три последовательные вершины этого многоугольника не должны лежать на одной прямой.
Примеры
Входные данные
8 0 0 9 0 9 9 6 9 6 3 3 3 3 6 0 6
Выходные данные
6 0 0 9 0 9 9 6 9 6 6 0 6
#1338
Темы:
[Быстрая сортировка]
[Сканирующая прямая]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2009,
Задача B
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Над ареной огромного спортивного комплекса Независимого Главного Университета (НГУ) решили построить перекрытие. Перекрытие будет построено по клеевой технологии и состоять из склеенных друг с другом блоков. Блок представляет собой легкий прямоугольный параллелепипед. Два блока можно склеить, если они соприкасаются перекрывающимися частями боковых граней ненулевой площади.
НГУ представил план комплекса, имеющий вид прямоугольника размером W на L. При этом один из углов прямоугольника находится в начале системы координат, а другой имеет координаты (W, L). Стены комплекса параллельны осям координат.
Подрядчики известили НГУ, что они готовы к определенному сроку изготовить блоки и установить их. Для каждого блока фиксировано место его возможного монтажа, совпадающее по размерам с этим блоком. Места выбраны так, что ребра блоков параллельны осям координат. Места монтажа блоков не пересекаются.
По техническим условиям перекрытие должно состоять из такого набора склеенных блоков, который содержит сплошной горизонтальный слой ненулевой толщины. Торопясь ввести комплекс в эксплуатацию, НГУ решил построить перекрытие из минимально возможного числа блоков.
Требуется написать программу, которая позволяет выбрать минимальное число блоков, которые, будучи установленными на указанных подрядчиками местах, образуют перекрытие, либо определить, что этого сделать невозможно. Высота, на которой образуется перекрытие, не имеет значения.
Входные данные
В первой строке входного файла указаны три целых числа: N — количество возможных блоков (1 ≤ N ≤ 105) и размеры комплекса W и L (1 ≤ W, L ≤ 104). Каждая из последующих N строк описывает место монтажа одного блока, определяемое координатами противоположных углов: (x1, y1, z1) и (x2, y2, z2), при этом 0 ≤ x1 < x2 ≤ W, 0 ≤ y1 < y2 ≤ L, 0 ≤ z1 < z2 ≤ 109. Все числа во входном файле целые и разделяются пробелами или переводами строк.
Гарантируется, что места установки блоков не пересекаются друг с другом.
Выходные данные
Первая строка выходного файла должна содержать либо слово «YES», если перекрытие возможно построить, иначе — слово «NO». В первом случае вторая строка выходного файла должна содержать минимальное число блоков, образующих перекрытие, а последующие строки — номера этих блоков, в соответствии с порядком, в котором они перечислены во входном файле.
Если возможно несколько минимальных наборов блоков, выведите любой из них.
Примечания
Решения, корректно работающие в случае, когда все числа во входном файле не превышают 100, будут оцениваться из 40 баллов.
Примеры
Входные данные
1 10 10 0 0 0 10 10 10
Выходные данные
YES 1 1
Входные данные
2 10 10 0 0 0 10 5 5 0 5 5 10 10 10
Выходные данные
NO
#1761
Темы:
[Сканирующая прямая]
[Задачи на моделирование]
Источники:
[
Командные олимпиады,
Командные чемпионаты школьников Санкт-Петербурга по программированию,
2004,
Задача A
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
В городе \(n\) автобусных остановок, через которые проходят \(k\) кольцевых автобусных маршрутов. Каждый маршрут задается списком номеров остановок, через которые он проходит, \(i\)-ый маршрут проходит по остановкам \(a_{i, 1}\), \(a_{i, 2}\), …, \(a_{i, l_i}\) (в этом порядке). По маршруту ходит ровно один автобус. В момент времени 0 этот автобус находится на остановке \(a_{i,1}\). На то, чтобы доехать до следующей на своем маршруте остановки, автобус тратит ровно одну минуту. Временем стоянки автобуса на остановке можно пренебречь. Все маршруты кольцевые, то есть через минуту после остановки \(a_{i, l_i}\) автобус оказывается на остановке \(a_{i, 1}\) и едет по маршруту еще раз.
Несколько человек в этом городе решили покататься на автобусах. При этом каждый из них составил план своего катания. План \(j\)-го человека состоит из остановки \(b_j\), на которой человек начнет свое катание и последовательности чисел \(c_{j, 1}\), \(c_{j, 2}\), …, \(c_{j, m_j}\). Эти числа означают следующее: в момент времени 0 человек придет на остановку \(b_j\) и дождется ближайшего автобуса (если в этот момент какой-то автобус находится на остановке \(b_j\), человек сядет в него). На этом автобусе он проедет \(c_{j, 1}\) остановок, после чего выйдет и дождется следующего автобуса на той остановке, где он окажется. На нем он проедет \(c_{j, 2}\) остановок, снова выйдет и снова дождется следующего автобуса. И так далее. Если в какой-то момент к остановке подъедет сразу несколько автобусов, то человек сядет в автобус с минимальным номером маршрута. Когда человек выходит из автобуса на какой-то остановке, он может уехать с этой остановки не раньше, чем через минуту.
Для каждого человека определите, через сколько минут после начального момента и на какой остановке закончится его катание.
Входные данные
Во входном файле записано сначала число \(n\), затем число \(k\). Далее записано \(k\) строк, задающих автобусные маршруты. Каждая строка начинается с числа \(l_i\), задающего длину маршрута, затем идет список остановок, через которые проходит маршрут: \(a_i\),1, \(a_i\),2,… \(a_i\),\(l_i\). Маршрут может несколько раз проходить через одну и ту же остановку.
Далее идет число \(p\) – количество людей, и затем p строк, задающих планы людей. Каждая строка содержит сначала числа \(b_j\) – номер начальной остановки и \(m_j\) – количество чисел в последовательности. Затем идут числа \(c_j\),1, \(c_j\),2, …, \(c_j\),\(m_j\).
Все числа во входном файле натуральные и не превышают 50.
Выходные данные
В выходной файл для каждого человека выведите два числа: время в минутах, когда закончится его катание, и номер остановки, на которой это произойдет. Если же человек не сможет реализовать свой план до конца (на какой-либо остановке он не дождется автобуса), выведите для него два нуля.
Примеры
Входные данные
6 4 4 1 2 3 5 2 3 4 5 5 2 1 3 2 2 4 3 3 1 4 1 2 3 4 2 1 1 6 3 1 2 3
Выходные данные
20 1 2 3 0 0
#2534
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2010,
Задача F
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Фермер Архип решил заняться земледелием и выращивать брюссельскую редиску. Для этого он купил прямоугольное поле, состоящее из \(n\) рядов по \(m\) участков в каждом. Все участки являются одинаковыми и имеют квадратную форму. Оказалось, что на момент покупки некоторые из этих участков уже удобрены, а некоторые — нет. Редиска растет только на удобренных участках.
Для получения большего урожая Архип решил удобрить некоторый прямоугольный фрагмент поля, состоящий из целых участков. В выбранном фрагменте Архип удобряет каждый участок. Повторное удобрение участка делает его непригодным к выращиванию брюссельской редиски. Закончив удобрять, фермер выбирает для посадки редиски прямоугольный фрагмент поля, состоящий из целых участков, каждый из которых удобрен ровно один раз.
Архип должен выбрать на поле фрагмент для удобрения таким образом, чтобы фрагмент для посадки редиски имел максимальную площадь.
Напишите программу, которая по заданному полю находит фрагмент поля для удобрения и фрагмент поля под посадку.
Входные данные
В первой строке входного файла записаны натуральные числа \(n\) и \(m\) (\(2\le n\le2\,000\), \(2\le m\le2\,000\)), где \(n\) — количество рядов на поле, а \(m\) — количество участков в каждом ряду (количество столбцов). Далее в \(n\) строках содержится описание поля. Каждая из этих \(n\) строк содержит \(m\) символов. Символ «1» обозначает, что соответствующий участок поля удобрен, а «0» — не удобрен. Гарантируется, что поле содержит хотя бы один удобренный и хотя бы один неудобренный участок. Поле расположено таким образом, что первая строка его описания соответствует северной стороне, а первый столбец — западной стороне.
Выходные данные
Первая строка должна описывать фрагмент поля для удобрения. Фрагмент описывается четырьмя числами \(a\), \(b\), \(c\), \(d\), где \(a\) и \(b\) — номер ряда и столбца самого северо-западного его участка, а \(c\) и \(d\) — номер ряда и столбца самого юго-восточного. Ряды нумеруются с севера на юг от 1 до \(n\), а столбцы — с запада на восток от 1 до \(m\).
Вторая строка должна описывать фрагмент под посадку в том же формате.
Третья строка должна содержать площадь фрагмента (количество участков) под посадку.
Если решений несколько, выведите любое.
Система оценивания
Решения, корректно работающие при \(n\le40\) и \(m\le40\), будут оцениваться из 30 баллов, а решения, корректно работающие при \(n\le300\) и \(m\le300\), будут оцениваться из 60 баллов.
Примеры
Входные данные
4 4 1110 1010 1110 0000
Выходные данные
2 2 2 2 1 1 3 3 9
Выбрано
:
|