--->
92 задач
<---
Источники
#112099
Темы:
[Одномерные массивы]
[Порядковые статистики]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Кроме Земли, пандорианцы уже много тысячелетий исследуют и другие планеты. Большой интерес для них в прошлом представляла планета Арракис. К сожалению, с началом исследований на Земле финансирование исследований на Арракисе было существенно урезано, и местным агентам-исследователям пришлось искать дополнительные источники дохода.
К счастью, пандорианцы очень хорошо разбираются в финансовых вопросах. Им не составило труда проанализировать политические, экономические и психологические тенденции, а также некоторые другие факторы, не имеющих названий на земных языках и на основе этих данных точно предсказать изменение стоимости воды на Арракисе на ближайший год. Как известно, вода на этой планете является главной ценностью после золота, на которое эту воду можно купить.
Изначально пандорианцы обладают запасом золота в 10 золотых слитков. Они решили в один из дней года купить на все это золото воды, а в какой-то последующий день продать всю купленную воду и получить прибыль за счет разницы стоимости. К примеру, если бы стоимость воды в день покупки составляла 1 литр за 4 золотых слитка, а стоимость воды в день продажи – 1 литр за 6 золотых слитков, то пандорианцы могли бы получить купить \(\frac{10}{4}=2.5\) литра воды, а продать они эту воду смогут за \(2.5 \times 6=15\) золотых слитков. Таким образом, прибыль пандорианцев составила бы \(15-10=5\) золотых слитков. Конечно же, пандорианцы хотят максимизировать свой доход в результате этих махинаций. Помогите им выбрать оптимальные дни для покупки и продажи воды!
Входные данные
В первой строке задано целое число 2 ≤ N ≤ 100 000 — количество дней в году на планете Арракис.
Во второй строке заданы N целых положительных чисел a i ( 1 ≤ i ≤ N , 1 ≤ a i ≤ 5000 ), задающих стоимость воды на Арракисе в день i .
Выходные данные
Выведите два целых числа: первое число — номер дня, в который стоит купить воду, второе число — номер дня, в который следует воду продать. Дни нумеруются с единицы. Если оптимальных пар дней для покупки/продажи несколько, то выведите любую из них.
Выведите два нуля, если покупка и продажа воды по указанной схеме не принесет пандорианцам прибыли.
Примеры
Входные данные
6 10 3 5 3 11 9
Выходные данные
2 5
Входные данные
4 5 5 5 5
Выходные данные
0 0
#112811
Темы:
[Рекурсия]
[Одномерные массивы]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
512 megabytes
На день рождения маленький Ипполит получил долгожданный подарок — набор дощечек с написанными на них буквами латинского алфавита. Теперь-то ему будет чем заняться долгими вечерами, тем более что мама обещала подарить ему в следующем году последовательность целых неотрицательных чисел, если он хорошо освоит этот набор. Ради такого богатства Ипполит готов на многое.
Прямо сейчас юный исследователь полностью поглощён изучением хорошести строк. Хорошестью строки называется количество позиций от 1 до L - 1 (где L — длина строки), таких, что следующая буква в строке является следующей по алфавиту. Например, хорошесть строки "abcdefghijklmnopqrstuvwxyz" равна 25, а строки "abdc" — только 1.
Ипполит размышляет над решением закономерно возникающей задачи: чему равна максимально возможная хорошесть строки, которую можно собрать, используя дощечки из данного набора? Вы-то и поможете ему с ней справиться.
Входные данные
Первая строка ввода содержит единственное целое число N — количество различных букв в наборе (1 ≤ N ≤ 26). Обратите внимание: в наборе всегда используются N первых букв латинского алфавита.
Следующие N строк содержат целые положительные числа ci — количество букв соответствующего типа (1 ≤ ci ≤ 109). Таким образом, первое число означает количество букв "a", второе число задаёт количество букв "b" и так далее.
Выходные данные
Выведите единственное целое число — максимально возможную хорошесть строки, которую можно собрать из имеющихся дощечек.
Примеры тестов
Входные данные
3
1
1
1
Выходные данные
2
Входные данные
2
3
4
Выходные данные
3
Примечание
В первом тесте имеется по одной дощечке с каждой из 3 различных букв. Ответ 2 достигается на строке "abc"
Система оценки
Каждый тест в данной задаче оценивается отдельно. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются.
Подзадача 1. Во всех тестах данной группы ci ≤ 100. Данная подзадача оценивается из 40 баллов.
Подзадача 2. Во всех тестах данной группы ci ≤ 1 000 000. Данная подзадача оценивается из 30 баллов.
Подзадача 3. Во всех тестах данной группы ci ≤ 109. Данная подзадача оценивается из 30 баллов.
ограничение по времени на тест
2 секундыограничение по памяти на тест
256 мегабайтОбычно в условии задач вам долго и нудно рассказывают, что нужно сделать. Но нам это показалось скучным. В этой задаче мы сделаем по-другому. Мы скажем вам, что не нужно делать:
Дана последовательность различных целых чисел. Переставьте её как вам угодно. Единственное требование: получившаяся последовательность не должна быть отсортирована — ни по возрастанию, ни по убыванию.
Входные данные
В первой строке содержится единственное число T (T ≤ 1 000) — количество тестов. Каждый тест состоит из двух строк:
В первой строке содержится единственное число N (3 ≤ N ≤ 1 000) — длина последовательности чисел.
В следующей строке содержатся N различных целых чисел — элементы последовательности. Гарантируется, что каждое число не меньше - 231 и не превосходит 231 - 1.
Выходные данные
Для каждого теста в отдельной строке выведите новую последовательность.
Примеры тестов
Входные данные
2
5
1 2 3 4 5
8
3 1 4 47 5 9 2 6
Выходные данные
5 1 4 3 2
3 1 4 47 5 9 2 6
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
«Знание наперед нельзя получить от богов и демонов,
нельзя получить и путем умозаключений по сходству,
нельзя получить и путем всяких вычислений.
Знание положения противника можно получить
только от людей» (Сунь Цзы, «Искусство войны»)
Для поднятия престижа Короны среди граждан Королевства, Его Величеству Бубею Второму понадобилась небольшая победоносная война. В качестве цели был выбран маленький приграничный город. Королевским шпионам было дано задание узнать численность войск, находящихся в городе. Так как ежедневно пересчитывать всех солдат в целом городе очень сложно, то было решено что такой подсчет будет сделан только один раз. Затем шпионы будут только наблюдать за прибывающими или убывающими из города частями (уже не с точностью до одного человека, а с точностью до войсковой единицы: взвод, рота, полк) и ежедневно докладывать в Столицу.
Однако не все войсковые единицы противника могут состоять из одинакового числа солдат. Поэтому для каждой такой единицы в Военном Министерстве введены специальные поправки.
Пусть известно начальное количество солдат противника в городе и известно какие войсковые единицы и в каком порядке покидали город или входили в него. Напишите программу, которая по этим данным вычислит максимально возможное количество солдат в городе на текущий момент.
Входные данные
В первой строке файла input.txt записано начальное количество солдат (целое, положительное, не превышает 3000). Во второй строке записано число P (целое, положительное, не более 10) – количество названий разных войсковых единиц в армии потенциального противника. Следующие P строк имеют такой формат: <название войсковой единицы><численность><поправка>. Название войсковой единицы – строка, содержащая только заглавные буквы английского алфавита длины не более 10 символов. Численность – целое положительное число не более 10000, поправка – целое положительное число не более 100.
Пример такой строки:
BRIGADE 2000 50 – это означает что в войсковой единице BRIGADE может быть от 1950 до 2050 солдат (поправка действует в обе стороны).
В следующих строках файла указаны данные из донесений шпионов по одному донесению в строке. Формат донесения <знак><название войсковой единицы>, где знак ‘+’ означает что единица вошла в город, ‘-’ – что единица покинула город. Гарантируется, что количество солдат в городе в любой момент времени не превышает \(10^6\).
Количество солдат также не может быть отрицательным (гарантируется, что входные данные непротиворечивы).
Выходные данные
В файл output.txt выведите единственное число – максимально возможную численность солдат в городе.
Пояснения к примерам
Комментарий к первому примеру: было 500 солдат, затем в город вошла BRIGADE численностью от 900 до 1100 (максимально 1100, поэтому прибавляем это число), затем вошла ARMY численностью от 2500 до 3500, а в конце BATTALION (от 450 до 550 человек).
Комментарий ко второму примеру: было 500 солдат, затем BATTALION (от 450 до 550) покинул город. В городе осталось от 0 до 50 солдат, берем максимальное по условию. Затем в город вошло от 450 до 550 солдат).
Примеры
Входные данные
500 3 BATTALION 500 50 BRIGADE 1000 100 ARMY 3000 500 +BRIGADE +ARMY +BATTALION
Выходные данные
5650
Входные данные
500 1 BATTALION 500 50 -BATTALION +BATTALION
Выходные данные
600
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Дано количество сообщений на некотором форуме (\(N\) натуральное, не более \(1000\)).
Также таблица, в которой указано какие сообщения на каком уровне находятся.
В первой колонке таблицы написаны номера сообщений (натуральные числа, не превосходят \(10^6\)).
Во второй колонке напротив номера сообщения стоит либо 0, если сообщение является корнем (началом) некоторой темы, либо номер того сообщения, ответом на которое является текущее.
Пример. Следующие исходные данные:
4 1 0 2 0 3 1 4 3соответствуют такой структуре форума:
Пусть администратор форума желает удалить сообщение с номером \(k\) (а также всю подветвь форума от этого сообщения). Сколько сообщений всего будет удалено (включая само сообщение номер \(k\))?
Входные данные
Сначала вводится натуральное число \(N\) (не превышает \(1000\)) – общее количество сообщений на форуме.
Затем вводится \(N\) строк таблицы, по \(2\) числа на строке – номер текущего сообщения и номер того сообщения, ответом на которое является текущее (или \(0\)).
В последней строке вводится натуральное число \(k\). Гарантируется, что сообщение с номером \(k\) существует.
Выходные данные
Выведите количество сообщений, которое будет удалено.
Примеры
Входные данные
1 1 0 1
Выходные данные
1
Выбрано
:
|