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

Partial Judge Header

Tags

Discuss

Description

Today is your birthday, your father wants to prepare a gift for you. He ranks his brains and finally decides 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, your father told you this is a binary search tree (BST) originally, and you want to know whether the broken information of the binary tree is possible to reconstruct the original binary search tree (BST) and get its inorder traversal sequence.

Note: the value of each node is same as its index in this problem. 

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.

Hint: observe what is special about BST's inorder traversal.
 

Input

The input contains T testcases.

The first line of each testcase contains a single integer N, representing the number of nodes in the binary tree.

The indices of nodes in the binary tree are 1-based, ranging from 1 to N, and the value of each node is same as its index in this problem.

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.

Constraint of testcases:

for all testcases: 1 ≤ N ≤ 100000, 1 ≤ T ≤ 10

Testcase 1: the answer is always "YES", and when input the children of each node, the first one is always the left child, the second one is always the right child (You just need to print the inorder traversal of the tree).

Testcases 2, 3: the answer is not always "YES". but when input the children of each node, the first one is always the left child, the second one is always the right child (You just need to print the inorder traversal of the tree).

Testcases 4, 5: No additional constraint.

Output

For each testcase, if there exists a way to distribute nodes to left child or right child that it becomes a BST, then output "YES" otherwise "NO".

If the answer is yes, please output the inorder traversal of the tree in the next line. Otherwise, don't ouput anything in the next line.

Remember to add a newline character at the end of every line, and there is no spaces at the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

After extensive practice, Gilbert has finally become a Master Gardener.

Input

The first line contains two positive integers, H and T, representing the height of the expression tree and the type of query, respectively.

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.

It is guaranteed that the length of the expression is 2^H+1 - 1.

Constraints

• For testcases 1 ~ 2: 1 ≤ H ≤ 6, T = 1
• For testcases 3 ~ 4: 1 ≤ H ≤ 20, T = 2, '-' operator ≤ 20
• For testcases 5 ~ 7: 1 ≤ H ≤ 20, T = 2
• For testcases 8 ~ 10: 1 ≤ H ≤ 10, T = 1

Output

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

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

Hints

• For testcases 1 ~ 2: The approach for the corresponding practice problem is applicable.
• For testcases 3 ~ 4: The approach for testcases 1 ~ 2 is also applicable, but please find each pair of siblings "directly" and see when is necessary to recalculate the while tree for a possible better beauty value.
• For testcases 5 ~ 10: A more efficient approach is required.

You may consider to use the following reference code.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define mod 998244353 // Define a modulo for the beauty calculation.
typedef struct _Node {
    int val; // {0 ~ 9: number, -1: +, -2: -, -3: *}
    int ans; // evaluate result
    struct _Node *lc, *rc, *p; //Left child, Right child, Parent
} Node;
char expr[2200000] = {}; // Input string representing the preorder expression of the tree.
Node *tree[2200000] = {}; // Array to store pointers to nodes for easy access.
int h, t, n;
int idx = 0;

// Function to build the expression tree from the input string.
Node *build() {
    if(idx >= n) return NULL;
    Node *r = (Node *)malloc(sizeof(Node));
    tree[idx] = r; 
    r->ans = -1, r->lc = r->rc = r->p = NULL;
    if(expr[idx] >= '0' && expr[idx] <= '9'){
        r->val = expr[idx] - '0';
        idx++;
    }
    else {
        if(expr[idx] == '+') r->val = -1;
        else if(expr[idx] == '-') r->val = -2;
        else r->val = -3;
        idx++;
        r->lc = build();
        r->rc = build();
        r->lc->p = r;
        r->rc->p = r;
    }
    return r;
}

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

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

// 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(Node *a, Node *b) {
}

int main() {
    scanf("%d %d", &h, &t);
    scanf("%s", expr);
    n = (1 << (h + 1)) - 1; // n = 2 ^ (h + 1) - 1
    build();
    int ans = eval(tree[0]);
    if(t == 1) {
    }
    else {
    }
    printf("%d\n", ans);
}

Sample Input  Download

Sample Output  Download

Tags

Discuss