Технокубок 2021 - Финал |
---|
Закончено |
В этом году в Конохе вновь проводится экзамен на звание Чунина, и в нем участвуют $$$n$$$ ниндзя с именами $$$s_1$$$, $$$s_2$$$, ..., $$$s_n$$$. Все имена участников различны. Один из этапов экзамена — сражения между участниками. В этом году руководство Конохи решило, что определять, кто с кем сражается, будут по-новому. Ниндзя $$$i$$$ сражается с ниндзя $$$j$$$, если выполнены три правила:
Строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Необходимо выяснить, сколько сражений будет проведено на экзамене в этом году.
Первая строка содержит натуральное число $$$n$$$ ($$$1 \leq n \leq 10^{6}$$$) — число участников экзамена.
Следующие $$$n$$$ строк содержат имена участников. Все имена непустые, различны и состоят из строчных латинских букв. Суммарная длина всех имен не превосходит $$$10^6$$$.
Необходимо вывести единственное число — количество сражений на экзамене в этом году.
5 hidan dan hanabi bi nabi
3
4 abacaba abaca acaba aca
4
В первом примере hidan сражается с dan, а hanabi сражается с nabi, который также сражается с bi. Ниндзя с именами hanabi и bi не сражаются, поскольку есть ниндзя с именем nabi, из-за которого для этой пары не выполняется третье условие.
Во втором примере сражения происходят между abacaba и acaba, abacaba и abaca, acaba и aca, abaca и aca.
Название |
---|