| Problem description | | Progress |
|
Темы:
hash
Trees
Petya and Vasya enthusiastically play spies. Today they are planning where they will be
located their secret bunkers and headquarters.
So far, Petya and Vasya have decided that they will need exactly n bunkers, which will be numbered from 1 to n for secrecy.
Some of them will be connected by two-way tunnels, and for reliability and secrecy, the tunnels will be accessible from any bunker to any one way.
Petya and Vasya even decided which of the bunkers will be connected by tunnels, but they cannot choose which one will be the headquarters.
The boys want to choose it and divide the remaining bunkers among themselves so that they get an equal number of bunkers. Exactly two tunnels lead to the headquarters: one from the bunker belonging to Vasya, the other from the bunker belonging to Petya.
Tired Petya went to his house, and in the morning Vasya showed him a plan on which the bunkers were marked with dots and the tunnels with segments.
In addition, Vasya chose the headquarters in such a way that the plan he drew was symmetrical with respect to a straight line passing through the point that corresponded to the headquarters.
Although Petya almost immediately showed Vasya that he had made a mistake and did not draw half of the bunkers, he wondered if it was possible to choose a headquarters and draw such a symmetrical plan.
Input:
The first line of the input file contains a single integer n (1 <= n <= 105) - the number of bins.
The next n - 1 lines contain two integers ui and vi (1 <= ui, vi <= n, ui ≠ vi) - numbers of bunkers connected by the i-th tunnel.
It is guaranteed that there is only one path between any two bunkers.
Output:
In the output file print "YES" if it is possible to choose a headquarters and draw such a plan, or "NO" if that's not possible.
Examples:
| Input |
Output |
2
1 2
| NO |
3
1 2
2 3
| YES |
| |
![]()
|
|
Темы:
hash
Bor
Trees
Trees
Once Konstantin, having participated in the next, already the 13th international Olympiad, was returning home by train. He, as always, sat and thought about the meaning of life, simultaneously solving programming problems. After some time, Konstantin dozed off, but the trouble is, in order to wake up, he must solve the problem that has popped up in his head, which haunts him!
This time, Konstantin dreamed of a tree that initially consisted of only one vertex with number 1. In the problem he set, new vertices were gradually added to the tree. In the i-th second, a vertex with the number i+1 was added to the tree, which was suspended as a son from the vertex pi, and on the edge between the vertices i+1 and pi the letter ci was written.
Each path from the root of the tree to the vertex v corresponds to a certain string obtained by writing out the symbols written on the edges of the current path in the order from the root to the vertex v. Konstantin faced a difficult task at first glance - after each addition of a new vertex, count the number of unique strings starting at the root of the tree (vertex number 1) and ending at some other vertex.
In his dream, Konstantin is not a genius at all, so he himself cannot solve this problem. Help Konstantin solve the problem and wake up.
Input:
The first line contains the number n - the number of requests to add a new node to the tree (1 <= n <= 300000).
The next n lines describe requests for adding vertices. The i-th query is described by the parameters pi (1 <= pi <= i) and ci, which mean that the added the vertex with number i+1 is suspended from the vertex with number pi as a child, and the symbol ci is written on the resulting edge - a lowercase letter of the Latin alphabet.
Output:
Print n lines. On the i-th line print the answer to Konstantin's problem after adding the i+1-th vertex.
Examples:
| Input |
Output |
2
1 b
2p |
1
2 |
3
1 o
1 o
2 j |
1
1
2 |
| |
![]()
|
|
Темы:
Trees
Implement a binary search tree for integers. The program receives a sequence of integers as input and builds a tree from them. Elements are added to the trees in accordance with the result of the search for their place. If the element already exists in the tree, you do not need to add it. The tree is not balanced.
Input
The program receives a sequence of natural numbers as input. The sequence ends with the number 0, which means the end of the input, and you do not need to add it to the tree.
Output
Print a single number – the height of the resulting tree.
The example matches the following tree:
Examples
| # |
Input |
Output |
| 1 |
7 3 2 1 9 5 4 6 8 0
|
4
|
| |
![]()
|
|
Темы:
Trees
Count the number of elements in the resulting tree and output this number.
Input
Enter a sequence of integers ending in zero. Zero itself is not included in the sequence.
Output
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
7 3 2 1 9 5 4 6 8 0
|
9
|
| |
![]()
|
|
Темы:
Trees
For the resulting tree, print a list of all leaves (vertices that have no children) in ascending order.
Input
Enter a sequence of integers ending in zero. Zero itself is not included in the sequence.
Output
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
7 3 2 1 9 5 4 6 8 0
|
1
4
6
8
|
| |
![]()
|
|
Темы:
Trees
For the resulting tree, print a list of all vertices that have two children, in ascending order.
Input
Enter a sequence of integers ending in zero. Zero itself is not included in the sequence. Build a tree according to this sequence.
Output
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
7 3 2 1 9 5 4 6 8 0
|
3
5
7
|
| |
![]()
|
Темы:
Trees
A tree is said to be balanced if, for any of its vertices, the heights of the left and right subtrees for that vertex differ by no more than 1.
Input
A sequence of integers ending in zero is entered. Zero itself is not included in the sequence. Build a tree corresponding to the given sequence.
Output
Determine if the tree is balanced, output the word YES or NO.
Examples
| # |
Input |
Output |
| 1 |
7 3 2 1 9 5 4 6 8 0
|
YES
|
| |
![]()
|
|
Темы:
Trees
Display the second largest element in the constructed tree. It is guaranteed that there is one.
Input
You are given a sequence of integers ending in zero. Zero itself is not included in the sequence.
Output
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
7 3 2 1 9 5 4 6 8 0
|
8
|
| |
![]()
|
|
Темы:
Trees
Display all elements of the resulting tree in ascending order.
Input
Enter a sequence of integers ending in zero. Zero itself is not included in the sequence. According to this sequence, you need to build a tree.
Output
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
7 3 2 1 9 5 4 6 8 0
|
1
2
3
4
5
6
7
8
9
|
| |
![]()
|
|
Темы:
Trees
For the resulting tree, print a list of all vertices that have only one child, in ascending order.
Input
Enter a sequence of integers ending in zero. Build a tree based on it.
Output
Display the list of required vertices.
Examples
| # |
Input |
Output |
| 1 |
7 3 2 1 9 5 4 6 8 0
|
2
9
|
| |
![]()
|
|
Темы:
Trees
Write a program that will implement actions in the "insert" binary search tree; and "find" (by value). The program must process requests of three types:
ADD n — if the specified number is not yet in the tree, insert it and output the word "DONE" if — leave the tree as it was and display the word "ALREADY".
SEARCH — should output the word «YES» (if the value is found in the tree) or the word "NO" (if not found). The tree does not change.
PRINTTREE — output the entire tree, always using the algorithm specified in the output format.
Input
Each line of the input contains one of the queries ADD n or SEARCH n or PRINTTREE. It is guaranteed that PRINTTREE queries will only be called when the tree is not empty. The total number of requests does not exceed 1000, of which no more 20 PRINTTREE. requests
Output
For each request, display the answer to it. For ADD and SEARCH — the corresponding word on a separate line. For the PRINTTREE request, a tree must be output, necessarily according to the following algorithm:
template void print_tree(Node *p, int level)
{
if(p==NULL)
return;
print_tree(p->left, level+1);
for(int i=0; i < level; i++)
cout << ".";
cout << p->data << endl;
print_tree(p->right, level+1);
}
(Initial call to this function — print_tree(root,0).)
Examples
| # |
Input |
Output |
| 1 |
ADD2
ADD 3
ADD2
SEARCH 2
ADD 5
PRINTTREE
SEARCH 7
|
DONE
DONE
ALREADY
YES
DONE
2
.3
..5
NO
|
| |
![]()
|
|
Темы:
Trees
Write a program that will implement the actions in the binary search tree "insert", "delete"; and "find" (by value). The program must process four types of requests:
ADD n — if the specified number is not yet in the tree, insert it and output the word "DONE" if — leave the tree as it was and display the word "ALREADY".
DELETE n — if the specified number is in the tree, delete it and display the word "DONE", if there is no — leave the tree as it was and display the word "CANNOT". When deleting an element that has two children, be sure to exchange the value with the maximum element of the left subtree.
SEARCH— should output the word «YES» (if the value is found in the tree) or the word "NO" (if not found). The tree does not change.
PRINTTREE — output the entire tree, always using the algorithm specified in the output format.
Input
Each input line contains one of the queries ADD n or DELETE n or SEARCH n or PRINTTREE . It is guaranteed that PRINTTREE queries will only be called when the tree is not empty. The total number of requests does not exceed 1000, of which no more 20 PRINTTREE. requests
Output
For each request, display the response to it. For ADD, DELETE and SEARCH — the corresponding word on a separate line. For the PRINTTREE request, a tree must be displayed, necessarily according to the following algorithm:
template void print_tree(Node *p, int level)
{
if(p==NULL)
return;
print_tree(p->left, level+1);
for(int i=0; i < level; i++)
cout << ".";
cout << p->data << endl;
print_tree(p->right, level+1);
}
(Initial call to this function — print_tree(root,0).)
Examples
| # |
Input |
Output |
| 1 |
ADD2
ADD 7
ADD 5
PRINTTREE
ADD 5
DELETE 3
ADD 0
PRINTTREE
DELETE 7
PRINTTREE
|
DONE
DONE
DONE
2
..5
.7
ALREADY
CANNOT
DONE
.0
2
..5
.7
DONE
.0
2
.5
|
| |
![]()
|
ID 44989.
coup
Темы:
Trees
Given an array. We need to learn how to handle two types of requests.
* 1 L R - flip segment [L,R]
* 2 L R - find the minimum on the segment [L,R]
Input
The first line of the file contains two numbers n, m. (1<=n,m<=105) The second line contains n numbers ni (1<=ai<=109) - source array. The remaining m lines contain queries in the format described in the condition. The numbers L, R are restricted to (1<=L<=R<=n).
Output
For each request of type 2, print the answer to it in the input file on a separate line.
Examples
| # |
Input |
Output |
| 1 |
10 7
5 3 2 3 12 6 7 5 10 12
2 4 9
1 4 6
2 1 8
1 1 8
1 8 9
2 1 7
2 3 6
|
3
2
2
2
|
| |
![]()
|
|
Темы:
Trees
Giggle opens its new office in Sudislavl and you are invited for an interview. Your task — solve the problem.
You need to create a data structure that is an array of integers. The array is initially empty. You need to support two operations:
- request: "
? i j» — returns the minimum element between the i-th and j-th, inclusive;
- change: "
+ i x" — add element x after i-th element of the list. If i=0, then the element is added to the beginning of the array.
Of course, this structure should be good enough.
Input
The first line of the input file contains a single integer n — number of operations on the array (1<=n<=200000). The following n lines describe the operations themselves. All add operations are valid. All numbers stored in the array do not exceed 109.
Output
For each operation print its result on a separate line.
Comment to example tests
The following table shows the process of changing the array from the example.
| Operation |
Array after its execution |
| originally |
empty |
+ 0 5 |
5 |
+ 1 3 |
5, 3 |
+ 1 4 |
5, 4, 3 |
+ 0 2 |
2, 5, 4, 3 |
+ 4 1 |
2, 5, 4, 3, 1 |
Examples
| # |
Input |
Output |
| 1 |
8
+ 0 5
+ 1 3
+ 1 4
? 12
+ 0 2
? 24
+ 4 1
? 3 5
|
4
3
1
|
| |
![]()
|
|
Темы:
Trees
Write a program that calculates the value of an arithmetic expression written as a character string. The expression uses only integers and signs of arithmetic operations (+-*/). The result of the division operation – integer.
Input
The input of the program is a character string containing the correct notation of an arithmetic expression.
Output
The program should output the value of the expression passed to it as an integer.
Examples
| # |
Input |
Output |
| 1 |
125-6-73/5*8
|
7
|
| |
![]()
|
|
Темы:
Trees
Write a program that calculates the value of an arithmetic expression written as a character string. The expression uses only integers, signs of arithmetic operations (+-*/) and brackets of arbitrary nesting. The result of the division operation – integer.
Input
The input of the program is a character string containing the correct notation of an arithmetic expression, possibly with brackets.
Output
The program should output the value of the expression passed to it as an integer.
Examples
| # |
Input |
Output |
| 1 |
(5+20)*(98-34)/(5*8-23)
|
94
|
| |
![]()
|
|
Темы:
Trees
Write a program that calculates the value of an arithmetic expression written as a character string. The expression uses integers, arithmetic operators, parentheses, and function calls ( sin , cos , abs , sqrt ). The result of the division operation – real number.
Input
The input of the program is a character string containing the correct notation of an arithmetic expression.
Output
The program must output the value of the expression passed to it as a real number. When displaying the result, you need to leave 3 digits in the fractional part of the number.
Examples
| # |
Input |
Output |
| 1 |
12+cos(sqrt(12+sin(2)))
|
11.100
|
| |
![]()
|
|
Темы:
Trees
Write a program that calculates the value of an arithmetic expression written as a character string. The expression uses integers, arithmetic operators, parentheses, function calls ( sin , cos , abs , sqrt ) and variable names (single-letter only). The result of the division operation – real number.
Input
The first line contains the correct entry for the arithmetic expression. The next few lines contain the values of all the variables used in the expression. Each of these lines has the format:
<variable name>=<value>
Each variable name consists of one lowercase Latin letter.
Output
The program must output the value of the expression passed to it as a real number. When displaying the result, you need to leave 3 digits in the fractional part of the number.
Examples
| # |
Input |
Output |
| 1 |
cos(z+abs(sqrt(r*sin(x+4))))
r=5
z=10
x=3
|
0.729
|
| |
![]()
|