Алгоритмы поиска

Физрук формирует дистанцию для забега школьников на уроке. Согласно требованиям, длина дистанции должна быть от \(L\) до \(R\) метров.

Дистанция пройдет вдоль дорожки в парке около школы. Вдоль дорожки растет \(n\) деревьев, первое дерево находится на расстоянии \(d_1\) метров от начала дорожки, \(i\)-е дерево находится на расстоянии \(d_i\) метров от предыдущего дерева для \(i > 1\). Для удобства физрук хочет, чтобы дистанция начиналась либо в начале дорожки, либо около какого-либо дерева, и заканчивалась также около какого-либо дерева.

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

Помогите физруку выбрать точки начала и конца дистанции.

Формат входных данных
Первая строка ввода содержат два целых числа \(L\) и \(R\) (\(1 \le L \le R \le 3 \cdot 10^{14}\)). Обратите внимание, что для считывания \(L\) и \(R\) необходимо хотя бы 64-битный тип данных (<<long long>> в C++).

Вторая строка ввода содержит целое число \(n\) (\(1 \le n \le 300\,000\)).

Третья строка ввода содержит \(n\) целых чисел \(d_1, d_2, \ldots, d_n\) (\(1 \le d_i \le 10^9\)).

Формат выходных данных
Выведите два целых числа: \(s\) и \(t\) — расстояние от начала дорожки до начала и конца дистанции, соответственно. Должны выполняться условия: \(0 \le s < t\), \(L \le t - s \le R\), \(s = 0\) или \(s\) совпадает с позицией некоторого дерева, \(t\) совпадает с позицией некоторого дерева.

Если выбрать организовать дистанцию не получится, выведите \(s = -1\), \(t = -1\).

Дана строка s и символ с, который встречается в s. Для каждого символа из строки s, определите расстояние до ближайшего символа с.
Расстояние между двумя индексами i и j равно abs(i - j), где abs - функция вычисления модуля числа.


Формат входных данных
В первой строке записана непустая строка s, состоящая из маленьких английских букв (длина строки не превышает 104). Во второй строке записан символ c. Гарантируется, что в строке s содержится как минимум один символ c.

Формат выходных данных
Выведите в одной строке через пробел n чисел ai. Число ai - расстояние от символа с индексом i до ближайшего символа c (n равно длине строки s, 0 <= i < n). Числа выводить в порядке следоваения букв в исходной строке.  

В биологической лаборатории проводят эксперимент. В начале у ученых есть \(n\) замороженных бактерий, пронумерованных от \(1\) до \(n\).

Согласно плану эксперимента замороженная бактерия с номером \(i\) попадёт в чашку Петри через \(a_i\) секунд после начала эксперимента. Если таких бактерий несколько, они все попадают туда одновременно.

Как только замороженная бактерия оказывается в чашке Петри, она размораживается и начинает созревать. Созревание бактерии с номером \(i\) занимает \(t_i\) секунд. Как только бактерия созрела, она начинает размножаться: немедлено превращается в две созревшие бактерии, и затем каждая созревшая бактерия в конце каждой секунды снова делится на две созревшие бактерии.

Размером колонии называется общее количество бактерий в чашке Петри. Цель эксперимента — определить, через сколько секунд размер колонии будет в точности равен \(m\).

Помогите ученым определить искомое число секунд или выясните, что размер колонии никогда не будет в точности равен \(m\).

Формат входных данных
В первой строке даны целые числа \(n\), \(m\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le m \le 10^{9}\)) — количество замороженных бактерий и желаемый размер колонии.

Во второй строке даны \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^{9}\)) — времена перемещения замороженных бактерий в чашку Петри.

В третьей строке даны \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le 10^{9}\)) — продолжительность созревания замороженных бактерий.

Формат выходных данных
Если размер колонии никогда не будет равен \(m\), выведите \(-1\).

В противном случае выведите число секунд после начала эксперимента, через которое размер колонии будет в точности равен \(m\).

Рассмотрим, как развивается эксперимент в первом примере.

Последовательность \([b_1, b_2, \ldots, b_k]\) называется битонической, если выполнены неравенства \(b_1 < b_2 < \ldots < b_i > \ldots > b_k\) для некоторого \(1 \le i \le k\).

Например, последовательности \([1]\), \([1, 2, 3, 2]\), \([1, 4, 10]\), \([3, 2]\) являются битоническими, а последовательности \([1, 1]\), \([2, 1, 3]\) — нет.

Задана последовательность \([a_1, a_2, \ldots, a_n]\). Требуется количество пар \((l, r)\) таких, что \(1 \le l \le r \le n\) и последовательность \([a_l, a_{l+1}, \ldots, a_r]\) является битонической.

Формат входных данных
Первая строка ввода содержит число \(n\) (\(1 \leq n \leq 300\,000\)).

Вторая строка ввода содержит \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\)).

Формат выходных данных
Выведите одно число — количество пар \((l, r)\), таких, что \(1 \le l \le r \le n\) и последовательность \([a_l, a_{l+1}, \ldots, a_r]\) является битонической.

В первом примере подходят следующие пары:

• \((1, 1)\), последовательность \([1]\)

• \((2, 2)\), последовательность \([1]\)

• \((2, 3)\), последовательность \([1, 2]\)

• \((2, 4)\), последовательность \([1, 2, 3]\)

• \((2, 5)\), последовательность \([1, 2, 3, 1]\)

• \((3, 3)\), последовательность \([2]\)

• \((3, 4)\), последовательность \([2, 3]\)

• \((3, 5)\), последовательность \([2, 3, 1]\)

• \((4, 4)\), последовательность \([3]\)

• \((4, 5)\), последовательность \([3, 1]\)

• \((5, 5)\), последовательность \([1]\)

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

Недавно в Диваново построили огромную шлюзовую систему. Всего было построено \(n\) шлюзов, \(i\)-й из них имеет объем \(v_i\) литров. Изначально все шлюзы пусты. В каждый шлюз ведет труба, при открытии которой в шлюз будет поступать по \(1\) литру воды в секунду. Исходно все трубы закрыты.

Шлюзовая система устроена так, что если доливать воду в \(i\)-й шлюз сверх его объема, она будет моментально моментально переливаться в шлюз с номером \(i + 1\). Если шлюз c номером \(i + 1\) тоже заполнен, вода будет переливаться дальше. Вода из последнего шлюза будет выливаться в озеро.

Для того, чтобы шлюзы начали функционировать, необходимо заполнить каждый из них. Мэра Дивановской области интересует \(q\) независимых запросов. Для каждого запроса предположим, что изначально все шлюзы пусты и все трубы закрыты, затем одновременно открываются несколько труб. Для \(j\)-го запроса мэр хочет знать, какое минимальное число труб надо включить, чтобы не позже чем через \(t_j\) секунд все шлюзы стали заполнены.

Помогите мэру справиться с этой сложной задачей и ответьте на все его запросы!

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(1 \le n \le 200\,000\)) — количество шлюзов.

Во второй строке вводятся \(n\) целых чисел \(v_1, v_2, \dots, v_n\) (\(1 \le v_i \le 10^9\)) — объемы шлюзов.

В третьей строке вводится одно целое число \(q\) (\(1 \le q \le 200\,000\)) — число запросов.

В следующих \(q\) строках вводится по одному целому числу \(t_i\) (\(1 \le t_j \le 10^9\)) — время, за которое нужно наполнить все шлюзы в \(j\)-м запросе.

Формат выходных данных
Выведите \(q\) чисел, \(j\)-е из них должно быть равно минимальному числу труб, которое нужно открыть, чтобы наполнить все шлюзы за время \(t_j\). Если за это время наполнить всю шлюзы невозможно, выведите \(-1\).

В первом примере \(6\) запросов:

В запросах \(1, 3, 4\) ответ \(-1\). Чтобы заполнить первый шлюз нужно подождать \(4\) секунды, даже если открыты все трубы.

В шестом запросе можно открыть трубы в шлюзах \(1, 3\), и \(4\). Тогда через \(4\) секунды заполнятся шлюзы \(1\) и \(4\). Через \(1\) секунду \(1\) литр воды перельётся в шлюзы \(2\) и \(5\). Шлюз \(3\) будет заполнен своей трубой.

Аналогично во втором запросе можно открыть трубы в шлюзах \(1, 3\) и \(4\).

В пятом запросе можно открыть трубы в шлюзах с номерами \(1, 2, 3, 4\).

Электронная почта Деда Мороза в течении долгого времени принимает заказы на новогодние подарки. Все желания детей кодируются некоторым положительным целым числом и затем передаются по каналу связи. Количество заказаов заранее неизвестно, но их всегда не менее двух. Признаком конца данных считается число 0. 
Для того, чтобы понять, что все данные приняты без ошибок, после данных передаётся контрольное значение. Контрольное значение равно максимально возможному произведению двух чисел из переданных, которое делится на 7, но не делится на 49. Если такое произведение получить нельзя, контрольное значение считается равным 1.
Дед Мороз очень занят в последний месяц перед Новым годом и просит вас обработать все входные данные и напечатать краткий отчёт, включающий количество принятых чисел, принятое контрольное значение, вычисленное контрольное значение и вывод о совпадении значений.


Формат входных данных
В каждой строке исходных данных содержится одно целое число. Сначала идут строки с основными данными – положительными числами, затем число 0 (признак окончания данных), в последней строке – контрольное значение.

Формат выходных данных
Программа должна вывести отчёт по форме, приведённой ниже в примере.
 

Примечание
В последней строке в зависимости от результата (если переданное контрольное значение и вычисленное контрольное значения равны) может быть values true

У Максимуса есть коллекция волшебных амулетов, каждый из которых обладает своей магической силой. Список имеющихся у него амулетов отсортирован в порядке неубывания магической силы. Вернувшись из очередного путешествия, Максимус составил список новых амулетов, предварительно отсортировав их по невозрастанию магической силы. Теперь у него два отдельных списка и он хочет объединить их в один упорядоченный по неубыанию список. 
Он хочет сделать это как можно быстрее. Помогите ему отсортировать два этих списка. Максимус просит вас написать программу, которая будет работать за O(len(A)+len(B)). 
 

Примеры

В Сильвертауне расположены n розничных магазинов. В логистический центр города доставили m типов товаров с различным количеством, которые необходимо распределить по всем розничным магазинам. Логистическому центру необходимо распределить все товары по магазинам, следуя следующим правилам:

- Каждому магазину распределяется не более одного типа товара, но любое его количество.
- После распределения каждому магазину предоставляется некоторое количество товаров (возможно нулевое).

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

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

Примеры

Примеры

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

Примеры

3 1 
1
100 00:01

01:08

Эвелине на Новый год подарили массив a из n неотрицательных целых чисел, каждое из которых не превосходит 2022. Её заинтересовал вопрос, сколько в этом массиве существует различных пар индексов, у которых первый индекс в паре меньше второго, таких, что сумма соответствующих элементов массива равна 2022. Формально, она хочет понять, сколько существует пар 1 <= i,j <= n, для которых выполняется ai+aj=2022.

Уже наступил февраль, а Эвелина все еще не успела посчитать ответ на вопрос, потому что массив слишком большой. Но она смогла запомнить его и рассказала о своем массиве вам, чтобы получить помощь с поиском ответа.

В первом примере не существует пар с суммой 2022.

Во втором подходят пары (1, 2), (3, 4).

В третьем примере подходят все пары (2, 4), (2, 5), (3, 4), (3, 5). 

Примеры

2
1 2022

0

4
1000 1022 1001 1021

2

5
700 1 1 2021 2021

4

Однажды утром Глеб с ужасом осознал, что проспал, а пары в «Высшем университете» начинаются уже скоро. Опоздать было бы не так страшно, если бы он их и не вёл. К счастью, автомобиль Глеба «Пантера» довольно мощный: для упрощения будем считать, что за одну секунду он может сначала или увеличить скорость на 1, или уменьшить скорость на 1, или не менять её, а после этого его автомобиль проезжает x метров, где x - его текущая скорость в метрах в секунду. Потом он снова принимает решение об изменении скорости. Начальная скорость автомобиля преподавателя в момент, когда он только выезжает из дома, равна нулю. Путь до университета от его дома не близкий: нужно проехать d метров.

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

Пока Глеб собирался на работу, его заинтересовал вопрос, а за какое минимальное время он может доехать до работы, если будет действовать оптимально. Так как преподаватель будет занят скоростным вождением, ответить на этот вопрос честь выпала вам!

Вводится одно целое число - d (1 <= d <= 10¹⁸), расстояние до университета.

Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

В первом тесте из условия Глебу выгодно действовать следующим образом:

1. Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
2. Не менять скорость, проехать один метр; скорость 1 м/с, проехал 2 метра от дома.

3. Уменьшить скорость на один; скорость 0 м/с, проехал 2 метра от дома.

Таким образом, он потратит 3 секунды, и его конечная скорость будет равно 0 м/с.

Во втором тесте из условия Глебу выгодно действовать, например, так:

1. Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
2. Увеличить скорость на один, проехать два метра; скорость 2 м/с, проехал 3 метра.
3. Увеличить скорость на один, проехать три метра; скорость 3 м/с, проехал 6 метров.
4. Уменьшить скорость на один, проехать два метра; скорость 2 м/с, проехал 8 метров.
5. Уменьшить скорость на один, проехать один метр; скорость 1 м/с, проехал 9 метров.
6. Не менять скорость, проехать один метр; скорость 1 м/с, проехал 10 метров.
7. Уменьшить скорость на один; скорость 0 м/с, проехал 10 метров.

    

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

Примеры

2

3

10

7

Однажды утром Глеб с ужасом осознал, что проспал, а пары в «Высшем университете» начинаются уже скоро. Опоздать было бы не так страшно, если бы он их и не вёл. К счастью, автомобиль Глеба «Пантера» довольно мощный: для упрощения будем считать, что за одну секунду он может сначала или увеличить скорость на 1, или уменьшить скорость на 1, или не менять её, а после этого его автомобиль проезжает x метров, где x - его текущая скорость в метрах в секунду. Потом он снова принимает решение об изменении скорости. Начальная скорость автомобиля преподавателя в момент, когда он только выезжает из дома, равна нулю. Путь до университета от его дома не близкий: нужно проехать d метров.

Глеб, обеспокоенный за знания своих студентов, хочет попасть в университет как можно раньше, чтобы успеть подготовиться к проведению лекции. К сожалению, у проезда на парковку университета установлен датчик движения: если скорость проезжающего транспортного средства будет превышать s, то администрация университета выпишет нарушителю дисциплинарное взыскание. Конечно, Глеб не хочет его получить, поэтому при въезде в университет, когда автомобиль проехал все d метров его скорость x должна быть не больше s.

Пока Глеб собирался на работу, его заинтересовал вопрос, а за какое минимальное время он может доехать до работы, если будет действовать оптимально, но не нарушать правила при въезде в университет. Так как преподаватель будет занят скоростным вождением, ответить на этот вопрос честь выпала вам!

В двух строках заданы два целых числа - d, s (1 <= d <= 10¹⁸, 0 <= s <= 10¹⁸), расстояние до университета и ограничение на конечную скорость.

Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

В первом тесте из условия Глебу выгодно действовать следующим образом:

1. Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
2. Не менять скорость, проехать один метр; скорость 1 м/с, проехал 2 метра.

    

Таким образом, он потратит 2 секунды, и его конечная скорость будет равно 1 м/с, что не превышает s.

Во втором тесте из условия Глебу выгодно действовать, например, так:

1. Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
2. Увеличить скорость на один, проехать два метра; скорость 2 м/с, проехал 3 метра.
3. Увеличить скорость на один, проехать три метра; скорость 3 м/с, проехал 6 метров.
4. Уменьшить скорость на один, проехать два метра; скорость 2 м/с, проехал 8 метров.
5. Уменьшить скорость на один, проехать один метр; скорость 1 м/с, проехал 9 метров.
6. Не менять скорость, проехать один метр; скорость 1 м/с, проехал 10 метров.
7. Уменьшить скорость на один; скорость 0 м/с, проехал 10 метров.

    

Таким образом, он потратит 7 секунд, и его конечная скорость будет равно 0 м/с, что не превышает s.

Примеры

2
1

2

10
0

7

Примеры