Description

The ternary operator is an operator in C. Its syntax is as follows:

It is often used to replace a simple if-else statement such as:

You can also combine several ternary operators together such as:

 

Now you are given a ternary expression, in which all the values are either true or false. Next you must evaluate the ternary expression with different combinations of values.

 

More specifically, a valid ternary expression is either:

or 

 

And the evaluation order of a ternary expression can be explained as follows:

• If the valid ternary expression is a single value, then just return the value.
• Otherwise:
  • if the value before ? is true then replace this ternary expression as the value of the ternary expression between ? and :
  • if the value before ? is false then replace this ternary expression as the value of the ternary expression after :

Hint: You can apply the idea of a syntax tree to solve this problem.

Input

The first line of the input is a valid ternary expression that contains the ternary operators and value indices.

• It is guaranteed that the value indices are pairwise distinct and range from 1 to the number of values in this ternary expression.
• For example, in the sample input below, the number of values is 5, and the value indices from left to right is 5, 3, 2, 4, 1, respectively.

The next line contains a single integer T, (T <= 5000), representing the number of combinations you have to evaluate.
For the next T lines, each line contains a binary string whose length is equal to the number of values in the ternary expression, giving the setting of each value.

• Note that the i-th character in this binary string (counted from left) is for the value index i. (1 represents true and 0 represents false)
• For string "01101", value indices 1-5 are set as 0,1,1,0,1, respectively.

There are 5 testcases in this problem.
For the first 3 testcases: 1 <= number of values <= 5
For the rest of the testcases: 1 <= number of values <= 3001

Output

For each combination, output the value of the ternary expression. (1 represents true and 0 represents false)
Remember to add a newline character at the end of every line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Today is your birthday, your father wants to prepare a gift for you. He ranks his brains and finally decide what to give. Since you are a college student major in computer science, he gives you a rooted binary tree for your birthday! But at the time you are unpacking the gift, you accidentally damage the binary tree! What a pity! You have tried very hard to restore the information of the binary tree but end up failure. For each node, you know which two nodes are its children, but you don't know which one is left child and which one is right child.

Fortunately, There's an inorder traversal sequence of the binary tree on the package, and you want to know whether the broken information of the binary tree is possible to form the inorder traversal sequence on the package.

Note:

The following figure is the way to form the tree that meets the input of sample testcase 1 and its inorder traversal is identical to the input inorder traversal.

 

Input

The input contains T testcases.

The first line of each testcase contains a single integer N representing the number of node in the binary tree. The index of nodes in the binary tree is 1-based. 

For the following N lines, each line contains two integers. For i-th line, the two integers represent the children of i-th node. 0 represents that the node doesn't exist.

Next line of the input contains N integers representing the inorder traversal sequence.

Constraint of testcases:

Testcase 1: N <= 5, T <= 4.
Testcase 2: T = 20, N <= 15, and node 1 is guarantee to be the root of the binary tree.
Testcase 3: T = 20, N <= 2000, and node 1 is guarantee to be the root of the binary tree.
Testcase 4: N * T <= 4 * 10⁶, N <= 2 * 10⁵, and node 1 is guarantee to be the root of the binary tree.
Testcase 5: T = 20, N <= 15.
Testcase 6: T = 20, N <= 2000.
Testcaes 7: T = 20000, N <= 10.
Testcase 8 ~ 10: N * T <= 4 * 10⁶, N <= 2 * 10⁵.

Output

For each testcase, if there exists a way to distribute nodes to left child or right child that its inorder traversal is identical to the input inorder traversal, then output "YES" otherwise "NO".

Remember to add a newline character at the end of every line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 

At the beginning of the semester at National Pokemon University (NPU), every student is running around for the course extra selection (加簽). In the add-or-drop selection session (加退選時期), to enroll in a course, students must submit "eForms" to the teacher. Due to the limited classroom size, after the formal course selection session, the teacher would decide who is eligible to take the course from the eForm list.

Team Rocket! Prepare for trouble! And make it double!  Unfortunately, Team Rocket had hacked into the school system, and messed up the order of the eForms! The serial numbers of the eForm list are now disorderly. They are just evil! 

Help these poor pokemon restore the eForms' order - sorting them by the serial numbers!

---

This is a partial judge problem. You would only need to implement the function "eFormSort" to pass the problem. 

Each eForm contains a serial number, a student ID, and a student name. The eForm list is given as a linked list (one node for each eForm). Your task is to make the serial numbers of that linked list in ascending order by changing the order of the eForms. The given program would output the status of each eForm, which can be either "Approved" or "Pending", after you sorted the eForm list.

 

        

 

Hint. 

1. Please notice that the memory is quite limited in this problem, and you need to sort the linked list directly by updating the "next" pointers of the nodes, instead of allocating too much extra space. The given program will check if you actually perform the required node sorting.
2. There are many ways to sort the linked list, and you may refer to the following two simple approaches:

• Approach 1: Use the Bubble Sort Algorithm. In this way, we just need to implement the operation of swapping two nodes. You can refer to the following gif and pseudocode to know more about this approach.

      

         

 

• Approach 2: While traversing the linked list, if you expect a node to occur but it does not, just keep traversing backward to find the node and move it forward. You can refer to the following gif to know more about this approach.

    

Input

• The first line contains an integer N (1 ≤ N ≤ 5000) - the number of submitted eForms.
• Each of the next N lines represents an eForm:
  • Format: <serial number> <student ID> <student name> <eForm status>
  • All of the serial numbers in the eForm list are distinct integer numbers between 1 and N
  • 1 ≤ student ID ≤ 10⁹
  • 1 ≤ length of student name ≤ 1000, and the name only consists of lower-case and upper-case alphabets A-Z / a-z
  • eForm status is either "Approved" or "Pending"
• For your convenience, in the given eForm list, the serial number of the first eForm must be 1.
• For the 30% of the test cases, the serial numbers of the given eForm list would be of the form "1, N, N-1, N-2, ..., 3, 2". That is, to solve this, you can just reverse the interval of [2, N].

 

Output

If you implement the function and sort the linked list correctly, the given program would output N lines - each of the lines represents an eForm in the input's format.

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

13826.c

Partial Judge Header

13826.h

Tags

Discuss

Description

What is a Perfect Binary Tree?

A perfect binary tree is a binary tree data structure with the following characteristics:

• Every level of the tree is completely filled with nodes. In other words, each level has the maximum number of nodes possible for that level.
• Each node in the tree has either two children or no children, and a node that has no children makes it a leaf node.
• The total number of nodes in a perfect binary tree of height h is 2^h+1 - 1. (Note that the height of the following example tree is 2 not 3.)

 

What is a Binary Search Tree?

A binary search tree (BST) is a binary tree data structure with the following properties:

• Each node in the tree has at most two child nodes (binary tree).
• For any node, its value is greater than or equal to the values stored in the left subtree.
• For any node, its value is smaller than the values stored in the right subtree.
• For any node, the left subtree and the right subtree are binary search trees respectively as well.

We know that the preorder traversal is based on the order "root -> left subtree -> right subtree". Therefore, for the preorder traversal sequence of a binary search tree, we can observe that the first number is the root of the tree, and in the following sequence, numbers smaller than or equal to the root belong to the left subtree (green part), while numbers larger than the root belong to the right subtree (blue part).

---

In this problem:

You are given the preorder sequence of a scrambled perfect binary search tree with unique node values, where the left and right subtrees of several nodes of the original tree have been swapped. See the following example of swapping node 8's and then node 12's left and right subtrees.

Can you help us reconstruct the original binary search tree and output its postorder sequence?

 

Input

• The first line contains an integer N  (1 ≤ N ≤ 10⁵) - the length of the preorder sequence for the scrambled perfect binary search tree.
• The second line contains N integers x₁, x₂, ..., x_N (1 ≤ x_i ≤ 10⁹) - representing the preorder sequence.

 

Output

Output one line that contains N integers - representing the postorder sequence of the original perfect binary search tree. Remember to print '\n' at the end.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In the programming academy, students enjoy learning from each other, where each person can become the “seafu” of others. Over time, this has led to a unique hierarchical system similar to a tree structure.

Within the academy, every student has exactly one "direct seafu,” except for the "Master FrankLee”, who sits atop the academy's hierarchy. He is the only one without a "direct seafu”, and he is the “seafu” of every students.

There are N students in the academy, each person has a uniuqe id number from 1 ~ N. There is a unique custom in the academy, seafu's id must be smaller than disciples' id. So "FrankLee" is always id number 1.

Now give you every student's direct seafu's id (except “FrankLee”), please answer the following questions.

Note: a student can be more than 1 students' "direct seafu", but can only have 1 "direct seafu".

 

Disciples Query:

Given an id number X. Output the number of disciples of student X.

A person is disciple of student X if student X is this person’s seafu. So Master FrankLee has N-1 disciples.

 

Seafu Test:

Given 2 id numbers A, B. (A≠B)

Check if student A is B’s seafu or student B is A’s seafu or neither.

if student A is B’s seafu, output "1".

if student B is A’s seafu, output "0".

if neither output "-1"

 

Note: A person x is person y’s seafu if person x is y’s direct seafu or y’s direct seafu’s direct seafu or y’s direct seafu’s direct seafu’s direct seafu, and so on…

Input

• The first line contains an integer N (1 ≤ N ≤ 1000), representing the number of people (excluding FrankLee) in the academy.
• The second line contains N - 1 space-separated integers, representing p_2, p₃, ..., p_N, which p_i means the direct seafu id of student i.
• Student id number 1 is always master FrankLee. And it is guarantee that p_i < i.
• The following line contains an integer Q (1 ≤ Q ≤ 1000), representing the number of queries.
• Each of the next Q lines contains a query "1 X"(disiples query) or "2 A B"(seafu test).

Constraints

• Testcase 1: There is only seafu test query, and the answer is to the query is either 0 or 1.
• Testcase 2: There is only seafu test query.
• Testcase 3~4: There is only disiples query. 
• Testcase 5~6: Satisfy no additional constraints.

 

Output

• Output Q lines, each lines contain the answer tod  each query.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Gilbert is a gardener who loves planting flowers and trees. He also enjoys using tree data structures to solve programming problems, such as segment tree and treap. However, he recently felt that programming was too exhausting and decided to focus on gardening.
By chance, he planted an "expression tree" that only operates with operations: +, -, and *. He was excited to discover that each expression tree has its own beauty value, which depends on the outcome of the expression tree's calculation divided by 998244353. For example, the beauty of the expression tree "0 * (3 - 4)" is 0 % 998244353 = 0.

As a gardener, Gilbert wants to enhance the beauty of this expression tree. He plans to do this by selecting two nodes that do not have an ancestor-descendant relationship and swapping their subtrees. Since Gilbert is lazy, he hopes to perform this swap no more than once. However, he is unsure how to swap to maximize the overall beauty of the tree. He has asked for your help and will provide you with the preorder expression of this expression tree. Please tell him the highest possible beauty of the expression tree after performing at most one swap.

Example:

Choosing to swap the subtrees of these two nodes can maximize the beauty of the tree.

Input

The first line of the input is an integer N(3 <= N <= 500), being the length of the prefix expression of the expression tree.

The next line is the expression tree (in prefix expression). The expression contains only +, -, * and digits. All the numbers in the expression are integers between 0 and 9.

Output

Output the maximum beautify of the expression tree after performing at most one swap.

Note that you should have a '\n' in the end.

Hint:

If you have no idea how to implement, please take it as your reference.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define mod 998244353 // Define a modulo for the beauty calculation.

// Define a node structure for the expression tree.
typedef struct _Node {
    int val; // {0 ~ 9: number, -1: +, -2: -, -3: *}
    int ans;
    struct _Node *lc, *rc; // Left child, right child.
} Node;

char s[505] = {}; // Input string representing the preorder expression of the tree.
Node *arr[505] = {}; // Array to store pointers to nodes for easy access.

// Function to build the expression tree from the input string.
Node *build() {
}

// Function to evaluate the expression tree and calculate its beauty.
int eval(Node *r) {
}

// Depth-First Search function to check if target node is in the subtree rooted at 'now'.
bool dfs(Node *now, Node *target) {
}

// Function to check if two nodes have an ancestor-descendant relationship.
bool check(int a, int b) {
}

// Function to swap the subtrees rooted at nodes a and b.
void swap(int a, int b) {
}

// Main function.
int main() {
}

Sample Input  Download

Sample Output  Download

Tags

Discuss