На далекой планете Тау Кита есть непонятные нам обычаи. Например, таукитяне очень необычно для землян выбирают имена своим детям. Родители так выбирают имя ребенку, чтобы оно могло быть получено как удалением некоторого набора букв из имени отца, так и удалением некоторого набора букв из имени матери. Например, если отца зовут «abacaba», а мать — «bbccaa», то их ребенок может носить имена «a», «bba», «bcaa», но не может носить имена «aaa», «ab» или «bbc». Возможно, что имя ребенка совпадает с именем отца и/или матери, если оно может быть получено из имени другого родителя удалением нескольких (возможно, ни одной) букв.
Пусть отец по имени X и мать по имени Y выбирают имя своему новорожденному ребенку. Так как в таукитянских школах учеников часто вызывают к доске в лексикографическом порядке имен учеников, то есть в порядке следования имен в словаре, то они хотят выбрать своему ребенку такое имя, чтобы оно лексикографически следовало как можно позже.
Требуется написать программу, которая по именам отца и матери находит лексикографически наибольшее имя для их ребенка.
Первая строка входного файла содержит X — имя отца. Вторая строка входного файла содержит Y — имя матери. Каждое имя состоит из строчных букв латинского алфавита, включает хотя бы одну букву и имеет длину не более \(10^5\) букв.
Выходной файл должен содержать искомое лексикографически наибольшее из возможных имен ребенка. В случае, если подходящего имени для ребенка не существует, выходной файл должен быть пустым.
Правильные решения для тестов, в которых имена содержат только буквы «a» и «b» и имеют длину не более 1000, будут оцениваться из 20 баллов.
Правильные решения для тестов, в которых имена содержат только буквы «a» и «b» и имеют длину не более \(10^5\), будут оцениваться из 40 баллов.
Правильные решения для тестов, в которых имена имеют длину не более 1000, будут оцениваться из 40 баллов.
Несмотря на выделение отдельных групп тестов, на окончательную проверку будут приниматься только решения, правильно работающие для всех тестов, приведенных в условии задачи.
abcabca abcda
ca
ccba accbbaa
ccba
В каждой строке сначала записан номер класса (число, равное 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
У Егора очень старый телефон. Слава отправил Егору кодовую фразу от Серёжиного банковского счёта, чтоб его ограбить, но телефон Егора настолько стар, что не умеет принимать длинные сообщения. Он разбивает их на несколько маленьких случайной длины, и приходят они ему в случайном порядке.
Когда Егор получил все эти сообщения, он по-настоящему расстроился. Он проклинал телефон, кидал его об стену. К несчастью, телефон оказался обидчивым и перемешал ещё и все буквы в каждом сообщении, хоть и склеил при этом все сообщения в одно. Егор знал, что Серёжа любит такие строки, что в них все буквы идут по убыванию (в обратном алфавитном порядке). Помогите Егору и Славе и найдите кодовую фразу от Серёжиного банковского счёта по единственному оставшемуся сообщению в телефоне.
Единственная строка входных данных содержит строку s — сообщение в телефоне Егора (1 ≤ |s| ≤ 105). Гарантируется, что s содержит только маленькие латинские буквы.
Выведите кодовую фразу от Серёжиного банковского счёта.
qwerty
ywtrqe
onehundredseventynine
yvutsronnnnniheeeeedd
При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.
Все классы школы пронумерованы последовательно от 1 до \(n\). Известно, что для каждого класса с номером \(i\), требуется ровно один кондиционер, мощность которого больше или равна \(a_i\) ватт.
Администрации школы предоставили список из \(m\) различных моделей кондиционеров, которые можно закупить. Для каждой модели кондиционера известна его мощность и стоимость. Требуется написать программу, которая определит, за какую минимальную суммарную стоимость кондиционеров можно оснастить все классы школы.
Первая строка входного файла содержит одно целое число n (1 ≤ \(n\) ≤ 50 000) количество классов в школе.
Вторая строка содержит \(n\) целых чисел \(a_i\) (1 ≤ \(a_i\) ≤ 1000)- минимальная мощность кондиционера в ваттах, который можно установить в классе с номером \(i\).
Третья строка содержит одно целое число \(m\) (1 ≤ \(m\) ≤ 50 000) - количество предложенных моделей кондиционеров.
Далее, в каждой из \(m\) строк содержится пара целых чисел \(b_j\) и \(c_j\) (1 ≤ \(b_j\) ≤ 1000, 1 ≤ \(c_j\) ≤ 1000) мощность в ваттах \(j\)-й модели кондиционера и его цена в рублях соответственно.
Выходной файл должен содержать одно число минимальную суммарную стоимость кондиционеров в рублях. Гарантируется, что хотя бы один корректный выбор кондиционеров существует, и во всех классах можно установить подходящий кондиционер.
В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.
Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе – кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).
Частичные решения для \(n\), \(m\) ≤ 1000 будут оцениваться из 50 баллов.
1 800 1 800 1000
1000
3 1 2 3 4 1 10 1 5 10 7 2 3
13
Поразрядная сортировка является одним из видов сортировки, которые работают за линейное от размера сортируемого массива время. Такая скорость достигается за счет того, что эта сортировка использует внутреннюю структуру сортируемых объектов. Изначально этот алгоритм использовался для сортировки перфокарт. Первая его компьютерная реализация была создана в университете MIT Гарольдом Сьюардом (Harold Н. Seward). Опишем алгоритм подробнее. Пусть задан массив строк s 1 , ..., s i причем все строки имеют одинаковую длину m . Работа алгоритма состоит из m фаз. На i -ой фазе строки сортируются па i -ой с конца букве. Происходит это следующим образом. Будем, для простоты, в этой задаче рассматривать строки из цифр от 0 до 9. Для каждой цифры создается «корзина» («bucket»), после чего строки s i распределяются по «корзинам» в соответствии с i -ой с конца цифрой. Строки, у которых i -ая с конца цифра равна j попадают в j -ую корзину (например, строка 123 на первой фазе попадет в третью корзину, на второй — во вторую, на третьей — в первую). После этого элементы извлекаются из корзин в порядке увеличения номера корзины. Таким образом, после первой фазы строки отсортированы по последней цифре, после двух фаз - по двум последним, ..., после m фаз - по всем. При важно, чтобы элементы в корзинах сохраняли тот же порядок, что и в исходном массиве (до начала этой фазы). Например, если массив до первой фазы имеет вид: 111,112,211, 311, то элементы по корзинам распределятся следующим образом: в первой корзине будет. 111,211,311, а второй: 112. Ваша задача состоит в написании программы, детально показывающей работу этого алгоритма на заданном массиве.
Первая строка входного файла содержит целое число n (1 ≤ n ≤ 1000) . Последующие n строк содержат каждая по одной строке s i . Длины всех s i , одинаковы и не превосходят 20. Все s i состоят только из цифр от 0 до 9.
В выходной файл выведите исходный массив строк в, состояние «корзин» после распределения элементов по ним для каждой фазы и отсортированный массив. Следуйте формату, приведенному в примере.
9 12 32 45 67 98 29 61 35 09
Initial array: 12, 32, 45, 67, 98, 29, 61, 35, 09 ********** Phase 1 Bucket 0: empty Bucket 1: 61 Bucket 2: 12, 32 Bucket 3: empty Bucket 4: empty Bucket 5: 45, 35 Bucket 6: empty Bucket 7: 67 Bucket 8: 98 Bucket 9: 29, 09 ********** Phase 2 Bucket 0: 09 Bucket 1: 12 Bucket 2: 29 Bucket 3: 32, 35 Bucket 4: 45 Bucket 5: empty Bucket 6: 61, 67 Bucket 7: empty Bucket 8: empty Bucket 9: 98 ********** Sorted array: 09, 12, 29, 32, 35, 45, 61, 67, 98