Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: "Два указателя"

Условие задачи  
ID 32981
Распродажа
Темы: "Два указателя"    Словари   

В магазине проходит новогодняя распродажа – цены всех товаров снижены на 25 %. Оказалось, что первоначально все цены делились на 4, поэтому после снижения цен все цены
также выражаются целым числом. Товаровед вечером перед распродажей снял ценники со всех товаров и напечатал для каждого товара ещё один ценник со сниженной ценой. Он оставил все ценники на столе,
рассчитывая утром их развесить. Но, придя утром в магазин, он обнаружил, что уборщица смешала все ценники вместе, и теперь ему нужно отделить старые ценники от новых.
Помогите ему решить эту задачу. 

Первая строка входных данных содержит общее количество ценников N, 2 ≤ N ≤ 105,N – чётное число. Следующие N строк содержат целые положительные числа, не превосходящие 109, идущие в порядке неубывания по одному в строке – числа, записанные на всех ценниках (как старых, так и новых). Гарантируется, что входные данные корректны,то есть решение существует.

Программа должна вывести N / 2 целых чисел в порядке неубывания – стоимости товаров после понижения цен.

Ввод Вывод Примечание
6
30
40
42
45
56
60
30
42
45
До распродажи цены товаров были 40, 56, 60, после снижения цены
на эти товары стали равны 30, 42, 45.

ID 28341
Метод двух указателей
Темы: "Два указателя"   

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

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

Выходные данные
Вывести длину наименьшей последовательности чисел, сумма которых больше K.
 
Ввод Вывод
6
7
3 1 3 2 4 3
3

ID 31782
Робот
Темы: "Два указателя"   

Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.
 
В процессе сборки двигателя могут встречаться операции 26 типов, которые обозначаются строчными буквами латинского алфавита. Процесс сборки состоит из N операций.
 
Предполагается использовать робота один раз для выполнения части подряд идущих операций из процесса сборки.
 
Память робота состоит из K ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы K + 1 операцию.
 
Требуется написать программу, которая по заданному процессу сборки определит количество экономически целесообразных способов использования робота.
 
Входные данные
В первой строке входного файла записано число K > 0 "— количество операций, которые можно записать в память робота.
 
Вторая строка состоит из N > K строчных латинских букв, обозначающих операции "— процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой.
 
Выходные данные
Выходной файл должен содержать единственное целое число "— количество экономически целесообразных способов использования робота.
 
Ввод Вывод
2
zabacabab
5
2
abc
0

ID 33139
Калитка в заборе
Темы: "Два указателя"   

Дядя Фёдор, кот Матроскин и Шарик решили обновить забор вокруг своего сада в Простоквашино. Матроскин и Шарик, недолго думая, вкопали N столбов вдоль одной из сторон участка. Это очень сильно расстроило Дядю Фёдора, так как его друзья забыли о самом главном — калитка должна находиться именно на этой стороне, и для неё необходимо было оставить проём шириной как минимум W. Теперь им придётся выкапывать некоторые столбы.
 
Чтобы работа не пропадала даром, выкопать надо как можно меньше столбов. Помогите Дяде Фёдору определить, какие именно столбы надо выкопать. После выкапывания столбов должен найтись промежуток (между двумя оставшимися столбами, или между оставшимся столбом и концом стороны участка, или между двумя концами стороны участка) ширины больше или равной W.
 
Входные данные
Первая строка содержит два целых числа N и W — количество вкопанных столбов и минимально необходимую ширину проёма для калитки соответственно. Гарантируется, что 0<=N<=30000 и что 0<=W<=60000.
 
Будем считать, что вдоль интересующей нас стороны участка введена ось координат. Во второй строке входного файла находятся два числа L и R — координаты левого и правого конца этой стороны (LR). Далее следуют N чисел — координаты вкопанных столбов. Все координаты (включая L и R) — различные целые числа, по модулю не превосходящие 30000. Гарантируется, что все столбы вкопаны между левым и правым концами стороны.
 
Выходные данные
В первой строке выходного файла должно быть минимальное число столбов, которые надо выкопать. Далее должны следовать номера этих столбов. Столбы нумеруются в том порядке, как они указаны во входном файле, начиная с 1.
 
Если решений несколько, то вы можете вывести любое. Если решения нет, то выведите в выходной файл одну строку, содержащую число -1.
 
Ввод Вывод
3 2
2 6
3 4 5
1
2
3 2
1 6
4 3 5
0
3 5
1 7
5 3 4
3
2
1
3

ID 33140
Кассы
Темы: "Два указателя"   

На одном из московских вокзалов билеты продают N касс. Каждая касса работает без перерыва определенный промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.
 
Входные данные
Сначала вводится одно целое число N (0<N<=10000).
 
В каждой из следующих N строк через пробел расположены 6 целых чисел, первые три из которых обозначают время открытия кассы в часах, минутах и секундах (часы — целое число от 0 до 23, минуты и секунды — целые числа от 0 до 59), оставшиеся три — время закрытия в том же формате. Числа разделены пробелами.
 
Время открытия означает, что в соответствующую ему секунду касса уже работает, а время закрытия — что в соответствующую секунду касса уже не работает. Например, касса, открытая с 10 ч 30 мин 30 с до 10 ч 35 мин 30 с, ежесуточно работает 300 секунд.
 
Если время открытия совпадает с временем закрытия, то касса работает круглосуточно. Если первое время больше второго, то касса начинает работу до полуночи, а заканчивает — на следующий день.
 
Выходные данные
Требуется вывести одно число — суммарное время за сутки (в секундах), на протяжении которого работают все N касс.
 
Ввод Вывод
3
1 0 0 23 0 0
12 0 0 12 0 0
22 0 0 2 0 0
7200
2
9 30 0 14 0 0
14 15 0 21 0 0
0
2
14 0 0 18 0 0
10 0 0 14 0 1
1

ID 33141
Имена
Темы: "Два указателя"   

На далекой планете Тау Кита есть непонятные нам обычаи. Например, таукитяне очень необычно для землян выбирают имена своим детям. Родители так выбирают имя ребенку, чтобы оно могло быть получено как удалением некоторого набора букв из имени отца, так и удалением некоторого набора букв из имени матери. Например, если отца зовут «abacaba», а мать — «bbccaa», то их ребенок может носить имена «a», «bba», «bcaa», но не может носить имена «aaa», «ab» или «bbc». Возможно, что имя ребенка совпадает с именем отца и/или матери, если оно может быть получено из имени другого родителя удалением нескольких (возможно, ни одной) букв.
 
Пусть отец по имени X и мать по имени Y выбирают имя своему новорожденному ребенку. Так как в таукитянских школах учеников часто вызывают к доске в лексикографическом порядке имен учеников, то есть в порядке следования имен в словаре, то они хотят выбрать своему ребенку такое имя, чтобы оно лексикографически следовало как можно позже.
 
- Формально, строка S лексикографически больше строки T, если выполняется одно из двух условий: строка T получается из S удалением одной или более букв с конца строки S;
- первые (i - 1) символов строк T и S не различаются, а буква в i-й позиции строки T следует в алфавите раньше буквы в i-й позиции строки S.

Требуется написать программу, которая по именам отца и матери находит лексикографически наибольшее имя для их ребенка.
 
Входные данные
Первая строка входного файла содержит X — имя отца. Вторая строка входного файла содержит Y — имя матери. Каждое имя состоит из строчных букв латинского алфавита, включает хотя бы одну букву и имеет длину не более 105 букв.
 
Выходные данные
Выходной файл должен содержать искомое лексикографически наибольшее из возможных имен ребенка. В случае, если подходящего имени для ребенка не существует, выходной файл должен быть пустым.
 
Ввод Вывод
abcabca
abcda
ca
ccba
accbbaa
ccba

ID 28331
Красота превыше всего
Темы: "Два указателя"   

В парке города Питсбурга есть чудесная аллея, состоящая из N посаженных в один ряд деревьев, каждое одного из K сортов. В связи с тем, что Питсбург принимает открытый чемпионат Байтландии по программированию, было решено построить огромную арену для проведения соревнований. Так, согласно этому плану вся аллея подлежала вырубке. Однако министерство деревьев и кустов воспротивилось этому решению, и потребовало оставить некоторые из деревьев в покое. Согласно новому плану строительства все деревья, которые не будут вырублены, должны образовывать один непрерывный отрезок, являющийся подотрезком исходного. Каждого из K видов деревьев требуется сохранить хотя бы по одному экземпляру. На вас возложена задача найти отрезок наименьшей длины, удовлетворяющий указанным ограничениям.
 
Входные данные
В первой строке входного файла находятся два числа N и K ( 1 ≤ N , K ≤ 250000 ). Во второй строке входного файла следуют N чисел (разделенных пробелами), i -ое число второй строки задает цвет i -ого слева дерева в аллее. Гарантируется, что присутствует хотя бы одно дерево каждого цвета
 
Выходные данные
В выходной файл выведите два числа, координаты левого и правого концов отрезка минимальной длины, удовлетворяющего условию. Если оптимальных ответов несколько, выведите любой.
 
Ввод Вывод
5 3
1 2 1 3 2
2 4
6 4
2 4 2 3 3 1
2 6

ID 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


 

ID 29640
Тихий дон №2
Темы: "Два указателя"    Префиксные суммы(минимумы, ...)   

Аксинья любит Григория, но она замужем за Степаном. Со своим мужем она несчастна, поэтому время, которое она проводит с ним можно характеризовать отрицательным показателем счастья Аксиньи (\(a_i < 0\)), а то время, которое она проводит с Григорием, - положительным показателем счастья (\(a_i > 0\)). Известно, что Аксинья проводит один день либо с мужем, либо с любовником. 

Найдите максимальное суммарное счастье за L дней, в которые Аксинья будет проводить с мужем не более C дней.
 
Входные данные
В первой строке подается 3 числа: N – кол-во дней, L и C (\(1 <= L, C <= N <= 1 000 000\)).
Во второй строке содержится N чисел a_i (\(1 <= |a_i| <= 1 000 000 000\)).

Входные данные
Требуется вывести ответ на задачу.
 

 

Примеры
Входные данные Выходные данные
1 5 3 3
1 -1 2 -2 3
3

ID 38347
Сложите конфетки
Темы: "Два указателя"   

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

Для этого Вася решил сыграть сам с собой в следующую игру. Он разложил конфеты на столе в несколько кучек, которые расположил в ряд. Если кучек не меньше двух, то из первой и последней в этом ряду кучек он выбирает ту, в которой меньше конфет. Пусть в наименьшей кучке оказалось B конфет. Тогда он B конфет перекладывает из первой кучки во вторую, и также B конфет перекладывает из последней кучки в предпоследнюю. При этом, естественно, одна из кучек (или даже две, если в первой и последней кучках конфет было поровну) становится пустой, и Вася забывает про ее существование. Он повторяет эти операции до тех пор, пока на столе не останется одна или две кучки.

Если останется одна кучка, то Вася все конфеты съест сам, а если две — то конфеты из первой кучки он съест сам, а из второй кучки отдаст Пете.

Напишите программу, которая по исходному распределению конфет в кучках определит, чем закончится Васина игра.

Входные данные
Начальное расположение кучек конфет будет описываться K парами чисел Ai, Ni, которые обозначают, что на столе выложено подряд Ni кучек конфет, по Ai конфет в каждой.

Во входном файле задано сначала число K (1≤K≤105). Затем идет K пар чисел Ai, Ni (1≤Ai≤100, 1≤Ni≤108). Общее количество кучек так же не превысит 108.

Выходные данные
В выходной файл выведите сначала 1 или 2 — количество кучек конфет, которые останутся в конце игры. Затем выведите соответственно одно или два числа — количества конфет в оставшихся кучках.

Примеры
Входные данные Выходные данные Пояснение
1 3
2 2
3 2
2 1
2
11 1
Исходно конфеты расположены в следующих кучках: 2 кучки по 2 конфеты, две кучки из 3-х конфет и одна из 2-х:
2 2 3 3 2
Далее по 2 конфеты перекладывается из 1 и 5кучек во 2 и 4, при этом и 1 и 5 кучки становятся пустыми, т.е. на столе остается только 3 кучки:
4 3 5
Теперь по 4 конфеты перекладываются из 1 и 3 кучек во 2-ю и на столе остается две кучки, игра заканчивается с результатом 11 1

 
2 1
1 7
1
7
Изначальноу нас 7 кучек по 1 конфете в каждой. После первого перекладывания получится следующая конфигурация:
2 1 1 1 1 2
После второго:
3 1 3
После третьего останется одна кучка с 7 конфетами.
3 5
1 1
2 1
3 1
4 1
5 2
2
15 5
Изначально имеется 6 кучек:
1 2 3 4 5 5
После первого перекладывания получим:
3 3 4 6 4
После второго:
6 4 9 1
После третьего:
5 5 10
Наконец, получим:
15 5