Description

HARD DO OTHER PROBLEM FIRST

This program implements a simple integer calculator.

The input is a valid arithmetic expression on a single line.

The expression contains integers (possibly negative), operators + - * /.

All tokens are separated by spaces. Example:

2 + 3 * 4 * -9

Input

A single line consisting of integers and operators + - * /, separated by spaces.

The expression is always guaranteed to be valid.

Output

Output exactly one integer: the result of the expression.

The final computed answer is guaranteed to be an integer value.

Ensure that the output formatting matches exactly.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given a sequence of integers. These integers are inserted into a Binary Search Tree (BST) one by one, in the given order.

After the BST is constructed, you will receive several queries. Each query contains an integer k, and you must determine the value of the node that is the k-th smallest element in the entire BST.

The BST insertion rule follows the standard definition:

• If a value is less than or equal to the node, it is inserted into the left subtree.

• Otherwise, it is inserted into the right subtree.

Each query asks for the element ranked k-th when all nodes are sorted in ascending order.

 

A completed program of BST structure and insertion is provided. You only need to write the function:

BS_Tree *find_kth_min_data (BS_Tree *root, int k)

so that it correctly returns the pointer to the k-th smallest node.

Given C code (complete the marked part):

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define debug 0

typedef struct bs_tree {
        int data;
        int sub_node_count;
        struct bs_tree *left;
        struct bs_tree *right;
}BS_Tree;

BS_Tree *find_kth_min_data (BS_Tree *root, int k){
/*
    Written by yourself
*/
}

BS_Tree *insert_sort_BS_Tree(BS_Tree *root, int data){
        BS_Tree *current = root;
        if (root == NULL) {
                current = (BS_Tree *) malloc (sizeof(BS_Tree));
                assert(current != NULL);
                if (debug) printf("malloc (BS_Tree *) at %p\n", current);
                current->data = data;
                current->left = NULL;
                current->right = NULL;
                return current;
        }
        if (data <= current->data)
                current->left = insert_sort_BS_Tree(current->left, data);
        else
                current->right = insert_sort_BS_Tree(current->right, data);
        return current;
}

int insert_sub_node_count (BS_Tree *root){
        int left_count, right_count, total_count;
        if (root == NULL) return 0;
        if (root->left == NULL && root->right == NULL) {
                root->sub_node_count = 1;
                return 1;
        }
        left_count = insert_sub_node_count(root->left);
        right_count = insert_sub_node_count(root->right);
        root->sub_node_count = 1 + left_count + right_count;
        return root->sub_node_count;
}

void print_inorder (BS_Tree *root){
        if (root == NULL) return ;
        print_inorder(root->left);
        printf("%d %d\n", root->data, root->sub_node_count);
        print_inorder(root->right);
}

BS_Tree *delete_BS_Tree(BS_Tree *root){
        if (root == NULL) return NULL;
        delete_BS_Tree(root->left);
        delete_BS_Tree(root->right);
        if (debug) printf("free (BS_Tree *) at %p\n", root);
        free(root);
        return NULL;
}

int main (void){
        int data, k;
        BS_Tree *root = NULL;
        BS_Tree *ptr_kth_min;
        do {
                scanf("%d", &data);
                if (debug) printf("input data %d\n", data);
                root = insert_sort_BS_Tree(root, data);
        }while (getchar() != '\n');
        insert_sub_node_count(root);
        if (debug) print_inorder(root);
        do {
                scanf("%d", &k);
                if (debug) printf("input k = %d\n", k);
                ptr_kth_min = find_kth_min_data(root, k);
                printf("%d\n", ptr_kth_min->data);
        }while (getchar() != '\n');
        root = delete_BS_Tree(root);
        return 0;
}

 

The following figure shows the tree structure for Sample Input 1.
The input data can be formatted using the function insert_sub_node_count(root).

The number next to each node represents the total number of nodes in its subtree.

 

Input

First line: n integers, representing the values to be inserted into the BST.

Second line: m integers, each representing a query k.

Constraints:

• 0 < n ≤ 100000

• 0 < m ≤ n

• 1 ≤ k ≤ n

Output

Output m lines. Each line contains the data of the node that is the k-th smallest value in the BST corresponding to each query.

Ensure the output formatting exactly matches the required samples.

Sample Input  Download

Sample Output  Download

Tags

Discuss