OpenFIPI 2.0

Задание выполняется с использованием прилагаемых
файлов.

Пусть S – последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L, R) подпоследовательность, состоящую из идущих подряд элементов, входящих в S, начиная с элемента с номером L и заканчивая элементом с номером R.

Требуется найти такие значения номеров элементов L, M, R, где
0 < L < M < R – 1 (т.е. между элементами с номерами M и R есть ещё как минимум один элемент), чтобы разность суммы элементов подпоследовательности S(M + 1, R) и суммы элементов подпоследовательности S(L, M) была максимальна.

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

Входные данные

Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (5 ≤ N ≤ 10 000 000) – количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

Типовой пример организации данных во входном файле

7

20

4

–2

13

–1

2

–10

При таких входных данных L = 2, M = 3, R = 6. Искомая максимальная разность равна (13 + (–1) + 2) – (4 + (–2)) = 12. Подпоследовательность «–2 13 –1» разбить на две подпоследовательности требуемого вида невозможно.

Ответом является число 12.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

  Задание выполняется с использованием прилагаемых файлов.

Задание выполняется с использованием прилагаемых
файлов.

Пусть S – последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L, R) подпоследовательность, состоящую из идущих подряд элементов, входящих в S, начиная с элемента с номером L и заканчивая элементом с номером R.

Требуется найти такие значения номеров элементов L, M, R, где
0 < L < M < R – 1 (т.е. между элементами с номерами M и R есть ещё как минимум один элемент), чтобы разность суммы элементов подпоследовательности S(L, M) и суммы элементов подпоследовательности S(M + 1, R) была максимальна.

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

Входные данные

Дано два входных файла (файл A и файл B), каждый из которых
в первой строке содержит число N (5 ≤ N ≤ 10 000 000) – количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

Типовой пример организации данных во входном файле

7

–20

3

–1

8

4

–2

10

При таких входных данных L = 2, M = 4, R = 6. Искомая максимальная разность равна (3 + (–1) + 8) – (4 + (–2)) = 8. Подпоследовательность «8 4 –2» разбить на две подпоследовательности требуемого вида невозможно.

Ответом является число 8.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Задание выполняется с использованием прилагаемых
файлов.

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

Определите минимальную суммарную стоимость доставки питания для спортсменов из цеха его подготовки в пункты питания на трассе.

Входные данные

Дано два входных файла (файл A и файл B), каждый из которых
в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество пунктов питания на кольцевой трассе. В каждой из следующих
N строк находится число – количество комплектов питания на пункте (все числа натуральные, количество комплектов питания на каждом пункте не превышает 1000). Числа указаны в порядке расположения пунктов питания спортсменов на трассе, начиная
с первого километра.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

Типовой пример организации данных во входном файле

6

8

20

5

13

7

19

При таких исходных данных, если пункты питания установлены на каждом километре трассы, необходимо открыть мобильный цех подготовки комплектов питания для спортсменов в пункте 6.
В этом случае сумма транспортных затрат составит:

1 ∙ 7 + 0 ∙ 19 + 1 ∙ 8 + 2 ∙ 20 + 3 ∙ 5 + 2 ∙ 13.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Задание выполняется с использованием прилагаемых
файлов.

Во время сессии студенты сдают 4 экзамена, за каждый из которых можно получить от 2 до 5 баллов. Студенты, получившие хотя бы одну «двойку», считаются не сдавшими сессию. Результаты сессии публикуются в виде рейтингового списка, в котором сначала указаны идентификационные номера студентов (ID), сдавших сессию, в порядке убывания среднего балла за сессию, а в случае равенства средних баллов – в порядке возрастания ID. Затем располагаются ID студентов, не сдавших сессию: сначала –получивших одну «двойку», затем – две «двойки», потом ID студентов с тремя «двойками» и, наконец, ID студентов, получивших по 2 балла за каждый из экзаменов. Если студенты имеют одинаковое количество «двоек», то их ID в рейтинге располагаются в порядке возрастания.

Повышенную стипендию получают студенты, занявшие в рейтинговом списке первые 25 % мест, при условии отсутствия у них «двоек». Гарантируется, что без «двоек» сессию сдали не менее 25 % студентов. Найдите ID студента, который занимает последнее место среди студентов с повышенной стипендией, а также ID первого в рейтинговом списке студента, который имеет более двух «двоек».

В ответе запишите два целых положительных числа: сначала ID студента, который занимает последнее место среди студентов с повышенной стипендией, затем ID первого в рейтинговом списке студента, который имеет более двух «двоек».

Входные данные

В первой строке входного файла находится число N, обозначающее количество студентов (целое положительное число, не превышающее 10 000). Каждая из следующих N строк содержит 5 чисел через пробел: ID студента (целое положительное число, не превышающее 100 000) и четыре оценки, полученные им за сессию. Гарантируется, что общее число студентов N кратно 4 и хотя бы один студент имеет более двух «двоек». Во входном файле все ID различны.

Выходные данные

Два натуральных числа: искомые ID студентов в порядке, указанном в условии задачи.

Типовой пример организации данных во входном файле

8

4 4 4 4 4

7 5 5 5 2

10 3 4 4 5

1 4 4 4 3

6 3 5 5 3

2 2 2 2 2

13 2 2 2 3

3 3 3 3 3

При таких исходных данных рейтинговый список ID имеет вид: 4 6 10 1 3 7 13 2. Ответ: 6 13.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Задание выполняется с использованием прилагаемых
файлов.

При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наименьшими номерами. В ответе запишите два целых числа: искомый номер ряда и наименьший номер места в найденной паре. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одна такая пара в зале есть.

Входные данные

В первой строке входного файла находятся три числа: N – количество занятых мест в зале (целое положительное число,
не превышающее 10 000), M – количество рядов (целое положительное число, не превышающее 100 000) и K – количество мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих N строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения M, а второе – K).

Выходные данные

Два целых положительных числа: наибольший номер ряда и наименьший номер места в найденной паре кресел.

Типовой пример организации данных во входном файле

7 7 8

1 1

6 6

5 5

6 7

4 4

2 2

3 3

При таких исходных данных ответом является пара чисел 5 и 6. Условию задачи удовлетворяют места 6 и 7 в ряду 5: перед креслами 6 и 7 нет занятых мест и это первая из двух возможных пар в этом ряду. В рядах 6 и 7 искомую пару найти нельзя.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.