eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Восстановление HTML файла

Восстановление HTML файла

Петя недавно скачал поврежденный HTML файл. Он выглядит как обычный HTML файл, но в нем есть некоторые несоответствия тэгов. Ваша задача - удалив минимальное количество открывающихся и закрывающихся тэгов сделать так, чтобы структура тэгов стала правильной. Более формально, HTML файл состоит из произвольных символов с ASCII кодами из диапазона от \textbf{32} до \textbf{126}, а также Linux-style переводов строки (символов с кодом \textbf{10}). Тэги открываются следующим образом: <\textbf{Имя тэга Параметры}> и закрываются следующим образом <\textbf{Имя тэга}>. \textbf{Имя тега} - строка, состоящая из больших и маленьких латинских букв, которые считаются различными. \textbf{Имя тэга} отделяется от \textbf{Параметров} как минимум одним пробелом (но не переводом сроки). Параметры могут содержать произвольные допустимые ASCII символы кроме \textbf{<}, \textbf{>} и переводов строк. Также допускаются открывающиеся тэги без параметров и записываются в следующей форме: <\textbf{Имя Тэга}>. HTML файл счиается правильным, если каждому открывающемуся тэгу можно привести в соответствие следующий далее в файле закрывающийся тэг таким образом, чтобы часть файла между этими тэгами также представляла собой правильный HTML файл, и аналогично можно привести в соответствие каждому закрывающемуся тэгу ровно один окрывающийся тэг идущий ранее в файле. HTML файл, не содержащий тэгов, также является правильным. Окрывающийся тэг считается соответствующим закрывающемуся, если у них одинаковое имя тэга. \InputFile Входной файл представляет из себя поврежденный HTML файл, который требуется исправить. Его длина не превосходит \textbf{10000} байт. Количество открывающихся и закрывающихся тэгов не превышает \textbf{500}. Символы \textbf{<} и \textbf{>} не встречаются нигде, кроме окрывающихся и закрывающихся тэгов. \OutputFile Выведите единственное целое число - минимальное количество окрывающихся/закрывающихся тэгов, которые требуется удалить, чтобы файл оказался правильным HTML файлом.
Лимит времени 2 секунды
Лимит использования памяти 64 MiB
Входные данные #1
<a href=http://kruzhok.newmail.ru>
<b someone has corrupted this file>
It was a good file before...
</a>
</b>
Выходные данные #1
2