Даны $$$4 \cdot k$$$ гирь массами 1 грамм, 2 грамма, ..., $$$4 \cdot k$$$ грамм. Их разделили на две равные по количеству и массе части. Удалите из каждой группы по две гири так, чтобы массы групп остались равными.
В первой строке входных данных записано целое число $$$k$$$ ($$$1 \le k \le 50000$$$). Во второй строке через пробел записаны $$$2 \cdot k$$$ целых чисел — массы гирь первой группы, в третьей строке записаны $$$2 \cdot k$$$ целых чисел — массы гирь второй группы. Суммы чисел в группах совпадают. Каждое число от 1 до $$$4 \cdot k$$$ встречается ровно один раз.
Выведите четыре целых числа в любом порядке – массы гирь, которые нужно удалить. В случае нескольких правильных ответов выведите любой.
Подзадача 1 (до 40 баллов): $$$k \le 20$$$
Подзадача 2 (до 28 баллов): $$$k \le 200$$$
Подзадача 3 (до 32 баллов): $$$k \le 50000$$$
2 2 5 3 8 7 1 6 4
3 2 4 1
Примечание для пишущих на языке Python: ввести набор чисел, записанных через пробел, можно так:
a = [int(x) for x in input().split()]
Составляя тесты к предыдущей задаче, жюри задумалось над вопросом: а сколько различных тестов для заданного $$$k$$$ можно придумать? Жюри считает два теста различными, если один из них нельзя получить из другого обменом групп местами и/или перестановкой чисел в группах. Напишите программу для поиска ответа на этот вопрос.
Вводится одно целое число $$$k$$$ ($$$1 \le k \le 16$$$).
Выведите одно целое число — количество способов разбить первые $$$4 \cdot k$$$ натуральных чисел на две группы по $$$2 \cdot k$$$ чисел в каждой так, чтобы суммы чисел в группах были одинаковы.
2
4
В примере для $$$k=2$$$ можно получить 4 различных способа разбиения:
- 1 2 7 8 и 3 4 5 6
- 1 3 6 8 и 2 4 5 7
- 1 4 5 8 и 2 3 6 7
- 1 4 6 7 и 2 3 5 8
Система оценивания. Решения, верно работающие для $$$k \le 6$$$, будут оценены в 50 баллов.
Обратите внимание: ответ может не помещаться в 32-битный целый тип, рекомендуется использовать 64-битный тип (long long в языке C++, long в Java и C#, int64 в Pascal). В Python ничего дополнительно делать не требуется.
Вася написал на листке $$$n$$$ подряд идущих положительных целых чисел. При этом всего оказалось выписано $$$k$$$ цифр. Какое число Вася написал первым?
Вводятся два целых числа $$$n$$$ и $$$k$$$, каждое в отдельной строке ($$$1 \le n \le 10^{17}$$$, $$$1 \le k \le min (18 \cdot n, 10^{18}))$$$.
Выведите число, которое было написано первым. Если есть несколько верных ответов, выведите наименьший. Если решений нет, выведите -1.
910
2
21
-1
Система оценивания.
Подзадача 1 (до 28 баллов): $$$n \le 100$$$, $$$k \le min(3 \cdot n, 10^3)$$$.
Подзадача 2 (до 36 баллов): $$$n \le 10^6$$$, $$$k \le min(7 \cdot n, 10^7)$$$.
Подзадача 3 (до 36 баллов): $$$n \le 10^{17}$$$, $$$k \le min (18 \cdot n, 10^{18})$$$.
Обратите внимание: входные данные и ответ в третьей подзадаче могут не помещаться в 32-битный целый тип, рекомендуется использовать 64-битный тип (long long в языке C++, long в Java и C#, int64 в Pascal). В Python ничего дополнительно делать не требуется.
Напишите программу для поиска подстроки в строке. Дополнительное условие: разрешена одна ошибка, то есть одна пара символов может не совпадать.
В первой строке входных данных записана строка $$$s$$$, в которой ищем. Во второй строке записана подстрока $$$q$$$, которую ищем. Строки содержат только строчные латинские буквы, а их длины не превышают $$$2 \cdot 10^5$$$ символов.
Выведите одно целое число — позицию вхождения подстроки $$$q$$$ в строку $$$s$$$ (позиции нумеруются с единицы). Если есть несколько верных ответов, то выведите наименьший из них. Если нет ни одного вхождения, то выведите 0.
abacabadababad
2
Решения, работающие для строк длиной до 1000 символов, могут получить до 40 баллов.
Дан лабиринт размером $$$N \times M$$$ клеток. В верхнем левом углу лабиринта находится квадрат со стороной $$$P$$$ клеток. За один шаг квадрат может перемещаться на одну клетку вверх, вниз, вправо или влево, если при этом он не столкнется с занятыми клетками. Необходимо найти наименьшую возможную длину пути, по которой квадрат может добраться до нижнего правого угла.
В первой строке вводятся три числа $$$N$$$, $$$M$$$, $$$P$$$. Далее идет $$$N$$$ строк по $$$M$$$ символов, обозначающих клетки лабиринта: '.', если клетка свободна, 'X', если занята. Гарантируется, что верхний левый и нижний правый квадраты $$$P \times P$$$ не содержат занятых клеток.
Выведите наименьшую возможную длину пути, или $$$-1$$$, если такого пути не существует.
5 5 2...XX....XX...XXX...XX...
6
5 5 2...XX...XXXX.XXXX...XX...
-1
Подзадача 1 (до 20 баллов): $$$1 \leq N,M \leq 10$$$, $$$P = 1$$$
Подзадача 2 (до 20 баллов): $$$1 \leq N,M \leq 2000$$$, $$$P = 1$$$
Подзадача 3 (до 20 баллов): $$$1 \leq N,M \leq 50$$$, $$$P = 2$$$
Подзадача 4 (до 20 баллов): $$$1 \leq N,M \leq 2000$$$, $$$1 \leq P \leq min(50,N,M)$$$
Подзадача 5 (до 20 баллов): $$$1 \leq N,M \leq 2000$$$, $$$1 \leq P \leq min(N,M)$$$