Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1899. Имена
Жадные алгоритмыОлимпиадные задачи на русском языке
| 21/01/2013 | Областная олимпиада школьников по информатике. II тур. (6) |
| 10/07/2017 | Лето 2017 - 8 (C) |
| 07/07/2023 | Лето 2023-6 сложные (командное) (I) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
На далекой планете Тау Кита есть непонятные нам обычаи. Например, таукитяне очень необычно для землян
выбирают имена своим детям. Родители так выбирают имя ребенку, чтобы оно могло быть получено как удалением
некоторого набора букв из имени отца, так и удалением некоторого набора букв из имени матери. Например, если
отца зовут "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` букв.
Формат выходного файла
Выходной файл должен содержать искомое лексикографически наибольшее из возможных имен ребенка. В случае, если
подходящего имени для ребенка не существует, выходной файл должен быть пустым (или его единственная строка должна быть пустой).
Пример ввода 1
abcabca abcda
Пример вывода 1
ca
Пример ввода 2
ccba accbbaa
Пример вывода 2
ccba
Пояснения к примеру
В первом примере имя ребенка не может начинаться с буквы большей с, так как имя отца не содержит таких
букв. Буква с содержится в обоих именах, следовательно, имя ребенка может начинаться с этой буквы.
Единственная буква, которая может идти следом за буквой с в имени ребенка — это буква a.
Система оценивания
Правильные решения для тестов, в которых имена содержат только буквы a и b и имеют длину не
более 1000, будут оцениваться из 20 баллов.
Правильные решения для тестов, в которых имена содержат только буквы a и b и имеют длину не
более `10^5`, будут оцениваться из 40 баллов.
Правильные решения для тестов, в которых имена имеют длину не более 1000, будут оцениваться из 40 баллов.
Несмотря на выделение отдельных групп тестов, на окончательную проверку будут приниматься только решения, правильно работающие для всех тестов, приведенных в условии задачи.
Источник: региональный этап Всероссийской олимпиады по информатике 2012/2013, http://neerc.ifmo.ru/school/ 