Temirlan Satylkhanov


Задача №1. (Тима и Рама) На доске в ряд написано $N$ целых чисел. Темірлан и Рамазан играют в следующую игру:

Пока Темірлан отошел, Рамазан хочет стереть ровна $K$ чисел. Он может стереть любые числа. Когда Темірлан вернется, они начнут играть как обычно, но на доске будет написано $N-K$ чисел.
Для каждого из $Q$ чисел $K_1,K_2, ..., K_Q$, Рамазан хочет узнать, какое значение у последнего оставшегося числа, если он заранее сотрет $K_i$ чисел, и оба игрока играют оптимально?
Формат входных данных:
В первой строке находится одно целое число $N$.
Во второй строке находятся $N$ целых числа $A_1,A_2,...,A_N (1 \le A_i \le 10^6)$ --- числа написанные на доске.
В третьей строке находится одно целое число $Q$.
В четвертой строке находятся $Q$ целых числа $K_1,K_2,...,K_Q(0 \le K_i \le N - 1)$.
Формат выходных данных:
Выведите через пробел $Q$ чисел, $i$-е из них, значения последнего оставшегося числа, если Рамазан заранее сотрет $K_i$ чисел.
Примеры:
1.Вход:
4
1 4 2 3
4
0 1 2 3
Ответ:
1 3 3 4
2.Вход:
3
5 5 5
3
0 1 2
Ответ:
5 5 5
3.Вход:
6
2 7 5 4 8 10
3
3 5 2
Ответ:
7 10 7
Замечание:
В первом тесте при $K=3$, Рамазану выгодно стереть первое,второе и четвертое числа.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:
( Temirlan Satylkhanov )
комментарий/решение олимпиада
Задача №2. (Тима и Рама) На доске в ряд написано $N$ целых чисел. Темірлан и Рамазан играют в следующую игру:

Пока Темірлан отошел, Рамазан хочет стереть ровна $K$ чисел. Он может стереть любые числа. Когда Темірлан вернется, они начнут играть как обычно, но на доске будет написано $N-K$ чисел.
Для каждого из $Q$ чисел $K_1,K_2, ..., K_Q$, Рамазан хочет узнать, какое значение у последнего оставшегося числа, если он заранее сотрет $K_i$ чисел, и оба игрока играют оптимально?
Формат входных данных:
В первой строке находится одно целое число $N$.
Во второй строке находятся $N$ целых числа $A_1,A_2,...,A_N (1 \le A_i \le 10^6)$ --- числа написанные на доске.
В третьей строке находится одно целое число $Q$.
В четвертой строке находятся $Q$ целых числа $K_1,K_2,...,K_Q(0 \le K_i \le N - 1)$.
Формат выходных данных:
Выведите через пробел $Q$ чисел, $i$-е из них, значения последнего оставшегося числа, если Рамазан заранее сотрет $K_i$ чисел.
Примеры:
1.Вход:
4
1 4 2 3
4
0 1 2 3
Ответ:
1 3 3 4
2.Вход:
3
5 5 5
3
0 1 2
Ответ:
5 5 5
3.Вход:
6
2 7 5 4 8 10
3
3 5 2
Ответ:
7 10 7
Замечание:
В первом тесте при $K=3$, Рамазану выгодно стереть первое,второе и четвертое числа.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:
( Temirlan Satylkhanov )
комментарий/решение олимпиада
Задача №3. 

Задача E. Na2a и уравнение

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

Na2a много баловался на уроке информатики, и учитель в наказание ему придумал следующую задачу. Найти неотрицательное целое число $x$, такое что ($a_1 \oplus x) + (a_2 \oplus x) + ... + (a_n \oplus x) = S$, где $a_1,...,a_n,S$ — заданные числа. Здесь $\oplus$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как <<$\string^$>>, в Pascal — как <>. Помогите Na2a решить данное уравнение.
Формат входного файла
В первой строке находятся два целых числа $n$, $S (1 \le n \le 10^5, 0 \le S \le 10^{12})$. Во второй строке находятся $n$ целых числа $a_1$, $a_2$, ..., $a_n(0 \le a_i \le 10^{12})$.
Формат выходного файла
Выведите -$1$, если уравнение не имеет неотрицательных решений. Иначе выведите такое $x(x \ge 0)$, что описанное в условии равенство выполняется. Если существует несколько ответов, выведите любой из них.
Система оценки
Данная задача содержит пять подзадач, в каждой подзадаче выполняются ограничения из условии и:
  1. $n \le 1000, a_i,s \le 1000$. Оценивается в $7$ баллов.
  2. $n = 2, a_i,s \le 10^{12}$. Оценивается в $22$ баллов.
  3. $n \le 10^4, a_i,s \le 10^6$. Оценивается в $20$ баллов.
  4. $n \le 10^5, a_i,s \le 5 \cdot 10^7$. Оценивается в $16$ баллов.
  5. $n \le 10^5, a_i,s \le 10^{12}$. Оценивается в $35$ баллов.
Пример:
Вход
3 4
1 2 3
Ответ
2
\Note Таблица для исключающего ИЛИ.\\ 1 $xor$ 1 = 1, 1 $xor$ 0 = 1\\ 0 $xor$ 1 = 1, 0 $xor$ 0 = 0\\ Например, если $X$ = $109_{10}$ = $1101101_{2}$, $Y$ = $41_{10}$ = $101001_{2}$ тогда: $X$ $\oplus$ $Y$ = $68_{10}$ = $1000100_{2}$. ( Temirlan Satylkhanov )
комментарий/решение олимпиада
Задача №4. 

Задача F. Тренерский выбор Тимы

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

Тима с недавних пор начал тренировать баскетбольные команды. Капитаном команды всегда выбирается игрок с максимальным ростом. Также он придумал свою формулу несовместимости игроков в одной команде. Формула зависит от роста всех игроков в команде. Несовместимость игроков в одной команде равняется сумме разниц роста между всеми игроками и ростом капитана. Более формально, пусть $h_1, h_2, ... , h_m$ это рост игроков команды, $mx = max(h_1, h_2, ..., h_m)$, тогда несовместимость = $\sum_{i=1}^{m} mx$-$h_i$. У Тимы есть $n$ игроков выстроенных в ряд, $i$-й из них имеет рост $a_i$. Он хочет разбить всех на $k$ команд, каждый игрок должен быть в ровно одной команде и команда должна состоять из игроков, которые составляют непрерывный отрезок в ряду. Тима хочет собрать команды так, чтобы суммарная несовместимость была минимальной. Помогите Тиме разбить на команды оптимально.
Формат входного файла
Первая строка входных данных содержит два целых чисел $n$ и $k$ ($1 \le n \le 10^5$, $1 \le k \le min(n, 20)$) — количество игроков в ряду и количество команд. Вторая строка содержит $n$ целых чисел $a_i$ ($1 \le a_i \le 10^6$) — рост $i$-го игрока слева в ряду в сантиметрах.
Формат выходного файла
Выведите единственное целое число — ответ на задачу.
Система оценки
Данная задача содержит шесть подзадач, в каждой подзадаче выполняются ограничения из условий:
  1. $n \le 100$, $k = 1$. Оценивается в $5$ баллов.
  2. $n \le 2000$. Оценивается в $11$ баллов.
  3. $k = 2$. Оценивается в $8$ баллов.
  4. $k = 3$. Оценивается в $15$ баллов.
  5. $a_i \le a_{i+1}$, для всех $1 \le i < n$. Оценивается в $19$ баллов.
  6. Ограничения из условия задачи. Оценивается в $42$ баллов.
Пример:
Вход
7 3
6 4 1 5 3 2 2
Ответ
7
Вход
5 2
4 1 5 5 6
Ответ
5
Вход
9 2
3 7 4 1 3 2 4 6 7
Ответ
22
( Temirlan Satylkhanov )
комментарий/решение олимпиада
Задача №5. 

Задача B. Яблоки

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

Тима и его $N - 1$ друзей собирали яблоки. Для удобства пронумеруем всех числами от $1$ до $N$. У Тимы номер $1$. Тима заметил, что у него яблок больше чем у его друзей, и решил поделиться своими яблоками. Он дал всем остальным столько яблок, сколько у них было. Т.е если у кого-то было $X$ яблок, то Тима дал ему еще $X$ яблок. Затем человек с номером $2$ дал всем столько, сколько у них имелось на тот момент. И так далее до $N$-го человека. И в результате у всех оказалось одинаковое количество яблок. Тима хочет знать сколько яблок было у каждого в начале. Он помнит, что в начале у него было $A_1$ яблок.
Формат входного файла
В первой строке входных данных записано одно целое число $T(1\le T \le 1000)$ - количество тестов. В следующих $T$ строках находится по два целых числа $N$ ($1 \le N \le 50$),$1\le A_1\le 10^{16}$.
Формат выходного файла
Выведите $T$ — строк, в каждой строке выведите $-1$ если такое случае невозможно. Иначе выведите $N$ чисел $A_1,A_2, .., A_N$. Если существует несколько возможных ответов, выведите любой из них.
Система оценки
Данная задача содержит четыре подзадачи:
  1. $1 \le T \le 50, N = 2, 1 \le A_1 \le 10^6$. Оценивается в $10$ баллов.
  2. $1 \le T \le 50, N = 3, 1 \le A_1 \le 10^9 $. Оценивается в $15$ баллов.
  3. $T = 1, 1 \le N \le 50, 1 \le A_1 \le 10^5$. Оценивается в $30$ баллов.
  4. $1 \le T \le 1000, 1 \le N \le 50, 1 \le A_1 \le 10^{16}$. Оценивается в $45$ баллов
Пример:
Вход
2
3 13
2 10
Ответ
13 7 4 
10 6 
Замечание
Первый тест: В начале 13, 7, 4. После 1-го : 2, 14, 8. После 2-го : 4, 4, 16. После 3-го: 8,8,8. ( Temirlan Satylkhanov )
комментарий/решение олимпиада
Задача №6. 

Задача E. Перевороты

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

На столе подряд лежат $K$ листов бумаги. Дано число $N$. На каждом листе записаны все числа от 1 до $N$ ровно по одному разу, но некоторые из них записаны на видимой стороне, а остальные на обратной. Ваша задача - перевернуть некоторые листы так, чтобы максимизировать количество различных чисел на видимых сторонах.
Формат входного файла
На первой строке даны $N$ и $K$, так чтобы $N \times K\le 10^6$ при этом $ N \ge 1 $ и $K \ge 1$. На следующих $K$ строках идут описания листов. На $i+1$ строке, первое число это $m$ ($0 \le m \le N$) — количество чисел записанных на видимой стороне $i$-ого листа бумаги. Далее идут $m$ чисел которые написаны на видимой стороне $i$-го листа, каждый от $1$ до $N$.
Формат выходного файла
Выведите строку состоящий из $K$ символов. $i(1 \le i \le K)$ символ равняется 1 если надо перевернут, иначе 0. Если существует несколько ответов, вывести любой.
Система оценки
Данная задача содержит пять подзадач:
  1. $1 \leq N \leq 10$, $1 \le K \le 10$. Оценивается в $11$ баллов.
  2. $1 \leq N \le K$. Оценивается в $8$ баллов.
  3. $1 \leq N \leq 100$. Оценивается в $15$ баллов.
  4. $1 \leq N \times K \leq 5 \cdot 10^4$. Оценивается в $30$ баллов.
  5. $1 \leq N \times K \leq 10^6 $. Оценивается в $36$ баллов.
Примеры:
Вход
5 4
2 1 3
2 3 4
2 2 4
3 1 2 3
Ответ
1111
Вход
6 2
3 1 3 4
3 1 2 4
Ответ
01
( Temirlan Satylkhanov )
комментарий/решение олимпиада
Задача №7. 

Задача G. Секретные алгоритмы

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

В стране Timart есть $N$ городов и $M$ двусторонних дорог. Города пронумерованы от $1$ до $N$. Известно, что с каждого города можно добраться до любого другого по существующим дорогам. Андрей спрятал свитки с секретными алгоритмами в городах Timart. В $i$-ом городе хранится $A_i$ свитков. Рамазан хочет украсть эти свитки. Он может украсть все свитки из города, в котором он находится. Рамазан может начать воровать с любого города. Чтобы не быть пойманным, он не будет использовать одну дорогу два раза подряд. Свитки каждого города можно украсть не более одного раза, посещать города можно по несколько раз. Помогите Рамазану украсть как можно больше свитков.
Формат входного файла
В первой строке входных данных содержится два целых числа $N$, $M$ ($1 \le N \le 5 \cdot 10^5$, $0 \le M \le 5 \cdot 10^5$). Во второй строке находятся $N$ целых чисел $A_1, A_2, \ldots, A_N$, где $A_i$ — количество свитков в $i$-ом городе. В следующих $M$ строках содержится по $2$ целых положительных числа, разделенных пробелом, $u_i$, $v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$)— дорога соединяющая города $u_i$ и $v_i$. Известно, что между двумя городами не может быть больше одной дороги, и что никакая дорога не соединяет город с самим собой. Гарантируется, что между любыми двумя городами существует путь состоящий из заданных дорог
Формат выходного файла
Выведите одно целое число — максимальное количество свитков, которое может украсть Рамазан.
Система оценки
Данная задача содержит пять подзадач:
  1. $1 \le N \le 100$,$M = \frac{N \cdot (N - 1)}{2}$, $1 \le A_i \le 300$, для всех $1 \le i \le N$. Оценивается в $7$ баллов.
  2. $1 \le N \le 12$, $0 \le M \le 66$, $1 \le A_i \le 300$, для всех $1 \le i \le N$. Оценивается в $12$ баллов.
  3. $1 \le N \le 10^5$, $M = N - 1$, $1 \le A_i \le 10^9$, для всех $1 \le i \le N$. Оценивается в $12$ баллов.
  4. $3 \le N \le 10^5$, $M = N$, $1 \le A_i \le 10^9$, для всех $1 \le i \le N$. Оценивается в $25$ баллов.
  5. $1 \le N \le 5 \cdot 10^5$, $0 \le M \le 5 \cdot 10^5$, $1 \le A_i \le 10^9$, для всех $1 \le i \le N$. Оценивается в $44$ балла.
Пример:
Вход
8 8
1 2 3 4 5 6 7 8
1 2
2 3
2 4
2 5
5 6
6 7
7 8
8 5
Ответ
35
( Temirlan Satylkhanov )
комментарий/решение олимпиада
Задача №8. 

Задача H. Тима и сумма степеней

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

У Тимы есть целое число $N$ и массив $A$ из $N$ целых чисел. Также у него есть два целых числа $M$ и $K$. Для каждого $i$ от $1$ до $N$-$M$+$1$ Тима хочет посчитать значение выражения $1^K \cdot A_{i} + 2^K \cdot A_{i + 1} + \cdots + M^K \cdot A_{i + M - 1}$. Помогите ему решить эту задачу.
Формат входного файла
В первой строке находятся три целых числа $N$($1 \le N \le 10^5$),$M$($1 \le M \le N$) и $K$($0 \le K \le 20$). Во второй строке находятся $N$ целых числа $A_1,A_2, \cdots, A_N$ ($1 \le A_i \le 10^9$).
Формат выходного файла
Выведите $N$-$M$+$1$ строк, в $i$-ой строке выведите остаток $1^K \cdot A_{i} + 2^K \cdot A_{i + 1} + \cdots + M^K \cdot A_{i + M - 1}$. при делении на $10^9 + 7$.
Система оценки
Данная задача содержит пять подзадач:
  1. $1 \le N \le 100, 0 \le K \le 3,1 \le A_i \le 10$. Оценивается в $7$ баллов.
  2. $1 \le N \le 10^4, 0 \le K \le 20,1 \le A_i \le 10^9$. Оценивается в $12$ баллов.
  3. $1 \le N \le 10^5, 0 \le K \le 1,1 \le A_i \le 10^9$. Оценивается в $13$ баллов.
  4. $1 \le N \le 10^5, K = 2,1 \le A_i \le 10^9$. Оценивается в $20$ баллов.
  5. $1 \le N \le 10^5, 0 \le K \le 20,1 \le A_i \le 10^9$. Оценивается в $48$ баллов
Примеры:
Вход
5 3 2
1 2 3 4 5
Ответ
36
50
64
Вход
3 2 0
7 3 2
Ответ
10
5
Замечание
Пояснение к примеру 1: При $i = 1$, $1^K \cdot A_1 + 2^K \cdot A_2 + 3^K \cdot A_3$ = $1^2 \cdot 1 + 2^2 \cdot 2 + 3^2 \cdot 3 = 1 + 8 + 27 = 36$. При $i = 2$, $1^K \cdot A_2 + 2^K \cdot A_3 + 3^K \cdot A_4$ = $1^2 \cdot 2 + 2^2 \cdot 3 + 3^2 \cdot 4 = 50$. При $i = 3$, $1^K \cdot A_3 + 2^K \cdot A_4 + 3^K \cdot A_5$ = $1^2 \cdot 3 + 2^2 \cdot 4 + 3^2 \cdot 5 = 64$. ( Temirlan Satylkhanov )
комментарий/решение олимпиада