--->
21 задач
<---
Источники
В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель.
Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна 0, у любого другого элемента высота на 1 больше, чем у его родителя.
Вам дано генеалогическое древо, определите высоту всех его элементов.
Программа получает на вход число элементов в генеалогическом древе \(N\). Далее
следует \(N-1\) строка, задающие родителя для каждого элемента древа, кроме родоначальника.
Каждая строка имеет вид имя_потомка имя_родителя.
Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.
Эта задача имеет решение сложности \(O(n)\), но вам достаточно написать решение сложности \(O(n^2)\) (не считая сложности обращения к элементам словаря).
Пример ниже соответствует приведенному древу рода Романовых.
9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I
Alexander_I 4 Alexei 1 Anna 1 Elizabeth 1 Nicholaus_I 4 Paul_I 3 Peter_I 0 Peter_II 2 Peter_III 2
В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель.
Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна 0, у любого другого элемента высота на 1 больше, чем у его родителя.
Даны два элемента в дереве. Определите, является ли один из них потомком другого.
Программа получает на вход число элементов в генеалогическом древе \(N\). Далее
следует \(N-1\) строка, задающие родителя для каждого элемента древа, кроме родоначальника.
Каждая строка имеет вид имя_потомка имя_родителя.
Для каждого такого запроса выведите одно из трех чисел: 1, если первый элемент является предком второго, 2, если второй является предком первого или 0, если ни один из них не является предком другого.
9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I Anna Nicholaus_I Peter_II Peter_I Alexei Paul_I
1 2 0
В генеалогическом древе определите для двух элементов их наименьшего общего предка. Наименьшим общим предком элементов A и B является такой элемент C, что С является предком A, C является предком B, при этом глубина C является наибольшей из возможных. При этом элемент считается своим собственным предком.
Формат входных данных аналогичен предыдущей задаче.
Для каждого запроса выведите наименьшего общего предка данных элементов.
По-английски такая задача называется lowest common ancestor (LCA).
9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I Alexander_I Nicholaus_I Peter_II Paul_I Alexander_I Anna
Paul_I Peter_I Anna
Для каждого элемента дерева определите число всех его потомков (не считая его самого).
Формат входных данных совпадает с задачей W.
Формат выходных данных совпадает с задачей W. Выведите список всех элементов в лексикографическом порядке, для каждого элемента выводите количество всех его потомков.
Решение должно иметь сложность \(O(N)\), не считая сложности обращения к элементам словаря и сортировки результата.
9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I
Alexander_I 0 Alexei 1 Anna 4 Elizabeth 0 Nicholaus_I 0 Paul_I 2 Peter_I 8 Peter_II 0 Peter_III 3
Недавно произошла утечка информации из мега-популярной социальной сети. Среди конфиденциальной информации, попавшей в сеть, оказались и пароли всех пользователей.
Михаил, школьник, увлекающийся компьютерной безопасностью, нашёл произошедший инцидент очень интересным. Экспериментируя с социальной сетью, он нашёл ещё одну брешь в её системе безопасности! Войти в аккаунт можно, если ввести строку, содержащую настоящий пароль от аккаунта как подстроку. Например, если пользователь, чей пароль « abc » введёт « abc », « abcd » или « imaabcnema », у него успешно получиться авторизоваться в системе, но у него не получится если он введёт « axbc ».
Миша хочет узнать, сколько существует упорядоченных пар пользователей таких, что если первый пользователь введёт пароль, то он сможет войти в аккаунт второго пользователя.
В первой строчке вводится одно целое число N — число пользователей ( 1 ≤ N ≤ 20 000 ). В следующих N строках вводятся пароли пользователей, по одному в строке. Пароль содержит от 1 до 10 маленьких букв латинского алфавита.
Выведите единственное число — количество пар, которое интересует Мишу.
Решение, правильно работающее при 1 ≤ N ≤ 2 000 , будет оцениваться в 40 баллов.
Во втором примере первый пользователь может войти в аккаунт второго и третьего пользователя, а второй пользователь — в аккаунт первого и третьего пользователя.
3 aaa aa abb
1
3 x x xy
4
5 mir mirta ta ir t
6