"Два указателя"

11 задач
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Секретная последовательность#43349

Алиса оставила для своего отца профессора Селезнева секретную последовательность a[1..n]. Чтобы ее не прятать, она решила написать ее на самом видном месте, но в другом порядке следования чисел. Профессор Селезнев знает, что Алиса переписала секретную последовательность в следующем виде:

  • первым числом слева записано число a1;
  •  первым числом справа записано число a2;
  • вторым числом слева (после a1) записано число a3;
  • вторым числом справа (то есть перед числом a2) записано число a4;
  • все остальные числа записаны аналогичным образом.

То есть, если бы секретная последовательность была a = [1, 2, 3, 4, 5, 6], то профессор бы увидел следующую последовательность [1, 3, 5, 6, 4, 2]. Профессор Селезнев очень торопился и успел только сохранить в компьютер последовательность, которую увидел. Напишите программу, которая покажет профессору исходную секретную последовательность.



Входные данные
Первая строка содержит размер последовательности n (1 <= n <= 300), записанной Алисой для своего отца. Вторая строка содержит n чисел ai (1 <= ai <= 109) - саму последовательность.

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

6
1 3 5 6 4 2

 1 2 3 4 5 6
2 1
23		 23

 

"Два указателя"Задача на реализациюОдномерные массивы
✓ 112✗ 161700средняяВойти и решать
Сортировщик Томми#43034
У Томми есть детская игрушка «cортировщик», с расположенными подряд n колышками. На каждом колышке сейчас не более одного диска (то есть на каком-то колышке диск есть, а на каком-то его нет). Томми хочет переложить имеющиеся диски на колышках таким образом, чтобы они образовывали неубывающую последовательность при просмотре слева направо. То есть на каждом следующем колышке количество дисков должно быть не меньше, чем на предыдущем.  Какое минимальное количество дисков Томми необходимо переложить?
Обратите внимание, что какие- то колышки по окончанию сортировки могут быть пустыми. Какие-то колышки могут содержать более 1 диска.



Входные данные
Программа получает на вход в первой строке целое число n (1 <= n <= 105), количество колышек на «cортировщике». Следующая строка содержит n целых чисел a1, a2, ... an – наличие диска на соответствующем колышке (0 <= ai <= 1). число 0 означает, что на i-м колышке нет диска, 1 – диск есть.

Выходные данные
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 
8
0 0 1 1 1 1 1 1
 
0
2 
11
1 1 0 0 1 0 0 1 1 1 0
 
3
"Два указателя"Жадный алгоритмКонструктив
✓ 65✗ 75700средняяВойти и решать
Подпоследовательность длиной L#39482
Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, в которых количество отрицательных чисел не превышает С. Найдите среди них подпоследовательность с максимальной суммой, длины L. В ответе укажите сумму найденной подпоследовательности.

Входные данные
В первой строке записаны 3 числа: количество чисел N (1 <= N <= 1 000 000),  L и C (\(1 <= L, C <= N <= 1 000 000\)). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.

Пример организации исходных данных во входном файле (для L = 3 и С = 3):
5 3 3
1
-1
2
-2
3

В этом наборе можно выбрать несколько последовательностей, но с максимальной суммой равной 3 будет: 2+(-2)+3. 
Ответ (для С = 3 и L = 3): 3. 

 
"Два указателя"Префиксные суммы(минимумы, ...)
✓ 85✗ 212700средняяВойти и решать
Ослабление флота#33252
Кэрол Дэнверс, известная как Капитан Марвел противодействует флоту Скруллов. Каждый из
кораблей Скруллов имеет определенную мощность, выраженную натуральным числом.
Кэрол считает, что настолько сильна, что может не только вывести из строя флот, но и немного
развлечься. Внимательно изучив мощность корабля, она решила, что будет выводить их из строя
в следующем порядке: каждый раз Кэрол будет атаковать тот корабль из неатакованных ранее,
мощность которого является медианой мощностей оставшихся кораблей.
Медиану ряда чисел Кэрол вычисляет следующим образом:
• Если количество чисел в ряду нечетно, то медиана — число, стоящее посередине упорядоченного по возрастанию данного ряда.
• Если количество чисел в ряду чётно, то медианой ряда является:
– Меньшее из двух стоящих посередине чисел упорядоченного по возрастанию данного ряда, если два средних различны.
– Любое из двух стоящих посередине чисел упорядоченного по возрастанию данного ряда,
если два средних равны.
Помогите Капитану Марвел посчитать порядок, в котором нужно атаковать корабли.

Формат входных данных
В первой строке дано одно натуральное число n — число кораблей во флоте Скруллов (1 <= n <= 105).
Во второй строке содержатся n натуральных чисел ai — мощность i-го корабля (1 <= ai <=109).
Формат выходных данных
Выведите n чисел — мощности кораблей в том порядке, в котором Кэрол будет их атаковать.
 
Ввод Вывод
3
8 3 19
 
 8 3 19
4
4 2 2 1
 2 2 1 4


 
"Два указателя"
✓ 204✗ 374700средняяВойти и решать
Проверка подпоследовательности#28420
Проверить, является ли последовательность подпоследовательностью заданного массива.
 
Входные данные
В первой строке входных данных содержится число N – длина заданной последовательности (1 ≤ N ≤ 10000). Во второй строке заданы члены исходной последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.
 
В третьей строке записано число M – длина подпоследовательности (1 ≤ M ≤ 10000). В четвертой строке задаются члены подпоследовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

Выходные данные
Вывести "YES" если последовательность заданная в 4-ой строке является подпоследовательность заданного массива и "NO", если не является.
 
Ввод Вывод
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 5 4 6 7 8 9 10		 NO
10
1 2 3 4 5 6 7 8 9 10
9
1 2 3 5 6 7 8 9 10		 YES

Пояснение.
Не путать "подпоследовательность" с "подстрокой".
"Два указателя"
✓ 369✗ 793500лёгкаяВойти и решать
Точки на прямой#28417
Маленький Петя очень любит точки. Недавно мама подарила ему n точек, лежащих на прямой OX. Пете стало интересно, сколькими способами он может выбрать три различные точки так, чтобы расстояние между двумя самыми удаленными из выбранных точек не превышало d.
Обратите внимание, что порядок точек внутри выбранной тройки значения не имеет.

Входные данные
Первая строка содержит два целых числа: n и d (1 ≤ n ≤ 105; 1 ≤ d ≤ 109). Следующая строка содержит n целых чисел x1, x2, ..., xn, по модулю не превосходящих 109 — x-координаты точек, подаренных Пете.
Гарантируется, что координаты точек во входных данных строго возрастают.

Выходные данные
Выведите единственное целое число — количество троек точек, в которых расстояние между двумя самыми удаленными точками не превосходит d.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
 
Ввод Вывод
4 3
1 2 3 4
 4
4 2
-3 -2 -1 0
 2
5 19
1 10 20 30 50
 1
 
В первом примере нам подходит любая тройка различных точек.
Во втором примере нам подходят всего 2 тройки: {-3, -2, -1} и {-2, -1, 0}.
В третьем примере нам подходит одна тройка: {1, 10, 20}.
 
"Два указателя"Комбинаторика
✓ 362✗ 718600лёгкаяВойти и решать
Два одинаковых массива#28345
На вход подаются два массива A и В, отсортированных по неубыванию. Вам нужно узнать, существует ли такое число, которое содержится в обоих массивах. Если такое число существует, выведите 1, иначе выведите 0.

Входные данные
В первой строке записано натуральные числа N и M– количество элементов первого и второго массива соответственно,  (1 <= N, M <= 108). В следующих двух строках записаны элементы массива A и B. Во второй строке - элементы массива A, в третьей - элементы массива B. Все элементы массива неотрицательные числа, не превышающие 1018.

Выходные данные
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 4 4
1 2 3 4
2 4 7 8		 1
"Два указателя"Хеш
✓ 841✗ 2 034500лёгкаяВойти и решать
Пары точек#28344
На прямой находятся N точек. Требуется подсчитать количество пар индексов (i, j) таких, что i не равно j и |ai - aj|  <= D.

Формат входных данных
В первой строке находятся два числа N и D (1 <= N <= 105, 1 <= D <= 109). Во второй строке находится N неотрицательных чисел, каждое из котороых не более чем 2*109.

Формат выходных данных
Выведите на экран ответ на задачу.
"Два указателя"Использование сортировки
✓ 540✗ 2 833600лёгкаяВойти и решать
Метод двух указателей#28341
Дан массив из N положительных чисел. Найти в нем минимальное количество подряд идущих чисел, таких что их сумма больше K.

Входные данные
В первой строке записано число N, во второй - K (0<N<= 106, 0<=K<= 109). В третьей строке записаны натуральные числа последовательности.

Выходные данные
Выведите длину наименьшей последовательности чисел, сумма которых больше K. Если такой последовательности найдено не будет, то выведите -1.
 
Примеры
№ Входные данные Выходные данные
1 6
7
3 1 3 2 4 3		 3
"Два указателя"
✓ 944✗ 3 655400лёгкаяВойти и решать
Стильная одежда - 2#28333

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

В наличии имеется \(N_1\) кепок, \(N_2\) маек, \(N_3\) штанов и \(N_4\) пар ботинок (\(1 \le N_i \le 100\,000\)). Про каждый элемент одежды известен его цвет (целое число от 1 до \(100\,000\)). Комплект одежды — это одна кепка, майка, штаны и одна пара ботинок. Каждый комплект характеризуется максимальной разницей между любыми двумя его элементами. Помогите Глебу выбрать максимально стильный комплект, то есть комплект с минимальной разницей цветов.

Формат входных данных
Для каждого типа одежды \(i\) (\(i = 1, 2, 3, 4\)) сначала вводится количество \(N_i\) элементов одежды этого типа, далее в следующей строке — последовательность из \(N_i\) целых чисел, описывающих цвета элементов. Все четыре типа подаются на вход последовательно, начиная с кепок и заканчивая ботинками. Все вводимые числа целые, положительные и не превосходят \(100\,000\).

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

"Два указателя"
✓ 249✗ 451700средняяВойти и решать
Город Че#28332
В центре города Че есть пешеходная улица - одно из самых популярных мест для прогулок жителей города. По этой улице очень приятно гулять, ведь вдоль улицы расположено n забавных памятников.
 
Девочке Маше из города Че нравятся два мальчика из ее школы, и она никак не может сделать выбор между ними. Чтобы принять окончательное решение, она решила назначить обоим мальчикам свидание в одно и то же время. Маша хочет выбрать два памятника на пешеходной улице, около которых мальчики будут ее ждать. При этом она хочет выбрать такие памятники, чтобы мальчики не увидели друг друга. Маша знает, что из-за тумана мальчики увидят друг друга только в том случае, если они будут на расстоянии не более r метров.
 
Маше заинтересовалась, а сколько способов есть выбрать два различных памятника для организации свиданий.
 
Входные данные
В первой строке находятся два целых числа n и r (2<=n<=300 000, 1<=r<=109) - количество памятников и максимальное расстояние, на котором мальчики могут увидеть друг друга.
Во второй строке задано n положительных чисел d1 ... dn, где di - расстояние от i-го памятника до начала улицы. Все памятники находятся на разном расстоянии от начала улицы. Памятники приведены в порядке возрастания расстояния от начала улицы (1<=d1 <d2< ... < dn<=109).
 
Выходные данные
Выведите одно число - число способов выбрать два памятника для организации свиданий.
 
Примеры
№ Входные данные Выходные данные Пояснение
1
4 4
1 3 5 8
 2 В приведенном примере Маша может выбрать памятники 1 и 4 или памятники 2 и 4.
 
"Два указателя"
✓ 547✗ 1 146500лёгкаяВойти и решать
Поделиться
Класснуть