| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14846 | Event triggering logic inference |
|
| 14847 | Binary Search Tree Subtree Size Computation |
|
| 14849 | Simulated bookshelf management system(linked list) |
|
Description
Write a logical inference program.
We assume that in this logical inference system there are at most 26 events, and each event is represented by an uppercase letter.
We also assume that if one event is true, then several other events will also become true.
If an event triggers three events, we write it as:
This means that if A is true, then B, C, and D are also true.
That is, A triggers B, C, and D.
Given the logical triggering relationships among the events, we want to determine which events will be triggered when a certain event occurs.
Constraints:
-
0 < n ≤ 26
-
0 ≤ m ≤ 100
Input
The input consists of two parts.
Part 1: Trigger relationship
The first line contains an integer n, representing the number of logical trigger relations.
Each of the next n lines has the following format:
-
First, an event (the triggering event),
-
Followed by the events it triggers, separated by spaces.
For example, the following means that if A is true, then B, C, and D will become true;
Additionally, each event can trigger at most three events.
An event cannot trigger itself, and no cyclic triggers exist.
Each event appears at most once on the left-hand side.
Part 2: Queries
The next input section contains queries.
The first line is an integer m, representing the number of queries.
Each of the next m lines contains two events.
Ex. 2
A 3 B C D
C 2 Z F
2
A Z
Z A
Output
For each query, if the first event can trigger the second event (directly or indirectly), print "yes"; otherwise print "no".
Ex. yes
no
Sample Input Download
Sample Output Download
Discuss
Description
Write a program to compute the number of nodes in every subtree.
For example, in figure below, the subtree rooted at node 6 contains three nodes: 1, 6, and 9.
Constraints:
0 < n ≤ 100000
Input
The input consists of one line containing n integers that are to be inserted into a binary search tree (BST) in the given order.
Ex. 4 6 2 9 5
Output
The output should list, one node per line, each node’s value followed by the total number of nodes in the subtree rooted at that node.
The nodes must be printed in in-order traversal.
Ex. 2 1
4 5
5 1
6 3
9 1
Sample Input Download
Sample Output Download
Discuss
Description
Redo Problem 14804 using linked list representation.
This time, since the number of books n and the number of shelf positions m are no longer restricted, we can attempt larger inputs.
Constraints:
0 < n ≤ 1024,
0 < m ≤ 128
Input
The first line of input contains n, the number of books, and m, the number of shelf positions.
The books are numbered from 1 to n.
The second line contains a sequence of integers between 1 and n, representing the order in which we read the books.
The program must process all input until EOF.
Ex. 255 8
1 2 3 4 5 6 7 8 6 10 23 7 4
Output
The output consists of m integers, representing the books currently on the shelf from left to right.
If a shelf position does not contain a book, output 0 for that position.
Ex. 3 5 8 6 10 23 7 4