Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 544 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 91 92 93 94 95 96 97 >> Отображать по:
#112038
Межрегиональная олимпиада
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

На межрегиональной олимпиаде по программированию роботов соревнования проводятся в один тур и в необычном формате. Задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая \(i\)-я задача (1 ≤ \(i\) ≤ \(n\)) становится доступной участникам в свой момент времени \(s_i\). При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть \(t_i\) минут на то, чтобы сдать ее решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведенное на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение \(i\)-й задачи участник получает \(c_i\) баллов.

Артур, представляющий на межрегиональной олимпиаде один из региональных центров искусственного интеллекта, понимает, что важную роль на такой олимпиаде играет не только умение решать задачи, но и правильный стратегический расчет того, какие задачи надо решать, а какие пропустить. Ему, как и всем участникам, до начала тура известно, в какой момент времени каждая задача станет доступной, сколько времени будет отведено на ее решение и сколько баллов можно получить за ее решение. Артур является талантливым школьником и поэтому сможет успешно решить за отведенное время и сдать на проверку любую задачу, которую он выберет для решения на олимпиаде.

Требуется написать программу, которая определяет, какое максимальное количество баллов Артур сможет получить при оптимальном выборе задач, которые он будет решать, а также количество и перечень таких задач.

Формат входного файла

Первая строка входного файла содержит одно целое число \(n\) (1 ≤ \(n\) ≤ \(10^5\)) количество задач на олимпиаде.

Последующие \(n\) строк содержат описания задач, по три числа на каждой строке: \(s_i\) момент появления \(i\)-й задачи в минутах, \(t_i\) время, отведенное на ее решение в минутах, и \(c_i\) сколько баллов получит участник за решение этой задачи (1 ≤ \(s_i\), \(t_i\), \(c_i\) ≤ \(10^9\)).

Формат выходного файла

Первая строка выходного файл должна содержать одно число – максимальное количество баллов, которое сможет получить Артур на олимпиаде.

Вторая строка должна содержать одно целое число \(m\) - количество задач, которые надо решить при оптимальном выборе.

Третья строка должна содержать \(m\) разделенных пробелом целых чисел - номера этих задач в порядке их решения. Задачи пронумерованы, начиная с единицы, в порядке их описания во входном файле.

Если оптимальных ответов несколько, необходимо вывести любой из них.

Пояснения к примерам

В первом примере Артур успевает решить все задачи и получить три балла.

Во втором примере Артуру выгоднее решать последнюю задачу и получить за нее три балла, чем решать только первые две и получить два балла.

Система оценивания

Частичные правильные решения для тестов, в которых все \(c_i\) одинаковы и \(n\) ≤ 1000, оцениваются из 30 баллов.

Частичные правильные решения для тестов, в которых все \(c_i\) одинаковы, оцениваются из 50 баллов.

Частичные правильные решения для тестов, в которых \(n\) ≤ 1000, оцениваются из 50 баллов.

Примеры
Входные данные
2
1 1 1
2 2 2
Выходные данные
3
2
1 2
Входные данные
3
1 2 1
3 2 1
2 4 3
Выходные данные
3
1
3
#112041
Кондиционеры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.

Все классы школы пронумерованы последовательно от 1 до \(n\). Известно, что для каждого класса с номером \(i\), требуется ровно один кондиционер, мощность которого больше или равна \(a_i\) ватт.

Администрации школы предоставили список из \(m\) различных моделей кондиционеров, которые можно закупить. Для каждой модели кондиционера известна его мощность и стоимость. Требуется написать программу, которая определит, за какую минимальную суммарную стоимость кондиционеров можно оснастить все классы школы.

Формат входного файла

Первая строка входного файла содержит одно целое число n (1 ≤ \(n\) ≤ 50 000) количество классов в школе.

Вторая строка содержит \(n\) целых чисел \(a_i\) (1 ≤ \(a_i\) ≤ 1000)- минимальная мощность кондиционера в ваттах, который можно установить в классе с номером \(i\).

Третья строка содержит одно целое число \(m\) (1 ≤ \(m\) ≤ 50 000) - количество предложенных моделей кондиционеров.

Далее, в каждой из \(m\) строк содержится пара целых чисел \(b_j\) и \(c_j\) (1 ≤ \(b_j\) ≤ 1000, 1 ≤ \(c_j\) ≤ 1000) мощность в ваттах \(j\)-й модели кондиционера и его цена в рублях соответственно.

Формат выходного файла

Выходной файл должен содержать одно число минимальную суммарную стоимость кондиционеров в рублях. Гарантируется, что хотя бы один корректный выбор кондиционеров существует, и во всех классах можно установить подходящий кондиционер.

Пояснения к примерам

В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.

Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе – кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).

Система оценивания

Частичные решения для \(n\), \(m\) ≤ 1000 будут оцениваться из 50 баллов.

Примеры
Входные данные
1
800
1
800 1000
Выходные данные
1000
Входные данные
3
1 2 3
4
1 10
1 5
10 7
2 3
Выходные данные
13
#112089
Пляжный волейбол
  
Темы: [Очередь]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Вера очень много работала в этом году, подавая своим коллегам пример настоящего труженика. На восьмое марта за прекрасное исполнение служебных обязанностей Вера получила подарок — долгожданный отпуск в Теплой Стране! Тяжелые трудовые будни закончились, и Вера уже нежится на пляже на берегу Теплого Моря.

Любимое хобби Веры — пляжный волейбол, и как же Вера ждала момента, когда она сможет испытать невероятный азарт этой игры! Вера уже познакомилась с несколькими симпатичными волейболистами, но она пока не решила, какая же команда достойна иметь в своем составе такого замечательного игрока.

Каждый из N капитанов команд мечтает заполучить Веру в состав своей команды, поэтому они хотят максимально проявить себя. Так как поиграть хотят все, они решили действовать следующим образом: все N команд выстроились в очередь. Первый матч играется между двумя командами, которые стоят в очереди раньше остальных. Победитель игры остается на площадке, а проигравший отправляется в конец очереди. В каждом из следующих матчей победитель предыдущего играет с первой командой из очереди, а про- игравший в очередной встрече опять становится в конец очереди. Каждая команда имеет некоторую силу, причем для простоты будем предполагать, что силы всех команд различны, а победителем в матче является команда, сила которой больше. Матчей может быть как угодно много.

Вера решила для себя, что она будет действовать по самому справедливому принципу «считалочки»: она будет играть с одной из двух команд, играющих матч с соответствующем считалке номером \(K\). Но затем Вера поняла, что уже выбрала себе команду, в которой хотела бы играть, причем ориентируясь не только на ее силу. Ей известны \(Q\) считалок, соответствующих различным значениям \(K\). Для каждого из этих чисел \(K_i\) необходимо узнать, а кто же именно будет сражаться за столь ценный приз, то есть какие две команды будут играть в матче с номером \(K_i\).

Формат входного файла

Первая строка входных данных содержит единственное целое число \(N\) — количество команд (2 ≤ \(N\) ≤ 100 000). Вторая строка содержит \(N\) различных чисел от 1 до \(N\) — силы команд: первое число — сила команды, стоящей в начале очереди, второе — сила следующей по очереди команды, ..., последнее — сила команды, стоящей в конце очереди.

Третья строка содержит единственное целое число \(Q\) (1 ≤ \(Q\) ≤ 100 000) — количество известных Вере считалок. Каждая из следующих Q строк содержит число \(K_i\) (1 ≤ Ki ≤ 1018) — номер очередного интересующего Веру матча. Обратите внимание, \(K_i\) может быть больше \(N\).

Формат выходного файла

Выведите \(Q\) строк: для каждого интересующего Веру числа \(K_i\) два числа в любом порядке — силы команд, сыграющих на \(K_i\)-м шаге. Первая строка должна содержать ответ на первый запрос, вторая — на второй и так далее.

Комментарии

Разберем первый тест из условия:

Таким образом, в единственном интересующем Веру третьем матче сыграют команды с силами 4 и 3.

Система оценивания

Тесты к этой задаче состоят из четырех групп.

0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.

1. Тесты 3–18. В тестах этой группы \(N\) ≤ 2 000, Q = 1, \(K_i\) ≤ 2 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

2. Тесты 19–25. В тестах этой группы \(N\) ≤ 100 000, 1 ≤ \(Q\) ≤ 10, \(K_i\) ≤ 100 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.

3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура, причем только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.

Примеры
Входные данные
4
1 3 2 4
1
3
Выходные данные
3 4
Входные данные
4
2 1 4 3
3
1
5
2
Выходные данные
2 1
4 2
2 4
#112090
Турист Петр
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

На отдыхе в Теплой Стране Вера познакомилась с симпатичным волейболистом- трактористом Петром. Турист Петр, кстати, собирается после отличного отдыха в Теплой Стране отправиться в путешествие по городам Европы. Как известно, Европа обладает развитой транспортной системой: в Европе есть \(V\) интересующих Петра городов и \(E\) маршрутов ночных поездов. Каждый маршрут соединяет два различных города, время в пути составляет одну ночь. Поезда по маршруту ходят в обоих направлениях.

Основной целью поездки Петра является осмотр местных достопримечательностей. По- скольку Петр — невероятно занятой человек, то он решил, что все путешествие должно занимать не более четырех дней. Петр уже многое повидал, поэтому на осмотр достопримечательностей в каждом городе Петр тратит ровно один день. Он хочет составить наиболее практичный тур: каждый день он будет тратить на осмотр города, а каждую ночь — на переезд ночным поездом между городами. Разумеется, Петр не имеет ни малейшего желания посещать один город несколько раз.

Но на этом прагматичность Петра не заканчивается: Петр, как настоящий турист, хочет посмотреть на самые красивые европейские достопримечательности. Он долго изучал справочники и для каждого города оценил свою ожидаемую радость от его посещения \(p_i\). Теперь он хочет найти маршрут, при котором его радость будет наибольшей. Помогите Петру найти такой маршрут.

Формат входного файла

В первой строке входных данных заданы два целых числа \(V\) и \(E\) (1 ≤ \(V\); \(E \le 3*10^5\)) — количество городов и маршрутов поездов, соответственно. В следующей строке заданы V целых чисел \(p_i\) (1 ≤ \(p_i\) ≤ \(10^8\)), где \(p_i\) обозначает ожидаемую радость от посещения го- рода с номером \(i\). В следующих \(E\) строках заданы описания маршрутов поездов. Каждое описание состоит из пары различных чисел \(a_i\) и \(b_i\) (1 ≤ \(a_i\); \(b_i\) ≤ V\( \)) — номеров городов, между которыми курсирует этот маршрут поезда. Гарантируется, что между каждой парой городов существует не более одного маршрута поезда.

Формат выходного файла

В первой строке выходных данных выведите число K (1 ≤ K ≤ 4) — количество городов в оптимальном маршруте туриста Петра. В следующей строке выведите номера этих городов в порядке посещения. Города нумеруются начиная с единицы. Если оптимальных маршрутов несколько, выведите любой из них.

Система оценивания

Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.

0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.

1. Тесты 3–16. В тестах этой группы \(V\); \(E\) ≤ 100. Эта группа оценивается в 20 баллов

2. Тесты 17–32. В тестах этой группы \(V\); \(E\) ≤ 1 000. Эта группа оценивается в 20 баллов.

3. Тесты 33–53. В тестах этой группы \(V\) ≤ 3 000, \(E\) ≤ 60 000. Эта группа оценивается в 30 баллов.

4. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 30 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура.

Примеры
Входные данные
5 4
4 2 3 1 5
1 2
2 3
3 4
4 5
Выходные данные
4
2 3 4 5
Входные данные
4 3
1 2 3 4
1 2
1 3
1 4
Выходные данные
3
4 1 3
#112091
Шустрая черепашка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Пафнутий и его друзья — большие любители разнообразных настольных игр. Особенно им нравятся игры, требующие как можно быстрее производить в уме непростые вычисления, поэтому абсолютным хитом их вечерних посиделок в аудиториях НУОП (Неизвестного университета олимпиадного программирования) стала игра «Шустрая черепашка». В комплект игры входят:

* Клетчатое поле из \(N\) рядов по \(M\) клеток. Каждая клетка поля либо свободна, либо блокирована для перемещения.

* Q игровых карточек. Каждая карточка содержит описание множества стартовых клеток A, множества дополнительно блокируемых клеток B и множества конечных клеток C. Множества A, B и C непусты, попарно не пересекаются и состоят из свободных клеток.

* Маленькая фишка в форме черепашки.

Правила игры очень просты. Игроки последовательно разыгрывают игровые карточки. Как только открывается очередная карточка, игрокам необходимо вычислить, сколько существует хороших троек клеток (\(a_i b_j c_k)\), где \(a_i \in A\), \(b_j \in B\), \(c_k \in C\). Тройка клеток называется хорошей, если можно провести черепашку из стартовой клетки ai в конечную клетку \(c_k\), не посещая при этом клетку \(b_j\). На перемещение черепашки наложено три условия:

1. Черепашка имеет право перемещаться только вниз и вправо в пределах поля.

2. Находиться на блокированных клетках запрещено

3. Клетка \(b_j\) также блокируется для перемещения

Так как таблицу с правильными ответами создатели не включили в комплект, в пылу игры постоянно возникают споры о правильности того или иного значения. Для установления истины ребята попросили вас посчитать ответы для данного комплекта.

Формат входного файла

Первая строка входного файла содержит два целых числа \(N\) и \(M\) (1 ≤ \(N\), \(M\) ≤ 150) — количество строк и столбцов игрового поля.

Следующие \(N\) строк по \(M\) символов описывают игровое поле в порядке следования сверху вниз, слева направо. Символ ‘.’ соответствует свободной клетке, а ‘#’ — занятой. Строки нумеруются от 1 до \(N\), столбцы — от 1 до \(M\)

Следующая строка содержит целое число \(Q\) (1 ≤ \(Q\) ≤ 100 000) — количество игровых карточек.

Далее следуют \(Q\) блоков, описывающих карточки. Каждый блок состоит из трех строк, описывающих множества \(A\), \(B\) и \(C\) соответственно. Первое число описания определяет размер соответствующего множества, после чего перечисляются его клетки. Каждая клетка задается двумя числами — номером строки и номером столбца. Все клетки в описании различны. Смотрите комментарии к примеру для лучшего понимания формата входных данных.

Гарантируется, что все множества непусты, все клетки всех множеств являются свободными и никакая клетка не принадлежит более чем одному множеству из какой-то карточки.

Формат выходного файла

В выходной файл выведите ровно \(Q\) чисел по одному на строке — правильные ответы на карточки в порядке их следования во входном файле.

Комментарии

В приведенном примере игровой комплект содержит две карточки

Во всех тройках первой карточки черепашка стартует в верхнем левом углу и финиширует в правом нижнем. Несложно видеть, что это возможно сделать, только если из трех элементов множества \(B\) блокируется первая клетка второй строки, то есть хорошей тройкой является \((1, 1) - (2, 1) - (5, 6)\).

На второй карточке хорошими являются тройки: \((1, 2) - (3, 1) - (5, 6)\), \((2, 1) - (3, 1) - (5, 6)\), \((2, 1) - (3, 3) - (5, 1)\).

Система оценивания

Тесты к этой задаче состоят из четырех групп

0. Тест 1. Тест из условия, оценивается в ноль баллов.

1. Тесты 2–18. В тестах этой группы \(N\) ≤ 100, \(Q\)total ≤ 1 000. Эта группа оценивается в 30 баллов. Баллы начисляются только при прохождении всех тестов группы.

2. Тесты 19–32. В тестах этой группы \(N\) ≤ 100, \(Q\)total ≤ 1 000 000. Эта группа оценивается в 30 баллов. Баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.

3. В тестах этой группы дополнительные ограничения отсутствуют, однако гарантируется, что \(N\) и \(Q\)total будут равномерно возрастать с номером теста. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура, причем только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.

Примеры
Входные данные
5 6
..##..
....#.
.#.#..
.#...#
..#...
2
1 1 1
3 2 1 2 3 4 3
1 5 6
2 1 2 2 1
2 3 1 3 3
2 5 1 5 6
Выходные данные
1
3
Страница: << 91 92 93 94 95 96 97 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест