Вы решили подготовиться к отборочному этапу олимпиады «Когнитивные технологии» и порешать задачи для подготовки.
До олимпиады осталось $$$n$$$ дней, а в архиве прошлых лет есть $$$m$$$ задач. Вы хотите составить план подготовки такой, чтобы было верно следующее:
- В течение каждого дня подготовки должно быть запланировано решение хотя бы одной задачи;
- В каждый последующий день, за исключением первого, вы должны решать не меньше задач, чем в предыдущий;
- Суммарно решено $$$m$$$ задач.
Формально, вам нужно заполнить массив $$$a$$$, состоящий из $$$n$$$ значений, где $$$a_i$$$ будет равняться количеству задач, которое вы планируете решить в день подготовки под номером $$$i$$$ ($$$1 \le i \le n$$$).
Для каждой пары дней с номерами $$$i$$$, $$$j$$$, такими, что $$$i \le j$$$, должно быть верно $$$1 \le a_i \le a_j$$$.
Например, пусть до олимпиады осталось $$$3$$$ дня и у вас есть $$$7$$$ задач в архиве. Тогда можно описать план подготовки как $$$a$$$ = [$$$1, 3, 3$$$].
Если составить план, удовлетворяющий условиям, описанным выше, невозможно — выведите -1.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Далее следуют описания наборов.
В первой строке даны ровно два целых числа $$$n$$$ ($$$1 \le n \le 10^5$$$) и $$$m$$$ ($$$1 \le m \le 10^5$$$) — количество дней до олимпиады и количество задач в архиве соответственно.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных в отдельной строке выведите:
- ровно $$$n$$$ целых чисел, разделенных пробелами — план подготовки к олимпиаде, если его возможно составить;
- -1 иначе.
Вы можете вывести любой подходящий план.
43 74 410 25 15
1 3 3 1 1 1 1 -1 1 2 3 4 5
Однажды ночью Рафаэль, Кейси Джонс и Эйприл О'Нил попали в засаду банды Пурпурные драконы. Всего бандитов $$$2 n$$$. Рафаэль быстро оценил обстановку и выяснил, что готов сразить $$$i$$$-го ($$$1 \le i \le 2 n$$$) бандита за время $$$a_i$$$. То же самое сделал Кейси Джонс, он готов сразить $$$i$$$-го ($$$1 \le i \le 2 n$$$) бандита за время $$$b_i$$$.
Парни уже готовы броситься в бой, но кто-то должен защищать Эйприл О'Нил, поэтому сражаться с бандитами придётся последовательно. Кроме того, чтобы никто не обиделся, мальчики решили поделить бандитов поровну. Сначала Рафаэль выбирает $$$n$$$ бандитов и поочерёдно расправляется с ними, затем Кейси Джонс поочерёдно расправляется с оставшимися $$$n$$$ бандитами. Обратите внимание, что каждого бандита нужно сразить ровно один раз.
Друзья очень торопятся посмотреть сериал про супергероев, поэтому хотят закончить битву как можно скорее. За какое минимальное суммарное время они справятся?
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Далее следуют описания наборов.
В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество бандитов, которых должны сразить Рафаэль и Кейси Джонс по отдельности.
Во второй строке даны $$$2 \cdot n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2 n}$$$ ($$$1 \le a_i \le 10^9$$$) — время, за которое Рафаэль сразит каждого бандита.
В третьей строке даны $$$2 \cdot n$$$ целых чисел $$$b_1, b_2, \ldots, b_{2 n}$$$ ($$$1 \le b_i \le 10^9$$$) — время, за которое Кейси Джонс сразит каждого бандита.
Гарантируется, что сумма $$$n$$$ по всем запросам не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите единственное целое число — минимальное суммарное время, за которое Рафаэль и Кейси Джонс расправятся с бандитами.
233 4 8 9 10 406 7 1 2 13 2121000000000 999999 888 1001000000 1000000000 777 101
41 2000876
В компьютерной игре Dota 2 есть герой Arc Warden. Его ультимейт создает своего клона, который обладает всеми способностями героя. Карта представляет собой дерево из $$$n$$$ вершин с нейтральным крипом в каждой вершине. Напомним, что деревом называется связный неориентированный граф без циклов. Зафармив крипов, герой может получить опыт и золото.
Arc Warden хочет посетить все вершины и зафармить всех крипов. Для этого он выбирает начальную вершину, встаёт в неё и создает своего клона в той же вершине. Затем они с клоном независимо обходят дерево, переходя в соседние по ребру вершины. Разрешается посещать одну вершину более одного раза.
Определите минимальное суммарное расстояние, которое Arc Warden и его клон должны пройти по дереву, чтобы посетить каждую вершину. Расстояние считается как количество рёбер.
Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 500$$$) — количество наборов входных данных.
Первая строка теста содержит целое число $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — количество вершин в дереве.
Следующие $$$n-1$$$ строк описывают рёбра дерева, где каждое ребро соединяет пару вершин $$$u$$$ и $$$v$$$ ($$$1 \leq u,v \leq n$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — минимальное суммарное расстояние, которое должны пройти Arc Warden и его клон, чтобы обойти всё дерево.
351 22 34 25 486 15 88 36 77 52 14 722 1
5 8 1
В первом наборе входных данных выгодно начать в вершине $$$2$$$. Arc Warden может пройти путь $$$2 \to 3 \to 2 \to 1$$$, а его клон может пройти путь $$$2 \to 4 \to 5$$$. Таким образом, суммарно будет пройдено $$$5$$$ рёбер. Можно показать, что ответ лучше получить нельзя.
После выпуска из Университета МИСИС Ваня решил устроиться программистом в Сбер. Чтобы успешно пройти собеседование, он решил полностью прорешать архив задач. К сожалению, архив оказался старым, и в нём нельзя было отсортировать задачи по сложности. Сложность каждой задачи обозначена целым числом.
Ваня придумал следующую стратегию: каждый день он будет просматривать задачи одну за другой, с первой до последней. Если текущую задачу он ещё не решал и уровень его навыка достаточен для её решения, то он решает её, и его навык увеличивается на $$$1$$$. Ваня может решить задачу, если его навык больше или равен сложности задачи.
Изначально уровень навыка Вани равен $$$1$$$. Сколько дней потребуется Ване, чтобы быть готовым к собеседованию?
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество задач в архиве.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — сложности задач в архиве.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Если Ваня сможет решить все задачи из архива, выведите, какое количество дней ему понадобится. В ином случае выведите $$$-1$$$.
441 2 4 333 1 152 4 3 2 511
2 2 -1 1
Это простая версия задачи. Единственное различие между двумя версиями — ограничение на количество различных чисел $$$a$$$ в запросах. В этой версии такое ограничение отсутствует.
Это интерактивная задача.
Вы с Эйприл О'Нил оказались в лаборатории Бакстера Стокмана и попали в ловушку. На вас наступает армия зубастых мышеловов. Единственный способ спастись: отгадать секретный код — число $$$p$$$ ($$$3 \le p \le 10^6$$$), с помощью которого их можно деактивировать. Эйприл работала в этой лаборатории, поэтому помнит, что число $$$p$$$ обязательно простое, ведь самые надёжные криптографические алгоритмы используют простые числа.
В панели управления мышеловами нашлась уязвимость. Она позволяет вам делать запросы «Сравнимо ли число $$$p$$$ по модулю $$$a$$$ с $$$d$$$?». Другими словами: «Верно ли, что $$$p - d$$$ делится нацело на $$$a$$$?». При этом $$$a$$$ и $$$d$$$ вы задаёте сами в каждом запросе.
Если вы нарушите формат взаимодействия или сделаете более $$$1000$$$ запросов, сработает защитный протокол самоуничтожения мышеловов, и вам не поздоровится.
Помогите Эйприл взломать панель управления и деактивировать мышеловов.
Вы можете сделать не более $$$1000$$$ запросов, включая вывод ответа.
Интерактор не является адаптивным, то есть число $$$p$$$ зафиксировано и не меняется с запросами.
Интерактор принимает запросы в следующем формате:
- ? $$$a$$$ $$$d$$$ ($$$2 \le a \le 2 \cdot 10^6$$$, $$$0 \le d \lt a$$$)
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Если вы пишете на C++, жюри советует не подключать ускорение ввода/вывода и использовать std::endl в качестве перевода строки.
Интерактор будет выдавать в ответ одно число:
- $$$0$$$, если число $$$p$$$ не сравнимо с $$$d$$$ по модулю $$$a$$$;
- $$$1$$$, в противном случае.
Когда вы готовы назвать число $$$p$$$ ($$$3 \le p \le 10^6$$$), выведите его в формате:
- ! $$$p$$$
После вывода секретного кода ваша программа должна немедленно завершиться, в противном случае жюри не гарантирует корректность вердикта.
? 2 1 ? 3 1 ? 3 2 ! 3
1 0 0
Это сложная версия задачи. Единственное различие между двумя версиями — ограничение на количество различных $$$a$$$ в запросах. В этой версии различных чисел $$$a$$$ в запросах может быть не более двух.
Это интерактивная задача.
Вы с Эйприл О'Нил оказались в лаборатории Бакстера Стокмана и попали в ловушку. На вас наступает армия зубастых мышеловов. Единственный способ спастись: отгадать секретный код — число $$$p$$$ ($$$3 \le p \le 10^6$$$), с помощью которого их можно деактивировать. Эйприл работала в этой лаборатории, поэтому помнит, что число $$$p$$$ обязательно простое, ведь самые надёжные криптографические алгоритмы используют простые числа.
В панели управления мышеловами нашлась уязвимость. Она позволяет вам делать запросы «Сравнимо ли число $$$p$$$ по модулю $$$a$$$ с $$$d$$$?». Другими словами: «Верно ли, что $$$p - d$$$ делится нацело на $$$a$$$?». При этом $$$a$$$ и $$$d$$$ вы задаёте сами в каждом запросе.
Если вы нарушите формат взаимодействия или сделаете более $$$1000$$$ запросов или спросите более двух различных чисел $$$a$$$, сработает защитный протокол самоуничтожения мышеловов, и вам не поздоровится.
Помогите Эйприл взломать панель управления и деактивировать мышеловов.
Вы можете сделать не более $$$1000$$$ запросов, включая вывод ответа.
Интерактор не является адаптивным, то есть число $$$p$$$ зафиксировано и не меняется с запросами.
Интерактор принимает запросы в следующем формате:
- ? $$$a$$$ $$$d$$$ ($$$2 \le a \le 2 \cdot 10^6$$$, $$$0 \le d \lt a$$$)
Ваши запросы должны содержать не более двух различных чисел $$$a$$$.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Если вы пишете на C++, жюри советует не подключать ускорение ввода/вывода и использовать std::endl в качестве перевода строки.
Интерактор будет выдавать в ответ одно число:
- $$$0$$$, если число $$$p$$$ не сравнимо с $$$d$$$ по модулю $$$a$$$;
- $$$1$$$, в противном случае.
Когда вы готовы назвать число $$$p$$$ ($$$3 \le p \le 10^6$$$), выведите его в формате:
- ! $$$p$$$
После вывода секретного кода ваша программа должна немедленно завершиться, в противном случае жюри не гарантирует корректность вердикта.
? 2 1 ? 3 1 ? 3 2 ! 3
1 0 0