Codeforces Round 256 (Div. 2) |
---|
Закончено |
Бизон-Чемпион не только бизон, но и любимец команды «Бизоны».
На очередном соревновании «Бизонам» попалась следующая задача: «Даны два различных слова (строки из латинских букв) s и t. Необходимо из слова s получить слово t». Задача показалась ребятам простой, ведь они хорошо знают суффиксные структуры данных. Бизон Старший любит суффиксный автомат. Применяя его один раз к строке, он может удалить из этой строки любой один символ. Бизон Средний хорошо знает суффиксный массив. Применяя его один раз к строке, он может поменять местами два любых символа в этой строке. Суффиксным деревом ребята не владеют, а с его помощью можно сделать гораздо большее.
Бизону-Чемпиону интересно, смогут ли «Бизоны» решить задачу. При этом, возможно, для решения задачи не требуются обе структуры данных. Выясните, смогут ли ребята решить задачу и если да, то как: можно ли решить ее только с помощью суффиксного автомата, только с помощью суффиксного массива или потребуются обе структуры? Обратите внимание, что структуры разрешается использовать неограниченное количество раз и в любом порядке.
В первой строке содержится непустое слово s. Во второй строке содержится непустое слово t. Слова s и t различны. Каждое слово состоит только из строчных букв латинского алфавита. Каждое слово содержит не более 100 букв.
В единственную строку выведите ответ на задачу. Выведите «need tree» (без кавычек), если из слова s невозможно получить слово t, используя суффиксный массив и суффиксный автомат. Выведите «automaton» (без кавычек), если для решения задачи достаточно только суффиксного автомата. Выведите «array» (без кавычек), если для решения задачи достаточно только суффиксного массива. Выведите «both» (без кавычек), если для решения задачи необходимы обе эти структуры данных.
Гарантируется, что если можно решить задачу только с использованием суффиксного массива, то решить задачу только с использованием суффиксного автомата невозможно. Аналогичное верно и для суффиксного автомата.
automaton
tomat
automaton
array
arary
array
both
hot
both
need
tree
need tree
В третьем примере можно действовать так: сначала превратить «both» в «oth», удалив первый символ с помощью суффиксного автомата, а потом сделать два обмена символов получившейся строки с помощью суффиксного массива и получить «hot».
Название |
---|