--->
10 задач
<---
Источники
#1001
Темы:
[Очередь]
Источники:
[
Личные олимпиады,
Московская олимпиада школьников,
10-11 классы,
2004,
1 день,
Задача A
]
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes
Дано N целых чисел. Требуется выбрать из них три таких числа, произведение которых максимально.
Дано N целых чисел. Требуется выбрать из них три таких числа, произведение которых максимально.
Входные данные
Во входном файле записано сначала число N — количество чисел в последовательности (3≤N≤106). Далее записана сама последовательность: N целых чисел, по модулю не превышающих 30000.
Выходные данные
В выходной файл выведите три искомых числа в любом порядке. Если существует несколько различных троек чисел, дающих максимальное произведение, то выведите любую из них.
Примеры
Входные данные
9 3 5 1 7 9 0 9 -3 10
Выходные данные
9 10 9
Входные данные
3 -5 -30000 -12
Выходные данные
-5 -30000 -12
#111636
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2013,
1 день,
Задача D
]
История Татаро-монгольского ханства богата на правителей. Каждый из N правителей принадлежал к одной из двух династий, причём власть часто переходила от одной династии к другой. Каждое восхождение правителя на престол отмечалось праздником, проводимым 26 марта. В летописях зафиксированы годы проведения этих праздников, причем известно, что правители первой династии устраивали для народа праздник кумыса, а второй — праздник мёда.
На конференции по истории Татаро-монгольского ханства каждый из S учёных предложил свою версию толкования летописи. А именно, i-й историк утверждал, что от каждого праздника кумыса до следующего праздника кумыса проходило не менее KLi лет, но не более KRi лет, в то время как от каждого праздника мёда до следующего праздника мёда проходило не менее MLi лет, но не более MRi лет.
Каждой предложенной версии может соответствовать несколько распределений правителей по династиям. Ученые договорились считать показателем сомнительности распределения число переходов власти к представителю той же самой династии.
Требуется написать программу, которая найдёт распределение, соответствующее хотя бы одной из версий и имеющее наименьший показатель сомнительности, а также версию, которой оно соответствует.
Входные данные
В первой строке входного файла записано число N (2 ≤ N ≤ 200 000) — количество праздников в летописи. Следующая строка содержит целые числа X1, X2, ..., XN (1 ≤ X1 ≤ X2 ≤ ... ≤ XN ≤ 109) — годы проведения праздников.
В третьей строке записано число учёных S (1 ≤ S ≤ 50). В каждой из последующих S строк записаны четыре натуральных числа KLi, KRi, MLi, MRi (1 ≤ KLi ≤ KRi ≤ 109), (1 ≤ MLi ≤ MRi ≤ 109).
Выходные данные
Первая строка выходного файла должна содержать числа P и Q, где P — номер учёного, версии которого соответствует распределение с наименьшим показателем сомнительности, а Q — показатель сомнительности этого распределения.
Вторая строка должна состоять из N цифр 1 и 2, записанных без пробелов, означающих приход к власти представителя первой или второй династии соответственно. Если существует несколько решений с наименьшим показателем сомнительности Q, выведите любое из них.
В случае, если ни в одной из версий учёных не существует способа распределения периодов правления между династиями так, чтобы не нарушались ограничения на промежутки времени между праздниками, выходной файл должен содержать единственное число 0.
Примечание
Данная задача содержит шесть подзадач. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
- Тесты из условия. Подзадача оценивается в 0 баллов.
- 2 ≤ N ≤ 15, 1 ≤ S ≤ 10. Подзадача оценивается в 20 баллов.
- 2 ≤ N ≤ 2000, 1 ≤ S ≤ 50, N × S ≤ 2000. Подзадача оценивается в 20 баллов.
- 2 ≤ N ≤ 10 000, 1 ≤ S ≤ 50, N × S ≤ 10 000. Подзадача оценивается в 20 баллов.
- 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50, N × S ≤ 200 000. Подзадача оценивается в 20 баллов.
- 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50. Подзадача оценивается в 20 баллов.
Примеры
Входные данные
3 1 2 3 1 1 1 1 1
Выходные данные
1 1 211
Входные данные
4 1 6 9 13 2 1 2 2 3 6 7 3 3
Выходные данные
0
Входные данные
5 3 6 8 9 10 2 2 3 1 1 1 4 1 10
Выходные данные
2 0 21212
#112089
Темы:
[Очередь]
Источники:
[
Личные олимпиады,
Открытая олимпиада школьников,
2013-2014,
Заключительный этап,
Задача A
]
ограничение по времени на тест
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
Фирма NNN решила транслировать свой рекламный ролик в супермаркете XXX. Однако денег, запланированных на рекламную кампанию, хватило лишь на две трансляции ролика в течение одного рабочего дня. И при этом обязательно транслировать ровно два рекламных ролика в день.
Фирма собрала информацию о количестве покупателей в каждый момент некоторого дня. Менеджер по рекламе предположил, что и на следующий день покупатели будут приходить и уходить ровно в те же моменты времени.
Помогите ему определить моменты времени, когда нужно включить трансляцию рекламных роликов, чтобы как можно большее количество покупателей прослушало ролик.
Ролик длится ровно одну единицу времени. Для каждого момента времени известно количество покупателей, находящихся в магазине в этот момент. Между концом первой рекламы и началом следующей должна пройти как минимум К - 1 единица времени.
Входные данные
Первая строка содержит два числа N (моментов времени) и K (время совершения покупки одним покупателем). Гарантируется, что N > K. ( N, K ≤ 200 000 ). Во второй строке содержится N чисел a i — количество покупателей в момент времени i . ( 0 ≤ a i ≤ 2 000 000 000 ).
Выходные данные
Выведите единственное число — количество просмотревших рекламу покупателей.
Примеры
Входные данные
5 2 3 5 1 4 2
Выходные данные
9
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes
Гоблины Мглистых гор очень любях ходить к своим шаманам. Так как гоблинов много, к шаманам часто образуются очень длинные очереди. А поскольку много гоблинов в одном месте быстро образуют шумную толку, которая мешает шаманам проводить сложные медицинские манипуляции, последние решили установить некоторые правила касательно порядка в очереди.
Обычные гоблины при посещении шаманов должны вставать в конец очереди. Привилегированные же гоблины, знающие особый пароль, встают ровно в ее середину, причем при нечетной длине очереди они встают сразу за центром.
Так как гоблины также широко известны своим непочтительным отношением ко всяческим правилам и законам, шаманы попросили вас написать программу, которая бы отслеживала порядок гоблинов в очереди.
Входные данные
В первой строке входных данный записано число \(N\) (\(1\le N\le 10^5\)) - количество запросов к программе. Следующие \(N\) строк содержат описание запросов в формате:
- "+ i" - гоблин с номером \(i\) (\(1\le i \le N\)) встает в конец очереди.
- "* i" - привилегированный гоблин с номером \(i\) встает в середину очереди.
- "-" - первый гоблин из очереди уходит к шаманам. Гарантируется, что на момент такого запроса очередь не пуста.
Выходные данные
Для каждого запроса типа "-" программа должна вывести номер гоблина, который должен зайти к шаманам.
Примеры
Входные данные
7 + 1 + 2 - + 3 + 4 - -
Выходные данные
1 2 3
Выбрано
:
|