ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1177. Сопоставление с шаблоном

An attempt to make the problem statement clear finally (+)
Послано Michael Rybak (accepted@ukr.net) 16 окт 2004 00:21
As this problem's statement is really hard to interpret unambiguously, I've decided to make this attempt to explain my view on it, which seems to be the one that authors meant.
 Here’s the list of notes that make the problem more clear:

in template:
1. Brackets ‘[]’ have the highest priority. Find the leftmost ‘[‘, then find the first ‘]’ after it; you can assume that these two brackets strictly correspond to each other, i.e. can’t be considered to correspond to any other brackets. Then find the first opening bracket after current closing one and so on.
2. Such templates, as [] and [^] are incorrect and don’t happen in test cases.
3. Given an opening bracket [ and a corresponding closing bracket ], let’s consider the string S between them. As Vladimir Yakovlev already stated, special characters '[', '%' and '_' mean themselves when included in brackets. Now, let’s describe a boolean function F(c,s), that determines whether template s matches character c. "Del(s,k)" will denote a function, that returns the tail of s starting from position k+1 inclusively. We shall also need a boolean function G:

F:
If s[1]='^', Then F(c,s):=Not G(c,Del(s,1)), Else F(c,s):=G(c,s)

G:
If s[2]='–' and length(s)>=3 Then G(c,s):=G(c,Del(s,3)) Or (s[1]<=c<=s[3])
            Else G(c,s)=G(c,Del(s,1)) Or (s[1]=c)

To my mind, these rules do make the problem statement clear and have nothing to deal with posting Source code, so I hope moderators won’t delete this message. I also want to say thank you to the person posting under nick "I have answers to all your questions :)" for helping people on this problem. In fact, your posts helped me to understand it.
I agree with this explanation (-)
Послано Vladimir Yakovlev (USU) 16 окт 2004 01:57
Re: An attempt to make the problem statement clear finally (+)
Послано Samsonov Alex [USU] 1 авг 2006 22:04
Thank you very much for your help. I can't imagine how much time it would take me to understand all this stuff. I think that the problem statement should be fixed. Or, should have the link to your post :)
Re: An attempt to make the problem statement clear finally (+)
Послано Denis Koshman 20 авг 2008 17:23
Thanks :)
Re: An attempt to make the problem statement clear finally (+)
Послано LLI_E_P_JI_O_K 7 авг 2015 20:03
Thank you for formalized statement =) very useful!