Processing math: 100%

4-й этап Республиканской олимпиады по информатике 2019, 9 класс, *ДЕНЬ 2* Казахстан, Актобе


Задача D. Выбор Айбара

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

У Айбара есть два массива A и B, что размер каждого равен n. Для каждого i, что (1<=i<=n), Айбар должен выбрать либо Ai, либо Bi. Он хочет максимизировать произведение суммы выбранных Ai и суммы выбранных Bj. Помогите Айбару найти максимальное значение. Гарантируется, что максимальное значение не превосходит 109.
Формат входного файла
Первая строка содержит одно целое число n (2<=n<=1000). Вторая строка содержит n целых чисел A1,A2,A3,...An (1<=Ai<=109). Третья строка содержит n целых чисел B1,B2,B3,...Bn (1<=Bi<=109).
Формат выходного файла
Выведите одно целое число -- ответ на задачу.
Система оценки
Данная задача содержит шесть подзадач:
  1. 2<=n<=1000,1<=Ai,Bi<=1. Оценивается в 8 баллов.
  2. 2<=n<=15,1<=Ai,Bi<=109. Оценивается в 9 баллов.
  3. 2<=n<=1000,1<=Ai,Bi<=109 и A1<=A2<=...<=An, B1B2...Bn . Оценивается в 10 баллов.
  4. 2<=n<=1000, Ai=Bi для всех i, сумма всех Ai не больше 105. Оценивается в 18 баллов.
  5. 2<=n<=100, сумма всех Ai не больше 300, сумма всех Bi не больше 300. Оценивается в 15 баллов.
  6. 2<=n<=1000,1<=Ai,Bi<=109. Оценивается в 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 операций. Операции бывают следующих типов:
  1. Добавить ориентированное ребро из вершины ui в вершину vi.
  2. Вывести xi, если существует ориентированный путь из вершины 1 в вершину xi, иначе 0.
Гарантируется, после операции граф останется ациклическим. Ациклический граф - случай ориентированного графа, в котором отсутствуют ориентированные циклы.
Формат входного файла
Первая строка входных данных содержит три целых числа n, q и t (1<=n,q<=106,0<=t<=1) — количество вершин, количество операций и константное число. Каждая из следующих q строк содержит описание одного запроса.
  1. Запросы первого типа заданы в формате: 1 ai bi (0<=ai,bi<=2109).
  2. Запросы второго типа заданы в формате: 2 ai (0<=ai<=2109).
Обратите внимание, что вершины ui, vi для запросов типа 1 и вершина xi для запросов типа 2 закодированы, и чтобы их получить нужно выполнить соответствующие преобразования: {
ui=(ai(tlastans))modn+1,vi=(bi(tlastans))modn+1

xi=(ai(tlastans))modn+1

} где lastans — последний ответ на запрос типа 2 (изначально lastans равен 0). Здесь обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как ^, в Pascal — как xor. Операция amodb означает взятие остатка от деления a на b. Гарантируется, что во входных данных присутствует хотя бы один запрос типа 2.
Формат выходного файла
Для каждого запроса второго типа выведите ответ в отдельной строке.
Система оценки
Данная задача содержит 5 подзадач, в каждой подзадаче выполняются ограничения из условий:
  1. Тесты из условий. Оценивается в 0 баллов.
  2. n,q<=103, ui=1, t=0. Оценивается в 11 баллов.
  3. n,q<=103. Оценивается в 18 баллов.
  4. t=0. Оценивается в 39 баллов.
  5. Ограничения из условия. Оценивается в 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,ij,1<=x<=109 и aix, а затем из числа ai отнять x, а к числу aj прибавить x. Стоимость такой операции |ij|x тенге.
Помогите Тиме, потратив минимальное количество тенге сделать массив хорошим.
Формат входного файла
В первой строке находятся два целых числа n,type(1<=n<=3105,0<=type<=1). Во второй строке находятся n целых числа a1,a2,...,an(108<=ai<=108). Гарантируется, что можно сделать массив a хорошим.
Формат выходного файла
В первой строке выведите минимальное количество тенге, которое необходимо чтобы сделать массив хорошим. Если type=1, во второй строке выведите одно целое число k(0<=k<=2n) — количество операции. В следующих k строках выведите по три целых числа i,j,x(1<=i,j<=n,ij,1<=x<=109) — описания операций. Вам не надо минимизировать количество операций, но нужно минимизировать количество потраченных тенге. Если type=0, то кроме минимального количество тенге, ничего выводить не надо.
Система оценки
Задача состоит из восьми подзадач:
  1. Примеры из условия. Оценивается в 0 баллов.
  2. n<=10,type=0,1<=ai<=1. Оценивается в 8 баллов.
  3. n<=200,type=0,10<=ai<=10,|a1|+|a2|+...+|an|<=400. Оценивается в 16 баллов.
  4. n<=105,type=0,108<=ai<=108,a1+a2+...+an=0. Оценивается в 12 баллов.
  5. n<=2000,type=0,1<=ai<=1. Оценивается в 15 баллов.
  6. n<=3105,type=0,108<=ai<=108,a1+a2+...+an=1. Оценивается в 13 баллов.
  7. n<=3105,type=0,108<=ai<=108. Оценивается в 15 баллов.
  8. n<=3105,type=1,108<=ai<=108. Оценивается в 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

комментарий/решение Проверить мое решение