Задача 5. Максимальное произведение ≡

Условие

Задан массив натуральных чисел [a₁, a₂, …, a_n]. Весом массива назовём сумму его элементов.

Необходимо разрезать заданный массив на два непустых массива [a₁, a₂, …, a_i] и [a_i+1, a_i+2, …, a_n] так, чтобы произведение их весов было как можно больше.

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

Формат входных данных

В первой строке входных данных находится целое число n — количество элементов в массиве (2 ≤ n ≤ 2 ⋅ 10⁵). В следующей строке находятся n целых чисел a₁, a₂, …, a_n — элементы массива (1 ≤ a_i ≤ 10⁹).

Формат выходных данных

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

Ограничения

1 ≤ a_i ≤ 10⁹

2 ≤ n ≤ 2 ⋅ 10⁵

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

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

Замечание

Если сделать разрез после первого элемента, произведение весов равно 1 ⋅ (2 + 3) = 5, а если после второго, то (1 + 2) ⋅ 3 = 9

Примеры тестов

3
1 2 3

2

Задача 6. Планировка участка ≡

Условие

Учёные планируют участок для испытательного полигона. Участок должен иметь форму прямоугольника a × b, а полигон должен иметь форму прямоугольника c × d. С точными значениями чисел a, b, c и d ученые пока не определились, однако известно следующее:

• Длины сторон a, b, c, d должны быть натуральными числами и выражаться в километрах.
• Для безопасности эксперимента длина и ширина участка должны отличаться от значения x, то есть должны выполняться неравенства a ≠ x, b ≠ x.
• Участок будет огражден забором, а полигон должен полностью помещаться внутри участка, то есть должны выполняться следующие условия: a > c, b > d.
• Площадь участка, не занятого полигоном, должна быть ровно n квадратных километров, то есть должно выполняться следующее условие: a ⋅ b − c ⋅ d = n.

Учёные хотят понять, сколько у них способов выбрать подходящие значения a, b, c и d.

Требуется написать программу, которая по заданным n и x определяет количество способов выбрать числа a, b, c и d так, чтобы все описанные условия выполнялись.

Формат входных данных

В первой строке ввода содержится два целых числа n и x — площадь свободного участка без полигона и запрещенная длина стороны участка соответственно.

Значение x = 0 означает, что ограничений на длины сторон нет (так как длины сторон должны быть натуральными числами, и, следовательно, больше 0).

Формат выходных данных

В единственной строке выведите количество способов выбрать числа a, b, c и d так, что все описанные условия выполняются.

Ограничения

1 ≤ n ≤ 3000

0 ≤ x ≤ 3000

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

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

Примеры тестов

3 0

1

5 0

5

5 3

2

Задача 7. Банкомат ≡

Условие

Ведётся разработка универсального банкомата, который сможет работать с любой денежной системой. Пусть в денежной системе некоторой страны используются n типов купюр, номиналы которых равны a₁, a₂, …, a_n. При этом все номиналы различны и перечислены в порядке возрастания: если i ≥ 2, то a_i − 1 < a_i, а также a₁ = 1.

Банкомат использует следующий жадный алгоритм для выдачи купюр. Пусть клиент запросил у банкомата сумму c. Изначально есть пустой набор выдаваемых купюр. На каждом шаге алгоритм добавляет в набор купюру максимально возможного номинала так, чтобы сумма номиналов купюр в наборе не превышала c. Когда сумма номиналов купюр в наборе стала равна c, алгоритм останавливается. Отметим, что, поскольку существует купюра с номиналом a₁ = 1, алгоритм всегда заканчивает работу за конечное число шагов.

Чтобы оценить эффективность данного алгоритма, требуется выяснить, какое максимальное число купюр может потребоваться выдать за один раз, если максимальная сумма, которую можно запросить, равна b. Поскольку максимальная сумма может зависеть от категории обслуживания клиента, необходимо ответить на q запросов для сумм b₁, b₂, …, b_q.

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

Формат входных данных

Первая строка содержит целое число n — количество номиналов купюр (1 ≤ n ≤ 200 000).

Вторая строка содержит n различных целых чисел a_i (1 = a₁ < a₂ < … < a_n ≤ 10¹⁸).

Третья строка содержит целое число q — количество запросов (1 ≤ q ≤ 200 000).

Следующие q строк содержат по одному целому числу b_i (1 ≤ b_i ≤ 10¹⁸).

Формат выходных данных

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

Ограничения

1 ≤ n ≤ 200000

1 = a₁ < a₂ < … < a_n ≤ 10¹⁸

1 ≤ q ≤ 200 000

1 ≤ b_i ≤ 10¹⁸

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

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

Замечание

• 2 будет выдано как 1 + 1,
• 8 будет выдано как 5 + 1 + 1 + 1,
• 49 будет выдано как 10 + 10 + 10 + 10 + 5 + 1 + 1 + 1 + 1.

Примеры тестов

4
1 5 10 50
3
2
8
50

2 2
8 4
49 9

Задача 8. Плакаты ≡

Условие

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

Для того, чтобы приветствовать команду, n друзей встанут в круг. Пронумеруем их от 1 до n в порядке их расположения по кругу. Таким образом, для всех i от 1 до n − 1 друзья с номерами i и i + 1 стоят рядом, также рядом стоят друзья с номерами n и 1. У каждого из друзей есть плакат. Каждый плакат характеризуется своей красочностью — целым неотрицательным числом. Плакат у друга с номером i имеет красочность a_i.

Когда поздравление начнётся, некоторые из друзей поднимут свои плакаты и будут показывать их команде. Для того, чтобы члены команды не растерялись и смогли рассмотреть все плакаты, не должно быть четырёх или более стоящих подряд друзей с поднятым плакатом.

Друзья планируют изменять плакаты в процессе встречи. Всего будет внесено q изменений в плакаты. После i-го из них плакат друга с номером p_i будет иметь красочность v_i. После каждого из изменений друзья хотят определить, какую максимальную суммарную красочность могут иметь поднятые плакаты, если нельзя нарушать установленное ограничение.

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

Формат входных данных

Первая строка ввода содержит целое число n (4 ≤ n ≤ 40 000) — количество друзей.

Вторая строка содержит n целых чисел a_i (0 ≤ a_i ≤ 10⁹) — исходные значения красочности плакатов у друзей.

Третья строка содержит одно целое число q (0 ≤ q ≤ 40 000) — количество изменений плакатов, которые вносили друзья.

Каждая из следующих q строк содержит два целых числа p_i и v_i (1 ≤ p_i ≤ n; 0 ≤ v_i ≤ 10⁹) — номер друга, плакат которого изменился, и новая красочность этого плаката.

Формат выходных данных

Выведите q + 1 число. Перед первым изменением, а также после каждого изменения плакатов выведите одно целое число — максимальное суммарное значение красочности поднятых плакатов, если нельзя поднимать больше трёх плакатов подряд.

Ограничения

4 ≤ n ≤ 40 000

0 ≤ a_i ≤ 10⁹

0 ≤ q ≤ 40 000

1 ≤ p_i ≤ n; 0 ≤ v_i ≤ 10⁹

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

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

Пояснения

Перед первым изменением плакаты следует поднять друзьям с номерами 2, 4, 5, 6. Суммарная красочность поднятых плакатов будет равняться 17.

После первого изменения плакат друга с номером 6 имеет красочность 0. Теперь плакаты следует поднять друзьям с номерами 1, 3, 4, 5. Суммарная красочность будет равняться 13.

После второго изменения плакат друга с номером 2 имеет красочность 5. Плакаты следует поднять друзьям с номерами 1, 2, 4, 5. Суммарная красочность будет равняться 15.

Примеры тестов

6
1 2 3 4 5 6
2
6 0
2 5

17
13
15