Темы --> Информатика --> Язык программирования --> Типы данных
    Символы(9 задач)
    Строки(121 задач)
    Целые числа(112 задач)
    Битовые операции(28 задач)
    Логический тип(3 задач)
    Структуры(18 задач)
    Вещественные числа(33 задач)
    Множества(16 задач)
    Словари(21 задач)
---> 356 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 53 54 55 56 57 58 59 >> Отображать по:
#3771
Родословная: подсчет уровней
  

В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель.

Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна 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
#3772
Родословная: предки и потомки
  
Темы: [Словари]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель.

Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна 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
#3773
Родословная: LCA
  
Темы: [Словари]

В генеалогическом древе определите для двух элементов их наименьшего общего предка. Наименьшим общим предком элементов 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
#3774
Родословная: число потомков
  
Темы: [Словари]

Для каждого элемента дерева определите число всех его потомков (не считая его самого).

Входные данные

Формат входных данных совпадает с задачей 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
#3864
Цапли
  
Темы: [Целые числа]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Петя и Маша пришли в зоопарк. Больше всего Пете понравились цапли. Он был поражен их способностью спать на одной ноге.

В вольере находятся несколько цапель. Некоторые из них стоят на двух ногах, некоторые — на одной. Когда цапля стоит на одной ноге, то другую ее ногу не видно. Петя пересчитал видимые ноги всех цапель, и у него получилось число a.

Через несколько минут к вольеру подошла Маша. За это время некоторые цапли могли поменять позу, поэтому Петя предложил ей заново пересчитать видимые ноги цапель. Когда Маша это сделала, у нее получилось число b.

Выйдя из зоопарка, Петя с Машей заинтересовались, сколько же всего цапель было в вольере. Вскоре ребята поняли, что однозначно определить это число можно не всегда. Теперь они хотят понять, какое минимальное и какое максимальное количество цапель могло быть в вольере.

Требуется написать программу, которая по заданным числам a и b выведет минимальное и максимальное количество цапель, которое могло быть в вольере.

Входные данные

Входной файл содержит два целых числа a и b, разделенных ровно одним пробелом (1 ≤ a ≤ 109, 1 ≤ b ≤ 109).

Выходные данные

Выведите в выходной файл два целых числа, разделенных пробелом — минимальное и максимальное число цапель, которое могло быть в вольере. Гарантируется, что хотя бы одно количество цапель соответствует условию задачи.

Примечание к примеру тестов

В приведенном примере возможны следующие варианты:

  1. В вольере две цапли. Когда Петя считал ноги, одна цапля стояла на двух ногах, а другая — на одной. Петя насчитал три ноги. Когда Маша считала ноги, обе цапли стояли на двух ногах, Маша насчитала четыре ноги.
  2. В вольере три цапли. Когда Петя считал ноги, все цапли стояли на одной ноге, Петя насчитал три ноги. Когда Маша считала ноги, одна цапля стояла на двух ногах, а еще две — на одной. Маша насчитала четыре ноги.
Примеры
Входные данные
3 4
Выходные данные
2 3
Страница: << 53 54 55 56 57 58 59 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест