қазақша
русский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$ баллов.
- $n = 4$
- $n = 5$
- $n = 10$
- $n = 11$
- $n = 20$
- $n = 21$
- $n = 2019$
- $n = 2020$
- $n = 12345$
- $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 <= 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Ответ
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 баллов.
- Примеры из условии.
- $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Ответ
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 )
комментарий/решение олимпиада