Алгоритмы

У вашего одноклассника, которого вы не очень любите за его занудство, но уважаете за его ум, были обнаружены две строки: строка t длины m и строка s длины n. Последовательность индексов p1, p2, ..., pm, где 1<=p1<p2<…<pm<=n, называется хорошей , если spi=ti для всех i от 1 до m. Шириной последовательности называется величина \(\max_{i = 1}^{m - 1} \left(p_{i + 1} - p_i\right)\), то есть максимальная разность между соседними элементами последовательности p.

Помогите однокласснику найти хорошую последовательность индексов с максимальной шириной. Одноклассник обещал вам, что строки s и t таковы, что хотя бы одна хорошая последовательность точно существует.

Первая строка входных данных содержит два числа n и m (2<=m<=n<=200000) - длины строк s и t соответственно.

Во второй строке входных данных задана строка s, состоящая из строчных букв английского алфавита, а в третьей строке задана строка t, состоящая из строчных букв английского алфавита.

Гарантируется, что существует хотя бы одна хорошая последовательность индексов.

Выведите одно число - максимальную ширину хорошей последовательности.

В первом примере из условия существуют две хорошие последовательности с шириной 3: это {1,2,5} и {1,4,5}.

Во втором примере из условия хорошая последовательность максимальной ширины — это {1,5}.

В третьем примере из условия есть лишь одна хорошая последовательность — это {1,2,3,4,5}.

В четвёртом примере из условия есть лишь одна хорошая последовательность — это {1,2}.

Примеры

5 3
abbbc
abc

3

5 2
aaaaa
aa

4

5 5
abcdf
abcdf

1

2 2
ab
ab

1

Примеры

3 2
2 6
3 4 5

1
1

3 2
1 6
4 3 5

0

3 5
1 7
5 3 4

3 
2
3
1

Примеры

4 1
4 2 1 5

3

7 10
1 3 20 2 7 45 5

15

Примеры

1 1 10
2

9.0000

5 1 10
1 2 4 8 16

28.0000

Примеры

8 2 3
170
205
225
190
260
130
225
160

30

Дан массив из n чисел, отсортированный по невозрастанию, и k запросов. Для каждого запроса выведите минимальный номер элемента массива, меньший данного (нумерация элементов массива начинается с 1).

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по невозрастанию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

Для каждого из k запросов выведите минимальный номер элемента массива, меньше данного. Если таких нет, выведите 0.

Примеры

5 5
9 8 5 3 3
2 4 8 1 10

0
4
3
0
1

Дан массив из n чисел, отсортированный по невозрастанию, и k запросов. Для каждого запроса выведите максимальный номер элемента массива, не меньше данного (нумерация элементов массива начинается с 1).

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по невозрастанию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

Для каждого из k запросов выведите максимальный номер элемента массива, не меньше данного. Если таких нет, выведите 0.

Примеры

5 5
9 8 5 3 3
2 4 8 1 10

5
3
2
5
0

Дан массив из n чисел, отсортированный по невозрастанию, и k запросов. Для каждого запроса выведите максимальный номер элемента массива, большего данного (нумерация элементов массива начинается с 1).

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по невозрастанию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

Для каждого из k запросов выведите максимальный номер элемента массива, большего данного. Если таких нет, выведите 0.

Примеры

5 5
9 8 5 3 3
2 4 8 1 10

5
3
1
5
0

Дан массив из n чисел, отсортированный по неубыванию, и k запросов. Для каждого запроса выведите максимальный номер элемента массива, меньший данного (нумерация элементов массива начинается с 1).

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по неубыванию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

Для каждого из k запросов выведите максимальный номер элемента массива, меньший данного. Если таких нет, выведите 0.

Примеры

5 5
3 3 5 8 9
2 4 8 1 10

0
2
3
0
5

Для полученного дерева выведите список всех вершин, имеющих только одного ребёнка, в порядке возрастания.

Вводится последовательность целых чисел,оканчивающаяся нулем. Построить по ней дерево.

Выведите список требуемых вершин.

 

Примеры

7 3 2 1 9 5 4 6 8 0

2
9

Выведите все элементы полученного дерева в порядке возрастания.

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. По данной последовательности требуется построить дерево.

Выведите ответ на задачу.

Примеры

7 3 2 1 9 5 4 6 8 0

1
2
3
4
5
6
7
8
9

Выведите второй по величине элемент в построенном дереве. Гарантируется, что такой найдется.

Дана последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.

Выведите ответ на задачу.

Примеры

7 3 2 1 9 5 4 6 8 0

8

Дан массив a из n целых чисел a1, a2,..., an. Научитесь быстро отвечать на запросы «Сколько чисел имеют значения от l до r»?

В первой строке находится целое число n (1<=n<=10⁵) — длина массива. Во второй строке находятся n целых чисел a1, a2,..., an (−10⁹<=ai<=10⁹). В третьей строке находится целое число k (1<=k<=10⁵) — число запросов. В следующих k строках находятся пары чисел l r (−10⁹<=l<=r<=10⁹).

Выведите k чисел (каждое в отдельной строке) - ответы на запросы.

Примеры

5
10 1 10 3 4
4
1 10
2 9
3 4
2 2

5
2
2
0 

Дан массив из n чисел, отсортированный по неубыванию, и k запросов. Для каждого запроса выведите максимальный номер элемента массива, не большего данного (нумерация элементов массива начинается с 1).

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по неубыванию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

Для каждого из k запросов выведите максимальный номер элемента массива, не большего данного. Если таких нет, выведите 0.

Примеры

5 5
3 3 5 8 9
2 4 8 1 10

0
2
4
0
5

Дан массив из n чисел, отсортированный по неубыванию, и k запросов. Для каждого запроса выведите минимальный номер элемента массива, не меньшего данного (нумерация элементов массива начинается с 1).

В первой строке входных данных содержатся числа n и k (0 < n,k <= 10⁵) - длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по неубыванию. В третьей строке содержатся k запросов. Все элементы массива и запросы - целые числа, каждое из которых по модулю не превосходит 2·10⁹ .

Для каждого из k запросов выведите минимальный номер элемента массива, не меньшего данного. Если таких нет, выведите n+1.

Примеры

5 5
3 3 5 8 9
2 4 8 1 10

1
3
4
1
6

На заключительный этап МОШ по информатике в 2023 году пришло N участников. Так получилось, что у каждого ребенка на каком либо из предметов одежды было записано одно число. При регистрации, один из организаторов решил записать все эти числа. Позже выяснилось, что каким-то чудесным образом, все участники зарегистрировались в порядке неубывания этих чисел на одежде.  

На следующий год организаторы решили на отборочном этапе добавить задачу, которая бы помогла им определить количество участников, у которых на одежде было записано определенное число. Напишите программу для решения данной задачи.

В первой строке входного файла содержится единственное число N (0 <= N <= 10⁵) — количество участников заключительного этапа. В следующей строке находятся N упорядоченных по неубыванию неотрицательных целых чисел, не превосходящих 10⁹ и разделенных пробелами — числа, записанные у участников на одежде. В третьей строке файла записано число M (1<=M<=100000) — количество чисел, информацию о которых хотят узнать судьи. В четвертой строке через пробел записаны M целых неотрицательных чисел (не превышающих 10⁹+1).

Выведите M чисел, каждое в отдельной строке. Для каждого заданного в четвертой строке числа  выведите количество участников с таким числом на одежде.

Громозека и Алиса придумали правила игры в бесконечную Дженгу.
В бесконченой Дженге каждый ход заключается в одном из двух действий на выбор игрока:

• если в башне есть хотя бы один брусок, то можно вытащить и убрать из башни ровно один брусок (количество брусков в башне уменьшается на 1);
• поставить на башню количество брусков на 1 больше, чем ставили в последний раз перед этим.

Например, можно выполнить такую последовательность действий при игре:

После 9 ходов, количество брусокв в башне в итоге будет равно 11, а по ходу игры из башни извлекли 4 бруска.

Известно, что Алиса и Громозека сделали n ходов в придуманной игре, при этом после всех выполненных ходов, количество брусков в башне равнялось k. Найдите суммарное количество убранных Алисой и Громозекой с башни брусков за все n ходов. Гарантируется, что для заданных n и k ответ существует.

В первой строке входных данных заданы два целых числа n и k (1<=n<=10⁹; 0<=k<=10⁹) - суммарное количество ходов и количество брусков в башне после n ходов. Гарантируется, что для заданных n и k ответ существует.

Выведите одно целое число - количество брусков, которые были вытащены Алисой и Громозекой вместе за время игры. Обратите внимание, что в этой задаче не может быть нескольких правильных ответов - ответ однозначно определяется по входных данным.
 

Примеры

1 1

0

9 11

4

5 0

3

3 2

1

Требуется определить в заданном массиве номер самого левого и самого правого элемента, равного искомому числу.

В первой строке вводится одно натуральное число N, не превосходящее 10⁵: количество чисел в массиве.

Во второй строке вводятся N натуральных чисел, не превосходящих 10⁹, каждое следующее не меньше прелылущего.

В третьей строке вводится количество искомых чисел M - натуральное число, не превосходящее 10⁶.

В четвертой строке вводится M натуральных чисел, не превосходящих 10⁹.

Выходные данные

Для каждого запроса выведите в отдельной строке через пробел два числа: номер элемента самого левого и самого правого элементов массива, равных числу-запросу. Элементы массива нумеруются с единицы.

Если в массиве нет такого числа, выведите в соответствующей строке два нуля, разделенных пробелом.

Примеры

4
1 2 2 3
4
4 3 2 1

0 0
4 4
2 3
1 1

Примеры

7 3 2 1 9 5 4 6 8 0

YES

Для полученного дерева выведите список всех вершин, имеющих по два ребёнка, в порядке возрастания.

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. Постройте по этой последовательности дерево.

Выведите ответ задачи.

Примеры

7 3 2 1 9 5 4 6 8 0

3
5
7