Если вас интересует математика, то эта задача для вас.
Будем называть целое число $$$n$$$ $$$k$$$-степенным, если его можно разложить в сумму различных степеней числа $$$k$$$, то есть если $$$n$$$ представимо в виде $$$n = k^{a_1} + k^{a_2} + \ldots + k^{a_d}$$$, где все $$$a_i$$$ целые и $$$a_i \ne a_j$$$ для всех $$$i \ne j$$$.
Ответьте на множество запросов: какое минимальное целое число, большее либо равное $$$n_i$$$, является $$$k_i$$$-степенным?
Первая строка ввода содержит целое число $$$q$$$ — количество запросов, на которые вам предстоит ответить ($$$1 \le q \le 10^5$$$).
Каждая из следующих $$$q$$$ строк содержит два целых числа $$$n_i$$$ и $$$k_i$$$, описывающие $$$i$$$-й запрос ($$$1 \le n_i \le 10^9$$$; $$$2 \le k_i \le 10^9$$$).
Выведите $$$q$$$ строк, в $$$i$$$-й из которых выведите минимальное $$$k_i$$$-хорошее число, большее либо равное $$$n_i$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | – | примеры из условия | полная | |
| 1 | 6 | $$$n_i \le 10^5$$$, $$$k_i = 2$$$ для всех $$$i$$$ | первая ошибка | |
| 2 | 9 | $$$n_i \le k_i$$$ для всех $$$i$$$ | первая ошибка | |
| 3 | 10 | $$$q = 1$$$; $$$n_i \le 10^5$$$ для всех $$$i$$$ | полная | |
| 4 | 11 | $$$n_i \le 10^5$$$, $$$k_i = 10$$$ для всех $$$i$$$ | первая ошибка | |
| 5 | 13 | $$$n_i \le 10^5$$$ для всех $$$i$$$; $$$k_i = k_j$$$ для всех $$$i, j$$$ | 1, 4 | первая ошибка |
| 6 | 16 | $$$q \le 500$$$; $$$k_i \ge 20$$$ для всех $$$i$$$ | первая ошибка | |
| 7 | 35 | без дополнительных ограничений | 0 – 7 | первая ошибка |
71 22 36 513 1014 33620 1210000 3
1 3 6 100 27 20736 19683
После тяжелого контеста бывает полезно выпить немного кофе. У настоящих программистов есть множество различных сортов кофе, которые постепенно добавляются в одну кружку. При этом мы будем рассматривать кофе с определенной особенностью: разные сорта кофе держатся в кружке «слоями» и не перемешиваются.
Напиток из таких сортов кофе можно описать следующим образом: всего в кружку налито $$$n$$$ сортов, $$$i$$$-й сорт характеризуется уровнем крепости $$$p_i$$$ и высотой слоя, который он занимает в кружке, $$$h_i$$$. При этом если $$$i \lt j$$$, то слой кофе $$$i$$$-го сорта находится ниже кофе $$$j$$$-го сорта. Также известно, что высота кружки равна $$$\sum\limits_{i=1}^n h_i$$$, то есть верхний край самого верхнего слоя кофе находится ровно на уровне верхней границы кружки.
Для разнообразия иногда хочется получить из такого «коктейля» напиток определенного суммарного уровня крепости. Суммарный уровень крепости определяется как среднее взвешенное уровней налитых в кружку сортов, то есть как $$$$$$P = \frac{\sum\limits_{i=1}^n p_i \cdot h_i}{\sum\limits_{i=1}^n h_i} \text{.}$$$$$$
Чтобы как-то изменять $$$P$$$, можно
При выпивании какого-то количества кофе из одного слоя высота этого слоя уменьшается на соответствующую величину, а все верхние слои опускаются на ту же величину вниз.
Ваша задача — ответить на запросы вида: можно ли из текущего напитка сделать напиток крепости $$$t_i$$$, и если можно, то какая минимальная высота трубочки для этого понадобится. Поскольку идеально точную необходимую высоту трубочки вычислить может быть сложно, достаточно определить минимальное количество верхних слоев кофе, достаточное, чтобы, отпив какое-то количество кофе из некоторых из них, можно было добиться суммарной крепости напитка $$$t_i$$$.
В первой строке ввода даны два целых числа $$$n$$$ и $$$q$$$ — количество слоев кофе в кружке и количество запросов ($$$1 \le n, q \le 2 \cdot 10^5$$$).
Следующие $$$n$$$ строк содержат по два целых числа $$$p_i$$$ и $$$h_i$$$ — уровень крепости и высоту $$$i$$$-го снизу кружки слоя кофе ($$$1 \le p_i, h_i \le 10^9$$$). Гарантируется, что сумма $$$p_i \cdot h_i$$$ по всем $$$i$$$ не превосходит $$$10^{18}$$$.
В $$$i$$$-й из следующих $$$q$$$ строк дано единственное целое число $$$t_i$$$, определяющее $$$i$$$-й запрос ($$$1 \le t_i \le 10^9$$$).
Выведите $$$q$$$ строк, в $$$i$$$-й из которых содержится единственное целое число от $$$0$$$ до $$$n$$$ — ответ $$$i$$$-й запрос. Если для какого-то запроса ответ такой, что нельзя добиться требуемого уровня крепости, выведите в качестве ответа на этот запрос число $$$-1$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Обратите внимание, что прохождение тестов из условия не является необходимым для тестирования на некоторых группах тестов.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке | |
| 0 | – | примеры из условия | полная | ||
| 1 | 5 | $$$q \le 100$$$; $$$n \le 15$$$; $$$p_i, h_i \le 100$$$ | 0 | полная | |
| 2 | 5 | $$$n, q \le 500$$$ | 0, 1 | первая ошибка | |
| 3 | 7 | $$$n, q \le 2000$$$ | 0 – 2 | первая ошибка | |
| 4 | 8 | $$$n, q \le 5000$$$ | 0 – 3 | первая ошибка | |
| 5 | 15 | $$$p_i \le p_j$$$ для $$$i | lt; j$$$ | первая ошибка | |
| 6 | 10 | $$$h_i = h_j$$$ для любых $$$i, j$$$; есть не более двух различных $$$p_i$$$ | первая ошибка | ||
| 7 | 10 | $$$h_i = h_j$$$ для любых $$$i, j$$$ | 6 | первая ошибка | |
| 8 | 15 | $$$p_i \le 10^5$$$ | 0, 1 | первая ошибка | |
| 9 | 25 | без дополнительных ограничений | 0 – 8 | первая ошибка |
3 41 13 72 41234
2 2 3 -1
Для примера из условия:
На клетчатой доске размером $$$n \times m$$$, состоящей из $$$n$$$ строк и $$$m$$$ столбцов, в клетке $$$(r, c)$$$, то есть на пересечении $$$r$$$-й сверху строки и $$$c$$$-го слева столбца, расположена фишка. На этой доске вам предстоит сыграть против компьютера в игру, в которой можно перемещать фишку и удалять клетки поля.
Каждый ход устроен следующим образом.
Если компьютер удаляет клетку, на которой находится фишка, игра заканчивается вашей победой. Ваша цель — победить как можно раньше. При этом вы не сообщаете компьютеру свои перемещения, поэтому можете играть нечестно: вместо реального перемещения фишки по полю вы можете следить за всеми возможными ее положениями. Иными словами, если в какой-то момент при удалении клетки $$$(i, j)$$$ существует последовательность перемещений фишки, при которой в данный момент фишка находится в точности в клетке $$$(i, j)$$$, вы можете сообщить компьютеру, что игра завершена, и вы победили.
Разумеется, компьютер следит за соблюдением правил, поэтому если вы сообщаете ему о своей победе при удалении клетки, на которой фишка не могла в этот момент находиться, вы автоматически проигрываете.
Определите как можно меньший номер хода, после которого вы можете сообщить комьютеру о своей победе, то есть после которого фишка могла оказаться на удаляемой клетке. Чем ближе ваш ответ к минимальному возможному, тем больше баллов вы получите.
В единственной строке ввода даны четыре целых числа $$$n$$$, $$$m$$$, $$$r$$$ и $$$c$$$ — размеры доски и координаты изначального расположения фишки ($$$1 \le r \le n \le 1000$$$; $$$1 \le c \le m \le 1000$$$).
Во второй строке ввода дано максимальное количество баллов, которое можно получить за соответствующую группу тестов. Ваше решение это значение может игнорировать.
В следующих $$$n \cdot m$$$ строках даны ходы, которые последовательно собирается сделать компьютер. Описание $$$t$$$-го хода задается тремя целыми числами $$$k_t$$$, $$$i_t$$$ и $$$j_t$$$ — количеством перемещений фишки, которые вам понадобится совершить, и координатами клетки поля, которую после этого требуется удалить ($$$1 \le k_t \le 10^9$$$; $$$1 \le i_t \le n$$$; $$$1 \le j_t \le m$$$).
Гарантируется, что все удаляемые клетки различны, то есть никакая клетка не удаляется дважды.
Выведите одно целое число от $$$1$$$ до $$$n \cdot m$$$ — номер хода, после которого вы сообщите компьютеру о своей победе.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач пройдены с положительным вердиктом.
То есть, если вы проигрываете игру на каком-либо тесте группы, вы получаете вердикт WA за соответствующий тест и $$$0$$$ баллов за всю группу. Иначе, если $$$R(\mathtt{group})$$$ — максимальное число баллов за группу, а $$$j(\mathtt{test})$$$ и $$$p(\mathtt{test})$$$ — ответы на тест программы жюри и вашей программы, соответственно, вы получаете за группу $$$$$$\left\lfloor R(\mathtt{group}) \cdot \min\limits_{\mathtt{test} \in \mathtt{group}} \frac{j(\mathtt{test})}{p(\mathtt{test})} \right\rfloor \text{ баллов.}$$$$$$
Обратите внимание, что прохождение тестов из условия не является необходимым для тестирования на некоторых группах тестов.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | – | примеры из условия | полная | |
| 1 | 7 | $$$k_1 = n + m$$$ | полная | |
| 2 | 6 | $$$k_t = 1$$$ для всех $$$t$$$ | первая ошибка | |
| 3 | 10 | ходы компьютера случайны и равновероятны | 0 | первая ошибка |
| 4 | 14 | $$$(i_t, j_t)$$$ и $$$(i_{t+1}, j_{t+1})$$$ имеют общую сторону для всех $$$t$$$ | 0 | первая ошибка |
| 5 | 11 | $$$k_t \le 2$$$ для всех $$$t$$$ | 2 | первая ошибка |
| 6 | 17 | $$$n = 1$$$ | полная | |
| 7 | 9 | $$$n, m \le 40$$$ | 0 | первая ошибка |
| 8 | 9 | $$$r = c = 1$$$ | полная | |
| 9 | 17 | без дополнительных ограничений | 0 – 8 | первая ошибка |
2 2 1 101 1 12 2 13 2 24 1 2
2
3 3 2 201 2 21 1 21 1 11 2 11 3 11 3 21 3 31 2 31 1 3
9
В первом примере можно, например, первым ходом передвинуть фишку из $$$(1, 1)$$$ в $$$(1, 2)$$$, а вторым — из $$$(1, 2)$$$ в $$$(2, 2)$$$ и затем в $$$(2, 1)$$$, тем самым поместив ее на удаляемую клетку.
Если увлечься темой кодирования информации, можно поймать себя на придумывании совершенно неожиданных алгоритмов. Сегодня вам предстоит разобраться в кодировании массива стеком.
Изначально вам дан пустой стек и пустой массив. Кодом массива $$$a$$$ назовем последовательность действий вида
Например, при выполнении последовательности действий $$$\mathtt{push}(1)$$$, $$$\mathtt{push}(2)$$$, $$$\mathtt{print}$$$, $$$\mathtt{print}$$$, $$$\mathtt{pop}$$$ и $$$\mathtt{print}$$$ в массив оказываются выписаны числа $$$[1, 2, 1, 2, 1]$$$, а на стеке остается лежать только число $$$1$$$. То есть такая последовательность является кодом массива $$$[1, 2, 1, 2, 1]$$$ длины $$$6$$$.
Вам дан массив $$$a$$$ и $$$q$$$ запросов: какой у отрезка массива $$$a$$$ с $$$l_i$$$-го по $$$r_i$$$-й элемент включительно минимальный по количеству действий со стеком код?
Найдите для каждого запроса код соответствующего отрезка массива. Не требуется найти код наименьшей возможной длины, но чем меньше найденный код, тем больше баллов получит ваше решение.
В первой строке ввода даны четыре целых числа $$$n$$$ и $$$q$$$ — длина массива $$$a$$$, про отрезки которого спрашивается в запросах, количество запросов, а также максимальный балл за тест и параметр $$$\gamma$$$, указанный в системе оценивания, которые ваше решение может игнорировать $$$(1 \le n \le 2000$$$; $$$1 \le q \le 10^4$$$).
Во второй строке перечислены $$$n$$$ целых чисел $$$a_i$$$ — элементы массива $$$a$$$ ($$$1 \le a_i \le 10^9$$$).
В $$$i$$$-й из следующих $$$q$$$ строк даны два целых числа $$$l_i$$$ и $$$r_i$$$ — границы отрезка из $$$i$$$-го запроса ($$$1 \le l_i \le r_i \le n$$$).
Для каждого запроса выведите в отдельной строке целое число $$$k$$$ от $$$1$$$ до $$$n + 1$$$ — количество действий в вашем коде соответствующего отрезка массива, после чего в следующей строке выведите через пробел $$$k$$$ целых чисел, описывающих эти действия в порядке их выполнения:
Если в результате выполнения выведенных действий происходит попытка снять число с вершины пустого стека или в конце не получается массив, равный заданному отрезку массива $$$a$$$, ваше решение получает вердикт Wrong Answer. Также вы получите вердикт Wrong Answer, если в вашем коде будет больше $$$n + 1$$$ действия.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач пройдены с положительным вердиктом. То есть, если вы получаете вердикт WA на каком-либо тесте в группе, вы получаете $$$0$$$ баллов за всю группу. Если все тесты группы пройдены с положительным вердиктом, вы получаете сумму баллов за все тесты в группе.
Для каждой подзадачи даны общие для тестов этой подзадачи ограничения и параметр $$$\gamma$$$, показывающий, насколько близкое к ответу жюри решение будет засчитываться на ненулевой балл.
Если ваше решение для $$$i$$$-го запроса в конкретном тесте строит код из $$$p_i$$$ действий, а решение жюри строит код из $$$j_i$$$ действий, то за этот тест ваше решение получает $$$$$$\max\left(0, \mathtt{score} - \max\left(0, \max\limits_{i=1}^q \left\lfloor\frac{p_i - j_i}{\gamma}\right\rfloor\right)\right) \text{ баллов,}$$$$$$ где $$$\mathtt{score}$$$ — максимальный балл за этот тест. Иными словами, за каждые $$$\gamma$$$ действий свыше решения жюри в каком-либо из запросов вы теряете один балл за тест.
Обратите внимание, что прохождение тестов из условия не является необходимым для тестирования на некоторых группах тестов.
| Подзадача | Баллы | Ограничения | $$$\gamma$$$ | Необходимые подзадачи | Информация о проверке |
| 0 | $$$2 \times 0$$$ | примеры из условия | $$$100$$$ | полная | |
| 1 | $$$4 \times 1$$$ | $$$n \le 10$$$ | $$$10$$$ | 0 | первая ошибка |
| 2 | $$$4 \times 1$$$ | $$$n \le 10$$$ | $$$1$$$ | 0, 1 | первая ошибка |
| 3 | $$$4 \times 1$$$ | $$$n \le 200$$$, $$$q = 1$$$ | $$$1$$$ | первая ошибка | |
| 4 | $$$5 \times 2$$$ | $$$q = 1$$$ | $$$1$$$ | 3 | первая ошибка |
| 5 | $$$5 \times 2$$$ | $$$n \le 200$$$ | $$$1$$$ | 0 – 3 | первая ошибка |
| 6 | $$$4 \times 1$$$ | $$$a_i = 1$$$ для всех $$$i$$$ | $$$100$$$ | первая ошибка | |
| 7 | $$$5 \times 2$$$ | $$$a_i = 1$$$ для всех $$$i$$$ | $$$1$$$ | 6 | первая ошибка |
| 8 | $$$5 \times 3$$$ | $$$a_i \le 2$$$ для всех $$$i$$$; $$$a_i = 2$$$ для не более чем одного $$$i$$$ | $$$50$$$ | 6, 7 | первая ошибка |
| 9 | $$$5 \times 2$$$ | $$$a_i \le 2$$$ для всех $$$i$$$; $$$a_i = 2$$$ для не более чем одного $$$i$$$ | $$$2$$$ | 6 – 8 | первая ошибка |
| 10 | $$$9 \times 2$$$ | $$$q \le 4000$$$ | $$$50$$$ | 0 – 9 | первая ошибка |
| 11 | $$$11 \times 1$$$ | $$$q \le 4000$$$ | $$$2$$$ | 0 – 10 | первая ошибка |
9 4 0 11 2 3 1 2 3 1 2 31 91 64 94 6
6 1 2 3 0 0 0 5 1 2 3 0 0 5 1 2 3 0 0 4 1 2 3 0
12 4 0 11 2 3 4 1 2 3 1 2 3 4 51 122 113 106 7
10 1 2 3 4 0 -1 0 4 5 0 11 2 3 4 1 2 3 1 2 3 4 0 9 3 4 1 2 3 1 2 3 0 3 2 3 0
Некоторые IT-компании проводят ежегодное глобальное мероприятие для сотрудников, на котором подводятся итоги года и обсуждаются ключевые точки в развитии всех проектов. В одной из компаний, на которой мы сфокусируемся, планируется обсуждение $$$k$$$ различных ее проектов.
Для того, чтобы мероприятие прошло интересно, необходимо выбрать хороших спикеров. Есть $$$n$$$ кандидатов, $$$i$$$-й из которых характеризуется своей осведомленностью о проектах — целым числом $$$a_i$$$ от $$$0$$$ до $$$2^k - 1$$$. При этом некоторые из кандидатов дружат между собой, а именно, есть $$$m$$$ пар друзей $$$(f_i, s_i)$$$.
Разумеется, всем хочется, чтобы мероприятие прошло гладко, а для этого необходимо, чтобы все спикеры попарно дружили между собой. При этом, чтобы рассказы спикеров не казались однообразными, важно, чтобы количество выбранных спикеров было как можно больше. Осведомленностью группы размера $$$s$$$, состоящей из кандидатов $$$i_1, i_2, \ldots, i_s$$$, называется $$$a_{i_1} \oplus a_{i_2} \oplus \ldots a_{i_s}$$$, где $$$\oplus$$$ — операция побитового исключающего «ИЛИ». Соответственно, помимо уже описанных критериев, среди всех подходящих групп кандидатов максимального размера необходимо выбрать группу спикеров с максимальной осведомленностью.
Мероприятие уже скоро, поэтому процесс набора кандидатов сейчас в самом разгаре. Ваша задача — выбрать оптимальную по описанным критериям группу спикеров.
Так как список кандидатов еще не утвержден окончательно и может меняться, вам надо решить эту задачу для $$$t$$$ возможных наборов кандидатов.
В первой строке ввода находится одно целое число $$$t$$$ — количество случаев, для которых надо решить задачу ($$$1 \le t \le 120$$$). Далее следует описание $$$t$$$ наборов входных данных.
Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ — количество кандидатов, количество пар друзей среди кандидатов и количество различных тем, которые будут обсуждаться на конференции, соответственно ($$$1 \le n \le 40$$$; $$$0 \le m \le \frac{n \cdot (n - 1)}{2}$$$; $$$0 \le k \le 30$$$).
Во второй строке каждого набора через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — уровни осведомленности о проектах каждого из кандидатов ($$$0 \le a_i \le 2^k - 1$$$).
Далее следуют $$$m$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$f_i$$$ и $$$s_i$$$ — номера кандидатов, образующих $$$i$$$-ю пару друзей ($$$1 \le f_i, s_i \le n$$$; $$$f_i \neq s_i$$$). Гарантируется, что все перечисленные пары друзей различны.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$120$$$.
Для каждого набора входных данных выведите через пробел два числа в отдельной строке — сначала выведите размер максимальной группы спикеров, а затем выведите максимальную возможную осведомленность группы.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Обратите внимание, что прохождение тестов из условия не является необходимым для тестирования на некоторых группах тестов.
Все указанные ограничения распространяются на все наборы входных данных в каждом тесте соответствующей группы.
Последняя подзадача имеет потестовую оценку и содержит $$$7$$$ тестов, каждый из которых независимо оценивается в $$$4$$$ балла.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | – | примеры из условия | полная | |
| 1 | 7 | $$$n \le 20$$$ | 0 | полная |
| 2 | 9 | $$$k = 0$$$ | первая ошибка | |
| 3 | 15 | $$$k \le 3$$$ | 2 | первая ошибка |
| 4 | 18 | $$$n \le 30$$$ | 0, 1 | первая ошибка |
| 5 | 14 | $$$a_i = 0$$$ при $$$2 \le i \le n$$$ | 2 | первая ошибка |
| 6 | 9 | $$$k = 2$$$, $$$n$$$ четное, $$$a_1 = \ldots = a_{\frac{n}{2}} = 1$$$, $$$a_{\frac{n}{2}+1} = \ldots = a_n = 2$$$ | первая ошибка | |
| 7 | $$$7 \times 4$$$ | без дополнительных ограничений | 0 – 6 | первая ошибка |
36 2 41 2 3 4 5 61 23 46 8 81 2 4 8 16 321 22 33 44 55 66 11 31 45 8 61 2 4 8 161 21 31 42 32 42 53 53 4
2 7 3 13 4 15
В примере из условия: