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


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Имена

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

На далекой планете Тау Кита есть непонятные нам обычаи. Например, таукитяне очень необычно для землян выбирают имена своим детям. Родители так выбирают имя ребенку, чтобы оно могло быть получено как удалением некоторого набора букв из имени отца, так и удалением некоторого набора букв из имени матери. Например, если отца зовут «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

Распродажа

"Два указателя" Словари

В магазине проходит новогодняя распродажа – цены всех товаров снижены на 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.

Тихий дон №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).

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

Ввод Вывод
5 3 3
1 -1 2 -2 3
3

 
(с) Шалдин В., 2018

Ослабление флота

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

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

Формат входных данных
В первой строке дано одно натуральное число 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


 

Красота превыше всего

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

В парке города Питсбурга есть чудесная аллея, состоящая из 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

Метод двух указателей

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

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

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

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

Робот

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

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

Калитка в заборе

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

Дядя Фёдор, кот Матроскин и Шарик решили обновить забор вокруг своего сада в Простоквашино. Матроскин и Шарик, недолго думая, вкопали 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

Кассы

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

На одном из московских вокзалов билеты продают 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