Description

Create a class Polynomial. The internal representation of a Polynomial is an array of terms. Each term contains a coefficient and an exponent, e.g., the term 2x⁴ has the coefficient 2 and the exponent 4.

• Use a 51-element array, coefficients, of digits to store each coefficient.
• Use a integer variable, greatestPower, to store an exponent.

Provide public member functions that perform each of the following tasks:

1. Adding two Polynomial.
2. Subtracting two Polynomial.
3. Multiplying two Polynomial.
4. Printing coefficients of the Polynomial in descending order.

Note:

1.      This problem involves three files.

• function.h: Class definition of Polynomial.
• function.cpp: Member-function definitions of Polynomial.
• main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp, and asked to implement function.h and function.cpp.

function.h

#ifndef POLYNOMIAL_H #define POLYNOMIAL_H #include <iostream> class Polynomial { public: Polynomial(); Polynomial(const int , const int [51]); Polynomial add( const Polynomial) const; // add function Polynomial subtract( const Polynomial ) const; // subtract function Polynomial multiplication( const Polynomial ) const; // multiplication function void output() const; private: int coefficients[101]; // integer coefficients int greatestPower; // integer greatestPower }; // end class Polynomial #endif

main.cpp

#include <iostream> #include <stdio.h> #include <string> #include "function.h" using namespace std; int main() { int greatestPower1, greatestPower2; int coefficient1[51], coefficient2[51]; Polynomial ans; cin>>greatestPower1; for(int i = greatestPower1 ; i >= 0; i--) { cin>>coefficient1[i]; } cin>>greatestPower2; for(int i = greatestPower2 ; i >= 0 ; i--) { cin>>coefficient2[i]; } Polynomial a(greatestPower1, coefficient1), b(greatestPower2, coefficient2) ; ans = a.add( b ); ans.output(); cout << endl; ans = a.subtract( b ); ans.output(); cout << endl; ans = a.multiplication( b ); ans.output(); cout << endl; } // end main

2.     For OJ submission:

       Step 1. Submit only your function.cpp into the submission block.

       (***Note that you don’t need to submit your function.h.)

       Step 2. Check the results and debug your program if necessary.

Input

There are four lines.

The first two lines represent the greatest power and the corresponding coefficients of the first polynomial.

The last two lines represent the greatest power and the corresponding coefficients of the second polynomial.

Note that the coefficients are in descending order and each element is separated by a blank.

Output

Your program should print the coefficients of the sum, difference and product of these two polynomials in descending order, respectively.

Note that every answer should be followed by a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

A stack is an abstract data type that serves as a collection of elements, where a node can be added to a stack and removed from a stack only at its top. Two principal operations can be used to manipulate a stack: push, which adds an element at the top, and pop, which removes the element at the top of the collection.

Let’s see how the stack data structure can be realized in C++.We have an approach to implement stack: linked list. Thus, we define a class as follows:

class List_stack {

    public:

        List_stack();

        ~List_stack();

        void push(const int &);

        void pop();

        void print();

    private:

        ListNode *head;

        ListNode *tail;

};

where List_stack implements the stack data structure

REQUIREMENTS:

Implement the constructor, destructor, push(), pop() and print() member functions of List_stack classes.

Note:

1.This problem involves three files.

• function.h: Class definitions.
• function.cpp: Member-function definitions.
• main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp and function.h, and asked to implement function.cpp.

function.h

#ifndef FUNCTION_H #define FUNCTION_H #include <iostream> class ListNode { friend class List_stack; //make List_stack a friend public: ListNode( const int &info ) //constructor : data( info ), nextPtr( NULL ), prevPtr( NULL ) { } //end ListNode constructor private: int data; //data ListNode *nextPtr; // next node in list ListNode *prevPtr; }; //end class ListNode class List_stack { public: List_stack(); ~List_stack(); void push(const int &); void pop(); void print(); private: ListNode *head; ListNode *tail; }; #endif // FUNCTION_H

main.cpp

#include<iostream> #include<string.h> #include "function.h" using namespace std; int main(){ List_stack L_stack; char command[10]; int n; while(cin>>command){ if(strcmp(command,"pop")==0){ L_stack.pop(); }else if(strcmp(command,"push")==0){ cin >> n; L_stack.push(n); }else if(strcmp(command, "print") == 0){ L_stack.print(); cout << endl; } } return 0; }

2.For OJ submission:

       Step 1. Submit only your function.cpp into the submission block.

       Step 2. Check the results and debug your program if necessary.

Input

There are three kinds of commands:

• “push integerA” represents adding an element with int value A at the top of the stack.
• “pop “ represents removing the element at the top of the stack.
• “print” represents showing the current content of the stack.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output should consist of the current state of the stack.

When the stack is empty, you don’t need to print anything except a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss

Description

The problem will ask you to create a binary search tree, and there will be 4 kinds of commands to complete

1. P : please print out the binary search tree in in-order form in th line ,if the tree is empty, please print "NULL"(There is an whitespace between each number, also after the last number,no space after NULL)

2. GetMax : print out the maximum height of the binary search tree( There need no space after output number)

3. SumLevel (input) : print out  the sum value of the nodes at the input level in the line, if the input level is bigger than the maximum height, please print out "0". ( There need no space after output number)

4. AverLevel (input) : print out the average value of the nodes at the input level in the line, please show only 3 digits after decimal point of the average numbers of level, if the input level is bigger than the maximum height, please print out "0". (You can simply use %.3f to display in such way) ( There need no space after output number)

the root level will represent as 1( for SumLevel & AverLevel, if the input level is 0, please print "0")

Input

The first line contains an integer N , which indicates the number of nodes of the binary search tree.

The second line is the data for create binary search tree

The third line contains an integer M , which indicates the number of commands.

Following line will be the input instruction

If there is same input value, please ignore the second one.

Output

There need to print newline in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mr. Kuo is an adventurer. One day, he finds a secret room in a cave.

There is some hint to the password of this room.

Mr. Kuo is given an integer N and a string S = s₁s₂...s_N consisting of L and R.

At first, Mr. Kuo has a string A = "0".

For each i = 1, 2, ..., N :

• If s_i is L, insert i to the left of the "number" i - 1 in A.
• If s_i is R, insert i to the right of the "number" i - 1 in A.

The final contents of A is the password. Please help Mr. Kuo find the password.

For example, N = 3 and S = "LRL", then：

• s₁ = L, insert 1 to the left of 0,   A = "10"
• s₂ = R, insert 2 to the right of 1, A = "120"
• s₃ = L, insert 3 to the left of 2,   A = "1320"

Input

The first line contains one integer T — the number of test cases. Description of the test cases follows.

The first line of each test cases contains an integer N.

The second linef of each test cases contains a string S consisting of L and R of length N.

For each test：

1. T ≤ 100, N ≤ 10
2. T ≤ 100, N ≤ 100
3. T ≤ 100, N ≤ 500
4. T ≤ 100, N ≤ 1000
5. T ≤ 100, N ≤ 10000
6. T ≤ 10, N ≤ 100000

Output

For each test case print a string A — the final contents of the password, seperated by spaces.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A recursive acronym is an acronym (an abbreviation word formed from the first letter of words) that refer to itselft recursively. For instance, GNU stands for GNU not Unix. 

In the community of computer science, there exists somewhat a tradition that quite a few people tend to choose such recursive acronym to express their humorousness, e.g. ATI stands for ATI Technology Incoperated (a graphic card manufacturer which was acquired by AMD and became Radeon later), TikZ stands for TikZ ist kein Zeichenprogramm (German; TikZ is not a drawing program, TikZ is a LaTeX package to draw vector graphics), and so forth.

In this problem, your task is to determine whether some words can form a typical recursive acronym refering to the first word.

Note

This problem is case-insensitive, i.e., it does not matter that a letter is lower case or upper case.

You could call getline() to get entire content including spaces of a line until the newline character, and use stringstream to split the line by spaces.  For more detail, you may refer to online resources.

Input

Each test case may contain several lines. For each line, please determine whether it can form a typical recursive acronym refering to its first word or not.

The number of lines won't exceed 10. Each line won't contain more than 1000 words. The length of words won't exceed 1000.

Output

For each line, if it can form a typical recursive acronym refering to its first word, then print o'_'o, otherwise QQ. Remember to put a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Stiff Waist Beast is a electric god in NTHU CS. He has lots of friends. All his friends live on Tsing Hua Street. the i-th friend lives in number a_i. We define D as the sum of the distances from him to his friends' homes. 

One day, Stiff Waist Beast is going to move to the street. Since he often goes to visit his friends, so he wants to move to a place on Tsing Hua Street such that D is the smallest. Can you help him find the place? 

(There might be some people lives in the same place, since every building has many floors.)

Input

The first line has one integer N, means Stiff Waist Beast has n friends. 

The next line has N integers a₁ a₂ ... a_N.

1 <= N <= 2e5. 

0 <= a_i <= 1e9.

Output

Please output the place Stiff Waist Beast should move to and the smallest D.

(If there are multiple places make D the smallest, please output the smallest one.)

Some examples:

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Just as the title, you will be given a pre-order traversal of BST, please print the post-order traversal of it.

(BST is a tree that the number of each node will be larger than its left subtree, and smaller than its right subtree.)

Think 1: Is binary search useful in this problem?

Think 2: Is it possible not to build the tree?

hint1: just by looking at the sequence, can you find which are in the left subtree, which are in the right subtree?

hint2: the left subtree and the right subtree are both a tree, don't you think it sounds familiar? (recur...)

hint3: is there any way that we can find the beginning of the right subtree quickly?

Input

The first line contains one integer N, means there are n node in this tree. 

The next line has N different integers, which is the pre-order traversal of the BST. Each number is between [1, 1e9].

For testcase 1~3: 1 <= N <= 1e4.

For testcase 4~6: 1 <= N <= 2e5.

Output

Print the post-order of the BST.

Notice: print a space after each number and DO NOT print '\n' at last.

Sample Input  Download

Sample Output  Download

Tags

Discuss