Batyr Sardarbekov


Задача №1. 

Задача B. Айбай и Абар

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

Айбай решил сделать подарок своему лучшему другу, весёлому приятелю и братишке Абару. Он решил подарить ему $n$ рыбок. Чтобы подарок вышел более красивым он решил сложить рыбки в кучки. Но Абару не любит когда есть две кучки с одинаковым количеством рыбок. На какое максимальное количество кучек Айбай может разбить $n$ рыбок?
Формат входного файла
Вам дано одно целое число $n$ $(1 <= n <= 10^9)$ - количество рыбок.
Формат выходного файла
Выведите одно число - максимальное количество кучек.
Примеры:
Вход
5
Ответ
2
Вход
12345
Ответ
156
Вход
13
Ответ
4
( Batyr Sardarbekov )
комментарий/решение(2) олимпиада
Задача №2. 

Задача D. Лучшие друзья

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

Айбай и Абар играют игру. У них есть два массива целых положительных чисел $a$ и $b$. Айбай может взять два соседних числа из массива $a$ и заменить их суммой этих двух чисел. Например : $[2, 4, 1, 7]$ -> $[2, 5, 7]$. Абар может делать то же самое с массивом $b$. Так как они лучшие друзья, то они хотят, чтобы получившиеся массивы были одинаковыми. Но они очень любят большие массивы, поэтому они хотят, чтобы получившиеся массивы были еще и максимальной длины. Найдите максимальную возможную длину получившихся массивов.
Формат входного файла
В первой строке задано целое число $n$ $(1 <= n <= 300000)$ - длина первого массива. Во второй строке задано $n$ целых чисел $a_{1},a_{2},...,a_{n}$ $(0 <= a_{i} <= 10^9)$ - элементы массива $a$. В третьей строке задано целое число $m$ $(1 <= m <= 300000)$ - длина второго массива. В четвертой строке задано $m$ целых чисел $b_{1},b_{2},...,b_{m}$ $(0 <= b_{i} <= 10^9)$ - элементы массива $b$.
Формат выходного файла
Выведите одно число — максимальную длину полученных массивов после применения операций к массивам $a$ и $b$ таким образом, что они становятся одинаковыми. Если же не существует способа сделать массивы одинаковыми, выведите -1.
Примеры:
Вход
5
11 2 3 5 7
4
11 7 3 7
Ответ
3
Вход
2
1 2
1
100
Ответ
-1
Вход
3
1 2 3
3
1 2 3
Ответ
3
( Batyr Sardarbekov )
комментарий/решение(3) олимпиада
Задача №3. 

Задача I. Контесты

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

У Тимы есть $n$ задач пронумерованных от $1$ до $n$. Сложность задачи с номером $i$ равна $a_i$. Однажды он решил сделать несколько контестов. Один контест состоит из 4 задач разной сложности. Разумеется одну задачу можно использовать только на одном контесте. Помогите ему составить максимальное количество контестов.
Формат входного файла
В первой строке одно число $n$ $(1 <= n <= 300000)$ - количество задач. Во второй строке $n$ целых чисел $a_1, a_2,... a_n$ $(1 <= a_i <= 300000)$ - сложность задач.
Формат выходного файла
В первой строке одно число $k$ $(0 <= k <= n / 4)$- максимальное количество контестов. В следующих $k$ строках по $4$ числа $i_1,\ i_2,\ i_3,\ i_4$ - номера задач контеста. Если возможных ответов несколько, выведите любой из них.
Примеры:
Вход
5
1 1 2 3 4
Ответ
1
2 3 4 5
Вход
10
3 1 4 5 3 2 4 3 5 1
Ответ
2
8 10 7 9
5 2 6 3
( Batyr Sardarbekov )
комментарий/решение(3) олимпиада
Задача №4. 

Задача I. Контесты

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

У Тимы есть $n$ задач пронумерованных от $1$ до $n$. Сложность задачи с номером $i$ равна $a_i$. Однажды он решил сделать несколько контестов. Один контест состоит из 4 задач разной сложности. Разумеется одну задачу можно использовать только на одном контесте. Помогите ему составить максимальное количество контестов.
Формат входного файла
В первой строке одно число $n$ $(1 <= n <= 300000)$ - количество задач. Во второй строке $n$ целых чисел $a_1, a_2,... a_n$ $(1 <= a_i <= 300000)$ - сложность задач.
Формат выходного файла
В первой строке одно число $k$ $(0 <= k <= n / 4)$- максимальное количество контестов. В следующих $k$ строках по $4$ числа $i_1,\ i_2,\ i_3,\ i_4$ - номера задач контеста. Если возможных ответов несколько, выведите любой из них.
Примеры:
Вход
5
1 1 2 3 4
Ответ
1
2 3 4 5
Вход
10
3 1 4 5 3 2 4 3 5 1
Ответ
2
8 10 7 9
5 2 6 3
( Batyr Sardarbekov )
комментарий/решение(3) олимпиада
Задача №5. 

Задача B. Перестановка

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

Постройте пилообразную циклическую перестановку $p$ длины $n$. Перестановка называется циклической тогда и только тогда, когда она состоит из единственного цикла.(То есть в графе с ребрами $i$ - $p_i$ ровно одна связанная компонента). Пилообразная перестановка - перестановка $p$, такая что её члены по очереди возрастают и убывают.($p_1 < p_2 > p_3 < p_4 ...$ или $p_1 > p_2 < p_3 > p_4 ...$)
Формат входного файла
Вам дано одно целое число $n$.
Формат выходного файла
Выведите любую подходящую перестановку.
Система оценки
Данная задача содержит ровно $10$ тестов и каждый оценивается в $10$ баллов.
  1. $n = 4$
  2. $n = 5$
  3. $n = 10$
  4. $n = 11$
  5. $n = 20$
  6. $n = 21$
  7. $n = 2019$
  8. $n = 2020$
  9. $n = 12345$
  10. $n = 123456$
Пример:
Вход
4
Ответ
3 1 4 2 
( Batyr Sardarbekov )
комментарий/решение(15) олимпиада
Задача №6. 

Задача E. Есмахан и стартап

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

Есмахан - начал стартап по разведению моржов. Он нанял $n-1$ работника. Есмахан - сотрудник номер $1$, все остальные пронумерованы от $2$ до $n$. У каждого из работников есть один непосредственный начальник $p_i$. У Есмахан нет начальников. Гарантируется, что значения $p_i$ образуют дерево. Теперь Есмахан должен им заплатить. Работник с номером $i$ хочет получить $a_i$ тенге. Пусть $i$ работник получит $b_i$ тенге, тогда его недовольство будет $|a_i - b_i|$. У Есмахана есть принцип - каждый работник должен получить больше чем любой его подчиненный. Вам нужно распределить зарплаты так чтобы суммарное недовольство было минимально.
Формат входного файла
В первой строке одно целое число $n$ $(1 <= n <= 200000)$. Во второй строке $n - 1$ целых чисел $p_2, p_3, ... p_n$ $(1 <= p_i <= i - 1)$ - номера начальников работников. В третей строке $n$ целых чисел $a_1, a_2, ... a_n$ $(1 <= a_i <= 10^9)$ - ожидания работников.
Формат выходного файла
Выведите одно целое число - минимальное суммарное недовольство работников.
Система оценки
Данная задача содержит ровно $25$ тестов и каждый оценивается в $4$ баллов.
  1. Тест из условия.
  2. $1 <= n <= 1000$, $1 <= a_i <= 1000$ для $1 <= i <= n$, у каждого работника не больше одного подчиненного | 2 теста.
  3. $1 <= n <= 1000$, $1 <= a_i <= 1000$ для $1 <= i <= n$ | 2 теста.
  4. $1 <= n <= 1000$, у каждого работника не больше одного подчиненного | 2 теста.
  5. $1 <= n <= 1000$ | 3 теста.
  6. $1 <= n <= 200000$, у каждого работника не больше одного подчиненного | 5 тестов.
  7. $1 <= n <= 200000$ | 10 тестов.
Пример:
Вход
7
1 2 1 1 5 6
1 2 3 1 4 3 3
Ответ
7
Замечание
Ответ в примере $b={5, 4, 3, 1, 4, 3, 2}$ ( Batyr Sardarbekov )
комментарий/решение(3) олимпиада
Задача №7. 

Задача C. ICPC

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

Новое правило в чемпионате мира по программированию ICPC: можно использовать три компьютера. Давайте посмотрим как это повлияла на одну из сильнейших команд с Казахстана. Кирилл, Айбар и Султан начали писать контест. В контесте всего $n$ задач и длится 5 часов. Они уже оценили время которое они потратят на каждую задачу. Кирилл решает задачу с номером $i$ за $a_i$ минут. Айбар за $b_i$. Султан за $c_i$. Как и всегда нужно решить как можно больше задач с меньшим штрафом. Штраф определяется как сумма времени решения для каждой принятой задачи. Например, если команда сдаст первую задачу на $5$ минуте, а вторую на $10$ минуте то штраф будет равен $5 + 10 = 15$. Вам нужно определить какой самый лучший результат может получить команда.
Формат входного файла
В первой строке дано одно целое числа $n$ ($1 <= n <= 10$) - количество задача на контесте. В следующих $n$ строк даны по три числа $a_i$, $b_i$ и $c_i$ $(1 <= a_i, b_i, c_i <= 500)$ - время которое Кирилл, Айбар и Султан потратят на задачу соответственно.
Формат выходного файла
Выведи максимальное количество задач и минимальный штраф.
Система оценки
Данная задача состоит из $10$ тестов. Каждый тест оценивается в 10 баллов.
  1. Примеры из условии.
  2. $n = 1$.
  3. $n = 2$.
  4. Для каждого $i$ выполняется $a_i = b_i = c_i$.
  5. Для каждого $i$ выполняется $a_i = b_i = c_i$.
  6. $n = 6$.
  7. $n = 7$.
  8. $n = 8$.
  9. $n = 9$.
  10. $n = 10$.
Пример:
Вход
2
1 123 345
300 301 301
Ответ
2 423
( Batyr Sardarbekov )
комментарий/решение(10) олимпиада
Задача №8. 

Задача A. Разделение команды

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

Есть $n$ игроков которые стоят в ряд. Они хотят сыграть в игру. Для этого им нужно разделится на две команды по $k$ человек. У $i$-го игрока $a_i$ уровень игры. Сила команды это сумма уровней всех его участников. Вы можете выбрать $2 * k$ игроков которые будут играть. Но они сами поделятся на команды. В первой команде будут первые $k$ игроков которые стоят ближе к началу ряду. Во второй команде будут последние $k$ игроков. Запишем силу первой команды как $A$ и второй как $B$. Найдите максимальное значение $A - B$. Например, есть $6$ игроков с уровнями $[3, 1, 7, 2, 1, 2]$. Если выбрать игроков с номерами $1, 3, 5 ,6$ то в первой команде будут игроки $1, 3$ и сила команды $A = 3 + 7 = 10$, во второй игроки $5, 6$ и сила команды $B = 1 + 2 = 3$. $A - B = 10 - 3 = 7$.
Формат входного файла
В первой строке два целых числа $n$, $k$ ($1 <= n <= 10^5$, $1 <= k <= \frac{n}{2}$) - колчество игроков и размер команд. Во второй строке $n$ целых чисел $a_1, a_2 \ldots a_n$ ($1 <= a_i <= 10^5$) - уровень игроков.
Формат выходного файла
Выведите максимальное значение $A - B$.
Система оценки
Данная задача содержит $7$ подзадач, в которых выполняются следующие ограничения:
  1. $n <= 15$. Оценивается в $12$ баллов.
  2. $a_i \geq a_{i+1}$ для $1 <= i <= n - 1$. Оценивается в $11$ баллов.
  3. $a_i <= a_{i+1}$ для $1 <= i <= n - 1$. Оценивается в $11$ баллов.
  4. $k = 1$. Оценивается в $16$ баллов.
  5. $k <= 100$. Оценивается в $19$ баллов. Необходимые подзадачи: 4.
  6. Исходные условия задачи. Оценивается в $31$ баллов. Необходимые подзадачи: 1,2,3,4,5.
Примеры:
Вход
6 2
3 1 7 2 1 2
Ответ
7
Вход
5 1
3 4 6 8 9
Ответ
-1
( Batyr Sardarbekov )
комментарий/решение олимпиада
Задача №9. 

Задача C. Тройка

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

Вам дана последовательность чисел $a$ длины $n$ и $q$ запросов. Каждый запрос состоит из двух чисел $l$ и $r$. Для каждого запроса найдите следующие значение: $$ \sum_{i=l}^{r} \sum_{j=l}^{r} \sum_{k=l}^{r} max(a_i, a_j, a_k) - min(a_i, a_j, a_k) $$ Так как ответ может быть большим, выведите его по модулю $10^9 + 7$.
Формат входного файла
В первой строке даны два целых числа $n$ и $q$ $(1 <= n, q <= 10^5)$. В следующей строке даны $n$ целых чисел $a_1, a_2, \ldots a_n$ $(1 <= a_i <= 10^9)$ — последовательность чисел. В следующих $q$ строках даны по два целых числа $l_i, r_i$ $(1 <= l_i <= r_i <= n)$ — описание $i$-го запроса.
Формат выходного файла
Выведите $q$ целых чисел — ответы на все запросы.
Примеры:
Вход
5 5
1 2 3 4 5
1 5
1 3
2 5
2 3
4 4
Ответ
300
36
120
6
0
Вход
6 1
999370245 75 860 26427 218288294 917
1 6
Ответ
731295209
( Batyr Sardarbekov )
комментарий/решение олимпиада