4-й этап Республиканской олимпиады по информатике 2019, 9 класс, *ДЕНЬ 2* Казахстан, Актобе
Задача D. Выбор Айбара
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
У Айбара есть два массива $A$ и $B$, что размер каждого равен $n$. Для каждого $i$, что $(1 <= i <= n)$, Айбар должен выбрать либо $A_i$, либо $B_i$. Он хочет максимизировать произведение суммы выбранных $A_i$ и суммы выбранных $B_j$. Помогите Айбару найти максимальное значение. Гарантируется, что максимальное значение не превосходит $10^9$.
Формат входного файла
Первая строка содержит одно целое число $n$ $(2 <= n <= 1000)$.
Вторая строка содержит $n$ целых чисел $A_1, A_2, A_3,...A_n$ $(1 <= A_i <= 10^9)$.
Третья строка содержит $n$ целых чисел $B_1, B_2, B_3,...B_n$ $(1 <= B_i <= 10^9)$.
Формат выходного файла
Выведите одно целое число -- ответ на задачу.
Система оценки
Данная задача содержит шесть подзадач:
- $2 <= n <= 1000, 1 <= A_i, B_i <= 1$. Оценивается в $8$ баллов.
- $2 <= n <= 15, 1 <= A_i, B_i <= 10^9$. Оценивается в $9$ баллов.
- $2 <= n <= 1000, 1 <= A_i, B_i <= 10^9$ и $A_1 <= A_2 <= ... <= A_n$, $B_1 \ge B_2 \ge ... \ge B_n$ . Оценивается в $10$ баллов.
- $2 <= n <= 1000$, $A_i=B_i$ для всех $i$, сумма всех $A_i$ не больше $10^5$. Оценивается в $18$ баллов.
- $2 <= n <= 100$, сумма всех $A_i$ не больше 300, сумма всех $B_i$ не больше 300. Оценивается в $15$ баллов.
- $2 <= n <= 1000, 1 <= A_i, B_i <= 10^9$. Оценивается в $30$ баллов.
Примеры:
Вход 5 1 4 3 2 5 5 2 2 4 1Ответ
108Вход
2 5 7 3 5Ответ
25Вход
7 1 1 1 1 1 1 1 1 1 1 1 1 1 1Ответ
12
Замечание
В первом сэмпле Айбар выбирает в массиве $A$ позиции 2, 3, 5, а в массиве $B$ позиции 1 и 4. Тогда ответ $(4 + 3 + 5) * (5 + 4)=108$.
комментарий/решение(1) Проверить мое решение
Задача E. НурлашКО
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
АланашКО и НурлашКО играют с графом, и им нужна Ваша помощь. Игра начинается с ориентированного ациклического графа $G$, состоящий из $n$ вершин, без ребер, во время игры игроки выполняют $q$ операций. Операции бывают следующих типов:
- Добавить ориентированное ребро из вершины $u_i$ в вершину $v_i$.
- Вывести $x_i$, если существует ориентированный путь из вершины 1 в вершину $x_i$, иначе $0$.
Формат входного файла
Первая строка входных данных содержит три целых числа $n$, $q$ и $t$ $(1 <= n, q <= 10^6, 0 <= t <= 1)$ — количество вершин, количество операций и константное число. Каждая из следующих $q$ строк содержит описание одного запроса.
- Запросы первого типа заданы в формате: $1$ $a_i$ $b_i$ $(0 <= a_i, b_i <= 2\cdot10^9)$.
- Запросы второго типа заданы в формате: $2$ $a_i$ $(0 <= a_i <= 2\cdot10^9)$.
$u_i = (a_i \oplus (t*lastans)) \mod n + 1, \quad v_i = (b_i \oplus (t*lastans)) \mod n + 1$
$x_i = (a_i \oplus (t*lastans)) \mod n + 1$
} где $lastans$ — последний ответ на запрос типа $2$ (изначально $lastans$ равен $0$). Здесь $\oplus$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как ^, в Pascal — как $xor$. Операция $a \mod b$ означает взятие остатка от деления $a$ на $b$. Гарантируется, что во входных данных присутствует хотя бы один запрос типа $2$.
Формат выходного файла
Для каждого запроса второго типа выведите ответ в отдельной строке.
Система оценки
Данная задача содержит 5 подзадач, в каждой подзадаче выполняются ограничения из условий:
- Тесты из условий. Оценивается в $0$ баллов.
- $n, q <= 10^3$, $u_i = 1$, $t = 0$. Оценивается в $11$ баллов.
- $n, q <= 10^3$. Оценивается в $18$ баллов.
- $t = 0$. Оценивается в $39$ баллов.
- Ограничения из условия. Оценивается в $32$ баллов.
Примеры:
Вход 5 9 0 2 0 2 1 1 0 1 2 1 1 2 3 1 2 3 2 3 1 1 2 2 3Ответ
1 0 2 0 4Вход
5 9 1 2 0 2 0 1 0 1 2 1 1 0 1 1 0 1 2 1 1 1 2 2 3Ответ
1 0 2 0 4
комментарий/решение(4) Проверить мое решение
Задача F. Сделайте неотрицательным!
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Тима считает массив целых чисел хорошим если все числа в массиве неотрицательные. У Тимы есть массив $a$ состоящий из $n$ целых чисел. Тима хочет сделать его хорошим, для этого он может делать следующую операцию:
- выбрать три целых числа $i,j, x$ такие, что $1 <= i,j <= n, i \ne j, 1 <= x <= 10^9$ и $a_i \ge x$, а затем из числа $a_i$ отнять $x$, а к числу $a_j$ прибавить $x$. Стоимость такой операции $|i - j| \cdot x$ тенге.
Формат входного файла
В первой строке находятся два целых числа $n, type (1 <= n <= 3 \cdot 10^5, 0 <= type <= 1)$.
Во второй строке находятся $n$ целых числа $a_1,a_2, ..., a_n(-10^8 <= a_i <= 10^8)$. Гарантируется, что можно сделать массив $a$ хорошим.
Формат выходного файла
В первой строке выведите минимальное количество тенге, которое необходимо чтобы сделать массив хорошим.
Если $type = 1$, во второй строке выведите одно целое число $k (0 <= k <= 2 \cdot n)$ — количество операции. В следующих $k$ строках выведите по три целых числа $i,j,x(1 <= i,j <= n, i \ne j, 1 <= x <= 10^9)$ — описания операций. Вам не надо минимизировать количество операций, но нужно минимизировать количество потраченных тенге.
Если $type = 0$, то кроме минимального количество тенге, ничего выводить не надо.
Система оценки
Задача состоит из восьми подзадач:
- Примеры из условия. Оценивается в 0 баллов.
- $n <= 10, type = 0, -1 <= a_i <= 1$. Оценивается в 8 баллов.
- $n <= 200, type = 0, -10 <= a_i <= 10, |a_1| + |a_2| + ... + |a_n| <= 400$. Оценивается в 16 баллов.
- $n <= 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 0$. Оценивается в 12 баллов.
- $n <= 2000, type = 0, -1 <= a_i <= 1$. Оценивается в 15 баллов.
- $n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 1$. Оценивается в 13 баллов.
- $n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8$. Оценивается в 15 баллов.
- $n <= 3 \cdot 10^5, type = 1, -10^8 <= a_i <= 10^8$. Оценивается в 21 баллов.
Примеры:
Вход 7 0 1 1 -1 0 -1 1 1Ответ
2Вход
4 1 4 -2 -2 1Ответ
5 3 1 2 2 1 3 1 4 3 1
комментарий/решение Проверить мое решение