ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > ВКОШП 2015 > задача:


09. Задача 2016.10

Задачи сборника

• Задача 01
• Задача 03
• Задача 05
• Задача 06
• Задача 07
• 04. Задача 04
• 08. Задача 08
• 09. Задача 2016.10
• 1013. Задача 02

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 40000/40000/40000/40000 мс. Лимит памяти 10340/65000/65000/65000 Кб.
По материалам олимпиады в Болгарии. Сложность Гамма

Мурмарианские археологи обнаружили очень древнюю библиотеку с огромным количеством странных глиняных табличек. Каждая такая табличка состоит из букв латинского алфавита. В ходе продолжительного анализа ученые выяснили, что в каждой такой табличке можно найти обычные слова их языка. Ученые обратились к вам с просьбой помочь автоматизировать процесс обнаружения некоторых слов в найденных табличках.
Каждая табличка представляет собой квадратную матрицу букв латинского алфавита в верхнем регистре размерностью n (1 ≤ n ≤ 100), содержащую от нескольких до 100 слов. Длина каждого слова от нескольких до 100 символов. Слова могут располагаться по горизонтали, вертикали и диагонали. Горизонтальные и диагональные слова могут читаться справа налево; вертикальные и диагональные слова могут читаться снизу вверх (т.е. в обратном порядке). Разрабатываемая программа должна найти каждое слово из списка слов в матрице букв.

Ввод
В первой строке указывается длина сторон матрицы – n (1 ≤ n ≤ 100). Следующие n-строк представляют собой саму матрицу букв, каждая линия которой содержит n-букв латинского алфавита в верхнем регистре. Затем идет список слов для проверки (каждое слово с новой строки). Всего слов может быть от нескольких до 100. Последняя строка содержит одиночный символ 0 (ноль).

Вывод
Для каждого найденного слова ваша программа должна вывести в одну строку координаты его первого и последнего символов в матрице букв, разделенные пробелом.
Координаты – это пара целых чисел, разделенных запятой (начинающиеся с 1), где первое число указывает номер строки, а второе число указывает номер столбца.
Если слово не найдено, то для него необходимо вывести текст Not found без указания каких-либо координат. Каждое слово может быть найдено не более 1 раза в матрице букв.


Ввод 1 Ввод 2
6
DAAAAA
AEAALA
HELLOA
AAAERA
AAAATA
AAAAAE
DELETE
HELLO
TROL
APA
0
	
7
PRINTFG
AEGROFR
ABCDNOG
AACOSFG
AZGTEFG
AACDEFG
VVCDEFG
VAZA
ROST
VAGON
PRINT
FORGE
0
	
Вывод 1 Вывод 2
1,1 6,6
3,1 3,5
5,5 2,5
Not found
	
7,2 4,2
2,7 5,4
7,1 3,5
1,1 1,5
2,7 2,2
	

Для отправки решений необходимо выполнить вход.

www.contester.ru