Contest.samsu.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача 3 регионального этапа Всероссийской олимпиады школьников по информатике 2011/2012 учебного года (offline)

Задачу добавил: alef

Успешно сдано решений: 10

Поврежденный XML

Входной файл:   input.txt
Выходной файл:    output.txt
Ограничение по времени:    2 секунды
Ограничение по памяти:    256 мегабайт


Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.
XML-строка состоит из открывающих и закрывающих тегов.
Открывающий тег начинается с открывающей угловой скобки (<), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка (>). Примеры открывающих тегов: <a>, <dog>.
Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш (/), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка. Примеры закрывающихся тегов: </a>, </dog>.
XML-строка называется корректной, если она может быть получена по следующим правилам:
•    Пустая строка является корректной XML-строкой.
•    Если A и B — корректные XML-строки, то строка AB, получающаяся приписыванием строки B в конец строки A, также является корректной
XML-строкой.
•    Если A — корректная XML-строка, то строка <X>A</X>, получающаяся приписыванием в начало A открывающегося тега, а в конец — закрывающегося с таким же именем, также является корректной XML-строкой. Здесь X — любая непустая строка из строчных букв латинского алфавита.
Например, представленные ниже строки:
<a></a>
<a><ab></ab><c></c></a>
<a></a><a></a><a></a>
являются корректными XML-строками, а такие строки как:
<a></b>
<a><b>
<a><b></a></b>
не являются корректными XML-строками.
Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.
Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.

Формат входного файла

Входной файл содержит одну строку, которая заменой ровно одного символа может быть превращена в корректную XML-строку. Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы латинского алфавита и символы «<» (ASCII код 60), «>»(ASCII код 62) и «/»(ASCII код 47).
Строка во входном файле заканчивается переводом строки.

Формат выходного файла

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

Пример входного файла - 1
<a></b>  

Пример выходного файла - 1
 <a></a>

Пример входного файла - 2
<a><aa>  

Пример выходного файла - 2
 <a></a>

Пример входного файла - 3
<a><>a>   

Пример выходного файла - 3
<a></a>

Пример входного файла - 4
<a/</a>  

Пример выходного файла - 4
 <a></a>

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

Сдать задачу

Задать вопрос жюри по этой задаче