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

Турниры > CEN303_2016Questions > задача:


HW052. 51020 - Number of nodes removed

CEN303_2016Questions

Старт: 28.окт.2016 в 17:00:00
Финиш: 01.ноя.2016 в 05:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (5)

Задачи турнира

• HW012. 51009 - Sum of the nth row
• HW021. 51011 - Decoding the Path
• HW022. 51012 - Palindrome-k
• HW023. 50741 - DNA Distance
• HW031. 51015 - Student Scholarships
• HW032. 51014 - Nine Men's Morris g...
• HW033. 50925 - Optimizing Elevator...
• HW051. 51019 - Finding the hidden...
• HW052. 51020 - Number of nod...
• HW061. 50448 - Paint Buckets
• HW062. 51021 - Number of Nodes
• HW071. 51042 - The most frequent ...
• HW072. 51043 - Genome Sequencing
• HW081. 51044 - Number of Trees
• HW082. 50699 - Fighting Vampires
• HW083. 50671 - Phalanx
• HW091. 51061 - The Longest Path

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

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

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Question by Ibrahim Mesecan.

Number of Nodes removed

You have a binary tree and you have to remove some nodes from the tree. You want to see the number of nodes removed:

  • number of leaves removed,
  • number of nodes which had one child
  • number of nodes which had two children

Question: Write a program that reads the information for a BST and then, reads the nodes to be removed from the tree. Then the program shows the number of nodes removed according to the number of children they have.

Input specification: You will be given two integers in the beginning, the number of nodes (n) to be added to the BST and the number of nodes to be removed from the tree (m). The following line will have n integers and the last line will have m integers where 0 ≤ m ≤ n ≤ 10,000 . Note: Assume that the BST is initially empty.

Output specification: Show three integers.

Sample Input
10 5
15 8 10 8 18 2 2 9 11 9
8 3 8 11 9
Sample Output
1 0 2

Explanation: There are 10 items given. However, Figure A shows the tree after inserting the given nodes.

There are five nodes to be removed from the tree. The first number is 8. And, it has two children. Figure B shows the configuration after the removal of 8. There is no 3 or 8 in the tree, so they do not change the tree. Then, 11 is removed from the tree and it has no child. And finally, 9 is given. After the removal of 8, 9 has moved up and now it has two children either. Thus, there is 1 leaf removed. And, two nodes (8 and 9) with two children.



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

www.contester.ru