Страница: << 1 2 3 Отображать по:

#111182

Числа

Темы: [Сортировка подсчетом]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2012, Задача B ]

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

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

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

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

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

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

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

280138
798081

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

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

123
456

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

-1

Примечание

Online-группа тестов оценивается в 60 баллов, в этой группе числа A и B содержат не более 1000 цифр каждое. При этом решения, правильно работающие для случая, когда A и B содержат не более 6 цифр, будут оценены не менее, чем в 20 баллов. Решения, правильно работающие для случая, когда A и B содержат не более 9 цифр, будут оценены не менее, чем в 40 баллов.

Offline-группа тестов оценивается в 40 баллов.

#111493

Имена

Темы: [Сортировка подсчетом]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2013, 2 день, Задача B ]

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

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

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

Система оценивания

Правильные решения для тестов, в которых имена содержат только буквы «a» и «b» и имеют длину не более 1000, будут оцениваться из 20 баллов.

Правильные решения для тестов, в которых имена содержат только буквы «a» и «b» и имеют длину не более \(10^5\), будут оцениваться из 40 баллов.

Правильные решения для тестов, в которых имена имеют длину не более 1000, будут оцениваться из 40 баллов.

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

Примеры

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

abcabca
abcda

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

ca

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

ccba
accbbaa

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

ccba

#112041

Кондиционеры

Темы: [Сортировка подсчетом]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2014, 2 день, Задача B ]

При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.

Все классы школы пронумерованы последовательно от 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 баллов.

Примеры

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

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

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

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

#113101

Счет в гипершашках

Темы: [Сортировка подсчетом] [Перестановки]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2016, 2 день, Задача B ]

Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал \(a\) баллов, второй — \(b\), а третий \(c\), то говорят, что игра закончилась со счетом \(a:b:c\).

Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в \(k\) раз.

После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа \(x_1, x_2, …, x_n\). Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.

Требуется написать программу, которая по числу \(k\) и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.

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

Первая строка входного файла содержит два целых числа: \(n\) и \(k (3 \le n \le 100 000, 1 \le k \le 10^9\) ).

Вторая строка входного файла содержит \(n\) целых чисел \(x_1, x_2, …, x_n (1 \le x_i \le 10^9 )\).

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

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

Пояснение к примеру

В приведенном примере Андрей сможет показать следующие варианты счета: 1:1:2, 1:2:1, 2:1:1, 1:2:2, 2:1:2, 2:2:1, 2:2:3, 2:3:2, 3:2:2. Другие тройки чисел, которые можно составить с использованием имеющихся карточек, не удовлетворяют заданному условию, что баллы любых двух игроков различаются не более чем в \(k\) = 2 раза.

Описание подзадач и системы оценивания

В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Подзадача 1 (15 баллов)

\(3 \le n \le 100 000, k = 1, 1 \le x_i \le 100 000\)

Подзадача 2 (23 балла)

\(3 \le n \le 100, k \le 100, 1 \le x_i \le 100\)

Подзадача 3 (30 баллов)

\(3 \le n \le 100 000, k \le 10^9 \le x_i \le 10^9\), все \(x_i\) различны

Подзадача 4 (32 балла)

\(3 \le n \le 100 000, k \le 10^9 \le x_i \le 10^9\)

Примеры

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

5 2
1 1 2 2 3

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

Страница: << 1 2 3 Отображать по:

Выбрано

Отменить

Добавить в контест