Batyr Sardarbekov


Задача №1. 

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

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

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