Batyr Sardarbekov

Задача №1.

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

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Айбай решил сделать подарок своему лучшему другу, весёлому приятелю и братишке Абару. Он решил подарить ему

$n$ рыбок. Чтобы подарок вышел более красивым он решил сложить рыбки в кучки. Но Абару не любит когда есть две кучки с одинаковым количеством рыбок. На какое максимальное количество кучек Айбай может разбить

$n$ рыбок?

Формат входного файла

Вам дано одно целое число

$n$

$(1 <= n <= 10^9)$ - количество рыбок.

Формат выходного файла

Выведите одно число - максимальное количество кучек.

Примеры:

Вход

Ответ

Вход

Ответ

Вход

Ответ

( 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.

Примеры:

Вход

Ответ

Вход

Ответ

-1

Вход

Ответ

( 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$ равна

Формат входного файла

В первой строке одно число

$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$ баллов.

$n = 4$
$n = 5$
$n = 10$
$n = 11$
$n = 20$
$n = 21$
$n = 2019$
$n = 2020$
$n = 12345$
$n = 123456$

Пример:

Вход

Ответ

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 <= n <= 1000$ , $1 <= a_i <= 1000$ для $1 <= i <= n$ , у каждого работника не больше одного подчиненного | 2 теста.
$1 <= n <= 1000$ , $1 <= a_i <= 1000$ для $1 <= i <= n$ | 2 теста.
$1 <= n <= 1000$ , у каждого работника не больше одного подчиненного | 2 теста.
$1 <= n <= 1000$ | 3 теста.
$1 <= n <= 200000$ , у каждого работника не больше одного подчиненного | 5 тестов.
$1 <= n <= 200000$ | 10 тестов.

Пример:

Вход

7
1 2 1 1 5 6
1 2 3 1 4 3 3

Ответ

Замечание

Ответ в примере

$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 баллов.

Примеры из условии.
$n = 1$ .
$n = 2$ .
Для каждого $i$ выполняется $a_i = b_i = c_i$ .
Для каждого $i$ выполняется $a_i = b_i = c_i$ .
$n = 6$ .
$n = 7$ .
$n = 8$ .
$n = 9$ .
$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$ подзадач, в которых выполняются следующие ограничения:

$n <= 15$ . Оценивается в $12$ баллов.
$a_i \geq a_{i+1}$ для $1 <= i <= n - 1$ . Оценивается в $11$ баллов.
$a_i <= a_{i+1}$ для $1 <= i <= n - 1$ . Оценивается в $11$ баллов.
$k = 1$ . Оценивается в $16$ баллов.
$k <= 100$ . Оценивается в $19$ баллов. Необходимые подзадачи: 4.
Исходные условия задачи. Оценивается в $31$ баллов. Необходимые подзадачи: 1,2,3,4,5.

Примеры:

Вход

6 2
3 1 7 2 1 2

Ответ

Вход

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$ целых чисел — ответы на все запросы.

Примеры:

Вход

Ответ

Вход

6 1
999370245 75 860 26427 218288294 917
1 6

Ответ

731295209

( Batyr Sardarbekov )
комментарий/решение олимпиада