Сортировка подсчетом


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


Условие задачи Прогресс
ID 34823. Имена на Тау Кита
Темы: Сортировка подсчетом   

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

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

Купцы хотят продать шаху n драгоценных камней, которые они привезли с собой. Для этого они выкладывают их перед шахом в ряд, после чего шах оценивает эти камни и принимает решение о том, купит он их или нет. Видов драгоценных камней на Востоке известно не очень много всего 26, поэтому мы будем обозначать виды камней с помощью строчных букв латинского алфавита. Шах обычно оценивает камни следующим образом. Он заранее определил несколько упорядоченных пар типов камней: (a1, b1), (a2, b2), ..., (ak, bk). Эти пары он называет красивыми, их множество мы обозначим как P. Теперь представим ряд камней, которые продают купцы, в виде строки S длины n из строчных букв латинского алфавита. Шах считает число таких пар (i,j), что 1 ≤ i < j ≤ n, а камни Si и Sj образуют красивую пару, то есть существует такое число 1 ≤ q ≤ k, что Si=aq и Sj=bq.

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


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

Первая строка входного файла содержит целые числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 676) число камней, которые привезли купцы и число пар, которые шах считает красивыми. Вторая строка входного файла содержит строку S, описывающую типы камней, которые привезли купцы.

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


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

В выходной файл выведите ответ на задачу — количество пар, которое должен найти визирь.


Примеры
входные данные
7 1
abacaba
aa

выходные данные
6

входные данные
7 3
abacaba
ab
ac
bb

выходные данные
7

ID 34820. Расшифровка письменности МАйя
Темы: Сортировка подсчетом   

Расшифровка письменности Майя оказалась более сложной задачей, чем предполагалось ранними исследованиями. На протяжении более чем двух сотен лет удалось узнать не так уж много. Основные результаты были получены за последние 30 лет.

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

Одна из проблем расшифровки письменности Майя заключается в определении этого порядка. Рисуя значки некоторого слова, писатели Майя иногда выбирали позиции для значков, исходя скорее из эстетических взглядов, а не определенных правил. Это привело к тому, что, хотя звуки для многих значков известны, археологи не всегда уверены, как должно произноситься записанное слово.

Археологи ищут некоторое слово W. Они знают значки для него, но не знают все возможные способы их расположения. Поскольку они знают, что Вы приедете на IOI ’06, они просят Вас о помощи. Они дадут Вам g значков, составляющих слово W, и последовательность S всех значков в надписи, которую они изучают, в порядке их появления. Помогите им, подсчитав количество возможных появлений слова W.

Задание

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


Ограничения

1 ≤ g ≤ 3 000, g – количество значков в слове W

g ≤ |S| ≤ 3 000 000 где |S| – количество значков в последовательности S


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

На вход программы поступают данные в следующем формате:

СТРОКА 1: Содержит два числа, разделенных пробелом – g и |S|.
СТРОКА 2: Содержит g последовательных символов, с помощью которых записывается слово W . Допустимы символы: ‘a’-‘z’ и ‘A’-‘Z’; большие и маленькие буквы считаются различными.
СТРОКА 3: Содержит |S| последовательных символов, которые представляют значки в надписи. Допустимы символы: ‘a’-‘z’ и ‘A’-‘Z’; большие и маленькие буквы считаются различными.


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

Единственная строка выходных данных программы должна содержать количество возможных вхождений слова W в S.


Важно для программирования на PASCAL

По умолчанию во FreePascal переменная типа string имеет ограничение размера в 255 символов. Если Вы хотите использовать более длинные строки, Вы должны добавить директиву {$ H +} в ваш код, сразу после строки program ...;.


Примеры
входные данные
4 11
cAda
AbrAcadAbRa

выходные данные
2

ID 34824. Списки по классам
Темы: Сортировка подсчетом   

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

В каждой строке сначала записан номер класса (число, равное 9, 10 или 11), затем (через пробел) — фамилия ученика.

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

Необходимо вывести список школьников по классам: сначала всех учеников 9 класса, затем — 10, затем — 11. Внутри одного класса порядок вывода фамилий должен быть таким же, как на входе.

Примеры

входные данные
9 Ivanov
10 Petrov
11 Sidorov
9 Grigoryev
9 Sergeev
10 Yakovlev

выходные данные
9 Ivanov
9 Grigoryev
9 Sergeev
10 Petrov
10 Yakovlev
11 Sidorov

ID 34818. Гистограмма
Темы: Сортировка подсчетом   

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

Входные данные
Входной файл содержит зашифрованный текст сообщения. Он содержит строчные и прописные латинские буквы, цифры, знаки препинания («.», «!», «?», «:», «-», «,», «;», «(», «)»), пробелы и переводы строк. Размер входного файла не превышает 104 байт. Текст содержит хотя бы один непробельный символ. Все строки входного файла не длиннее 200 символов.

Выходные данные
Для каждого символа c кроме пробелов и переводов строк выведите столбик из символов «#», количество которых должно быть равно количеству символов c в данном тексте. Под каждым столбиком напишите символ, соответствующий ему. Отформатируйте гистограмму так, чтобы нижние концы столбиков были на одной строке, первая строка и первый столбец были непустыми. Не отделяйте столбики друг от друга. Отсортируйте столбики в порядке увеличения кодов символов.

Пример
Входные данные Выходные данные
Hello, world!
     #   
     ##  
#########
!,Hdelorw
Twas brillig, and the slithy toves
Did gyre and gimble in the wabe;
All mimsy were the borogoves,
And the mome raths outgrabe.
         #              
         #              
         #              
         #              
         #              
         #         #    
         #  #      #    
      #  # ###  ####    
      ## ###### ####    
      ##############    
      ##############  ##
#  #  ############## ###
########################
,.;ADTabdeghilmnorstuvwy

ID 34880. Жребий Крижановского
Темы: Сортировка подсчетом   

Петя играет с друзьями в игру, которую иногда называют "Жребий Крижановского". Правила игры следующие: в каждом туре каждый игрок загадывает произвольное натуральное число. После этого игрок, загадавший минимальное число, которое не повторяется, выигрывает в этом туре, причем его выигрыш равен этому числу. Например, если играют 6 человек и были загаданы числа 3, 2, 1, 1, 4 и 2, то выиграл первый игрок, причем его выигрыш равен 3. Если все загаданные числа повторяются, то тур считается ничейным и никто баллов не получает.

Общий выигрыш игрока за игру равен сумме баллов за все сыгранные туры.

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

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

Входные данные
В первой строке вводится число n - количество игроков (2 <= n <= 100). Вторая строка содержит n чисел - баллы игроков перед последним туром (неотрицательные целые числа, не большие 100). Баллы перечислены в том порядке, в котором игроки обычно называют числа (то есть Петины баллы указаны последними). В третьей строке задано (n-1) число - числа, названные игроками в последнем туре (числа не превышают 100), в том порядке, в котором они их называли.

Выходные данные
Выведите число, которое следует назвать Пете.

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

Ввод Вывод
6
0 0 0 0 0 0
2 3 4 5 6
1
6
8 3 12 5 0 9
2 1 3 1 4
2

ID 34825. Мегавзлом
Темы: Сортировка подсчетом   

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

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

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

Единственная строка входных данных содержит строку s — сообщение в телефоне Егора (1 ≤ |s| ≤ 105). Гарантируется, что s содержит только маленькие латинские буквы.

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

Выведите кодовую фразу от Серёжиного банковского счёта.


Примеры

входные данные
qwerty
выходные данные
ywtrqe

входные данные
onehundredseventynine
выходные данные
yvutsronnnnniheeeeedd

ID 34822. Арифметика Саши и Кати
Темы: Сортировка подсчетом   

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

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

Вводятся два целых неотрицательных числа A и B (каждое число в одной строке). Длина каждого из чисел не превосходит 100 000 цифр.

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

Выведите одно число — максимальное целое число, которое можно составить используя как цифры первого числа, так и цифры второго числа. Если же ни одного такого числа составить нельзя, выведите -1.

Примеры тестов

входные данные

280138
798081
выходные данные
8810

входные данные
123
456
выходные данные
-1

ID 34819. Головоломка
Темы: Сортировка подсчетом   

Петя разгадывает головоломку, которая устроена следующим образом. Дана квадратная таблица размера NxN, в каждой клетке которой записана какая-нибудь латинская буква. Кроме того, дан список ключевых слов. Пете нужно, взяв очередное ключевое слово, найти его в таблице. То есть найти в таблице все буквы этого слова, причем они должны быть расположены так, чтобы клетка, в которой расположена каждая последующая буква слова, была соседней с клеткой, в которой записана предыдущая буква (клетки называются соседними, если они имеют общую сторону — то есть соседствуют по вертикали или по горизонтали). Например, на рисунке ниже показано, как может быть расположено в таблице слово olympiad.
P O L T E
R W Y M S
O A I P T
B D A N R
L E M E S
Когда Петя находит слово, он вычеркивает его из таблицы. Использовать уже вычеркнутые буквы в других ключевых словах нельзя.
После того, как найдены и вычеркнуты все ключевые слова, в таблице остаются еще несколько букв, из которых Петя должен составить слово, зашифрованное в головоломке.
Помогите Пете в решении этой головоломки, написав программу, которая по данной таблице и списку ключевых слов выпишет, из каких букв Петя должен сложить слово, то есть какие буквы останутся в таблице после вычеркивания ключевых слов.

Входные данные
В первой строке входного файла записаны два числа N (1?N?10) и M (0?M?200). Следующие N строк по N заглавных латинских букв описывают ребус. Следующие M строк содержат слова. Слова состоят только из заглавных латинских букв, каждое слово не длиннее 200 символов. Гарантируется, что в таблице можно найти и вычеркнуть по описанным выше правилам все ключевые слова.
Выходные данные
В единственную строку выходного файла выведите в любом порядке буквы, которые останутся в таблице.

Примеры
входные данные
5 3
POLTE
RWYMS
OAIPT
BDANR
LEMES
OLYMPIAD
PROBLEM
TEST
выходные данные
AENRSW

ID 38571. Автобусы
Темы: Сортировка подсчетом    Жадный алгоритм    Сканирующая прямая   

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

Более того, было решено заменить весь автобусный парк одинаковыми новыми, очень дорогими, но гораздо более надежными, красивыми и удобными машинами.

Автобусная сеть страны охватывает N городов, занумерованных целыми числами от 1 до N.

Идеальное расписание содержит M ежедневных рейсов, i-й рейс начинается в городе Fi в момент времени Xi и заканчивается в некотором другом городе Gi в момент времени Yi. Продолжительность каждого рейса ненулевая и строго меньше 24 часов. Рейс i выполняется одним из автобусов, находящихся в момент времени Xi в городе Fi.

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

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

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

Входные данные
В первой строке задаются целые числа N и М (1 ≤ N, M ≤ 100 000) — количество городов и рейсов автобусов соответственно.

В каждой из следующих M строк содержится описание рейса автобуса: номер города отправления Fi, время отправления Xi, номер города назначения Gi (Fi ≠ Gi), время прибытия Yi, отделенные друг от друга одним пробелом. Время прибытия и отправления задается в формате HH:MM, где HH — часы от 00 до 23, MM — минуты от 00 до 59.

Выходные данные
Выведите одно число — минимально необходимое количество автобусов. Если расписание невозможно обслуживать в течение неограниченного периода времени конечным числом автобусов, выведите число -1.

Примеры
Входные данные Выходные данные
1 4 6
1 10:00 2 12:00
1 10:00 3 09:00
3 12:00 4 23:00
2 11:00 4 13:00
4 12:00 1 11:00
4 12:00 1 10:30
8

ID 38535. Пожиратель карт
Темы: Конструктив    Сортировка подсчетом   

Ушан решил сыграть в карточную игру. У него есть колода, состоящая из N съедобных карт. На i-й карте сверху написано целое число Ai. Ушан выполняет описанную ниже операцию ноль или более раз, так что значения, записанные на оставшихся карточках, будут попарно различны.
Найдите максимально возможное количество оставшихся карт. Здесь N нечетное, что гарантирует сохранение хотя бы одной карты. 
Операция: вынуть из колоды три произвольные карты. Из этих трех карт съешьте две: одну с наибольшим значением, а другую с наименьшим значением. Затем верните оставшуюся одну карту в колоду.

Входные данные
В первой строке записано нечетное число N (\(3<=N<=10^5\)). Во второй строке записаны N чисел A(\(1<=A_i<=10^5\))

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

 

Примеры
Входные данные Выходные данные Пояснения
1 5
1 2 1 3 7
3 Оптимальное решение - выполнить операцию один раз, вынув две карты с 1 и одну карту с 2. Одна карта с 1 и другая с 2 будут съедены, а оставшаяся карта с 1 будет возвращена в колоду.
Тогда значения, написанные на оставшихся картах в колоде, будут попарно различными: 1, 3 и 7.
2 15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1
7  

 

ID 38992. Аэропорт
Темы: Сканирующая прямая    Сортировка подсчетом   

В аэропорту города Че ежедневно записываются данные прилета и вылета самолетов. В файле содержится информация за один день. Определите максимальное число самолетов, которые находились в аэропорту одновременно и в течении какого максимального промежутка времени (в минутах) находилось в аэропорту такое число самолетов. Учитываются только самолеты, информация о которых записана в файле.

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

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

Файл к заданию
 

Примеры
Входные данные Выходные данные
1 6
09:00 10:07
10:20 11:35
12:00 17:00
11:00 11:30
11:20 12:30
11:30 18:15
4 1

ID 39022. Гимнастические ленты. Тренировочное задание - 3
Темы: Сортировка подсчетом    ЕГЭ   

Для выступления гимнастки используют ленты, которые после выступления кладут на стол. Папа самой лучшей гимнастки Анны К. в ожидании награждения решил записывать координаты начала и конца лент. У вас есть файл с данной информацией. Определите в скольки точках стола получилась самая большая толщина покрытия и чему она равна. Стол имеет длину Lмм. По окончании выступления всех гимнасток, на столе оказалось N лент. Никакая лента не вылезает за границы стола. Все ленты лежат горизонтально. Ленты складываются друг на друга. 
 
Входные данные
В первой строке файла записаны два числа - L, N (1 <= L <= 10000, 1 <= N <= 10000). В слеующих строках записаны по 2 числа - l, r (1 <= l <= r <= L) - левые и правые концы лент относительно левого края стола.

В ответе укажите два числа через пробел - максимальную толщину ленточного покрытия стола и количество точек с такой толщиной. 
 
Примеры
Входные данные Выходные данные
1
39 4
3 21
3 15
2 20
3 17
4 13


Файл к заданию

ID 39226. Гимнастические ленты
Темы: Сортировка подсчетом    ЕГЭ   

Для выступления гимнастки используют ленты, которые после выступления кладут на стол. Папа самой лучшей гимнастки Анны К., в ожидании награждения, решил записывать координаты начала и конца лент. Если лента свисала с левого края стола, то он ставил левую координату равной нулю, если лента свисала с правого конца стола, то он ставил правую координату равной нулю. Если лента свисала с двух сторон, то он записывал обе координаты равной нулю. У вас есть файл с данной информацией. Определите, в скольки точках стола получилась самая большая толщина покрытия и чему она равна. Стол имеет длину Lмм. По окончании выступления всех гимнасток, на столе оказалось N лент. У некоторых лент свисает со стола только один конец, у некоторых оба. Все ленты лежат горизонтально. Ленты складываются друг на друга. 
 
Входные данные
В первой строке файла записаны два числа - L, N (1 <= L <= 10000, 1 <= N <= 10000). В слеующих строках записаны по 2 числа - l, r (1 <= l <= r <= L) - левые и правые концы лент относительно левого края стола.

В ответе укажите два числа через пробел - максимальную толщину ленточного покрытия стола и количество точек с такой толщиной. 
 
Примеры
Входные данные Выходные данные
1
39 4
3 21
3 15
2 20
3 17
4 13


Файл к заданию

ID 29468. Носки
Темы: Сортировка подсчетом   

Имеется стол длины L. На столе разложено N носков так, что никакой носок не вылезает за границы стола. Далее имеется умный мальчик Васёк, который хочет (сугубо в корыстных целях) замерить толщину покрытия стола носками в M точках.
 
Входные данные
Во входном файле даны сначала L, N, M (1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000).
 
Далее идут N пар чисел l ≤ r от 1 до L – левые и правые концы носков.
 
Затем идут M чисел от 1 до L интересующие Васька точки.
 
Выходные данные
Выведите M чисел – толщину носкового покрытия в каждой точке.
 
Ввод Вывод
39 4 7
3 21
3 15
2 20
3 17
4
17
33
5
9
25
37
4
3
0
4
4
0
0