Description

Given a tree, count the number of leaves in this tree. Each node has unique integer identification (ID), but all IDs may not be consecutive.

Input

There are multiple test cases. Each test case begins with an integer N (1 <= N <=1000). In the following N lines, each line has two integer a and b (1 <= a,b <= 1000), indicating node a is node b’s parent. The next line contains an integer R, which represents the root of the Tree. You can assume that all the nodes will be on the same tree. The input is terminated by N = 0.

Output

Print the number of the leaves for each test case.

Hint: All leaves have no children!

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

一個八數字推盤遊戲由3*3的棋盤組成，每一個格子上都有一個數字(0~8且不重複)，一開始盤面是亂的，

每次操作可以將0與其上.下.左.右的數字互換，經過若干次操作：

step 1 : 0往右與5互換

step 2 : 0往下與6互換

最後將盤面排回

即為正解。
Rody最近沉迷於八數字推盤遊戲當中，但最近要開始期末大爆炸了，Rody不再那麼空閒，因此他決定要先跳過太過困難的題目，等到暑假再來解。

困擾的Rody想要請你幫他鑑定題目的困難度。

Input

input第一行有一整數T(1<=T<=30)，代表底下有T筆測資。
第2~T+1行分別有9個不同的整數(0<=t1,t2,...,t9<=8)，代表一個八數字推盤遊戲。

(註:9個整數以row major方式填入3*3的盤面，如第二組測資 1 2 3 4 0 5 7 8 6 等同於下方示意圖)

Output

對於每組八數字推盤遊戲，若能在14步內完成遊戲，請輸出"You can solve it within x steps."，x為解決該遊戲所需的最少移動次數。

否則，請輸出"You'd better skip this game."

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

If you are not familiar with partial judge , please check this handout

A. Definition of Binary Search Trees

A binary search tree (BST) is a binary tree, whose internal nodes each store a key and each have two sub-trees, commonly denoted left and right. The tree additionally satisfies the property: the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in the right sub-tree.

Based on the above property of BSTs, when a node is to be inserted into an existing BST, the location for the node can be uniquely determined. For example, if a node with key 6 needs to be inserted into the following BST

the BST will become

B. Implementation of the BST Data Structure

There are two approaches to BST implementation: array and linked list.

1. Array:

An approach to storing a BST is to use a single, contiguous block of memory cells, i.e., an array, for the entire tree. We store the tree’s root node in the first cell of the array. (Note that, for ease of implementation, we ignore the 0th cell and start from the 1st cell.) Then we store the left child of the root in the second cell, store the right child of the root in the third cell, and in general, continue to store the left and right children of the node found in cell n in the cells 2n and 2n+1, respectively. Using this technique, the tree below

would be stored as follows

2. Linked list:

We set a special memory location, call a root pointer, where we store the address of the root node. Then each node in the tree must be set to point to the left or right child of the pertinent node or assigned the NULL value if there are no more nodes in that direction of the tree.

C. Detailed C++ Implementation for BST

Let’s see how the BST data structure can be realized in C++.We have two different approaches to BST implementation: array and linked list. Thus, we define four classes and use polymorphism as follows:

function.h

#ifndef function_h #define function_h #include <iostream> #include <math.h> using namespace std; class BST{ public: BST():Height(0){} virtual ~BST() {} virtual void insert(const int &) = 0; virtual bool search(const int &) const = 0; virtual void print() const = 0; int height() const { return Height; }// An empty tree has height of 0. A tree with only root node has height of 1. protected: int Height; }; class Array_BST : public BST{ public: Array_BST(); virtual ~Array_BST() {} virtual void insert(const int &) override; //root node is stored at index 1. virtual bool search(const int &) const override; virtual void print() const override{ int k = pow(2, height()); for (int i = 1; i <= k-1; i++) { if (array[i] != 0) cout << array[i] << " "; } } private: int array[1025]; }; class ListNode{ friend class List_BST; //make List_BST a friend public: ListNode(const int &info):key( info ),left( NULL ),right( NULL ) //constructor { }//end ListNode constructor private: int key; ListNode *left; ListNode *right; };//end class ListNode class List_BST : public BST{ public: List_BST(); virtual ~List_BST() { deleteTree(root); } virtual void insert(const int &) override; virtual bool search(const int &) const override; virtual void print() const override{ int i; for(i = 1; i <= Height; i++){ printGivenLevel(root, i); } } private: ListNode *root; // private member functions ListNode* createLeaf(int key) const; //new a ListNode and return its address /* clean a tree.*/ void deleteTree(ListNode *root); void printGivenLevel(ListNode* Ptr, int level) const { if (Ptr == NULL) return; if (level == 1) cout << Ptr->key << " "; else if (level > 1) { printGivenLevel(Ptr->left, level-1); printGivenLevel(Ptr->right, level-1); } } }; #endif /* function_h */

main.cpp

#include <iostream> #include <string.h> #include "function.h" using namespace std; void BSTManipulator(BST& bstobj1,BST& bstobj2, char cmd ){ int n; if (cmd == 'I') { cin >> n; bstobj1.insert(n); bstobj2.insert(n); }else if (cmd == 'S'){ cin >> n; if (bstobj1.search(n)) { cout << "yes" << endl; }else{ cout << "no" << endl; } if (bstobj2.search(n)) { cout << "yes" << endl; }else{ cout << "no" << endl; } }else if (cmd == 'H'){ cout << bstobj1.height() << endl;; cout << bstobj2.height() << endl;; }else if (cmd == 'P'){ bstobj1.print(); cout << endl; bstobj2.print(); cout << endl; } } int main(){ Array_BST A_bst; List_BST B_bst; char cmd; while (cin >> cmd) BSTManipulator(A_bst, B_bst, cmd); return 0; }

REQUIREMENTS:

Implement the constructor, insert(), search() member functions of both the Array_ BST and List_ BST classes and createLeaf(), deleteTree() of List_ BST class.

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.

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 four kinds of commands:

• “I A”: insert a node with int value A into the BST
• “S A”: if the integer A exists in the BST, print “yes”; otherwise, print “no”.
• “P”: show the current content of the BST.
• “H”: print the BST’s height.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output shows the result of each command.

When the BST 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

Tags

Discuss

Description

You are required to use linked list to do the multiplication of two polynomials.

Input

The input contains two lines. Each lines presents a polynomial. The format of each line is looked like : "5 4 -3 2 1 0" which means polynomial "5x⁴-3x²+1x^0".

Each polynomial must contain a constant term. (You can use this rule to determine whether the polynomial is end.)

For example, "-2 3 1 1 0 0" should be -2x³+1x¹.

(The input polynomial should be arrangement in descending power.)

Output

Output the answer. Print a space character in the begining.

For example, if the input is

5 4 -3 2 1 0 (means 5x⁴-3x²+1)

-2 3 1 1 0 0 (means -2x³+1x¹)

the output should be 

" -10 7 11 5 -5 3 1 1" (which means -10x⁷+11x⁵-5x³+x).

If the value of coefficient is 0, you don't have to print it.

(The output polynomial should be arrangement in descending power.)

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Warning: You are not allowed to use:

1. any static variables

2. any variables which is not inside a function

3. malloc and free

The storage of the vector is handled automatically, being expanded and contracted as needed. Vectors usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a vector does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted.

REQUIREMENTS:

Implement the push_back(), pop_back(), reserve() and destructor member functions of Vector classes.

Note:

If the value of size is equal to the value of capacity, and you need to change the value of capacity (reallocate memory) when you push_back a new element. The rule of increasing capacity is: new capacity = max(old capacity + 1, old capacity * 3).

The constructor of vector will not create an array (which means size and capacity is 0).

Input

here are five kinds of commands:

• pop_back: removes the last element
• push_back: adds an element to the end
• capacity: returns the number of elements that can be held in currently allocated storage
• size: returns the number of elements
• reserve: reserves storage (Increase the capacity of the container to a value that's equal to new capacity. If new capacity is greater than the current capacity, new storage is allocated, otherwise the method does nothing.)

Each commands is followed by a new line character ('\n').

Output

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

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Given a set of strings, perform the operations according to the following commands.

Commands: (n will not be equal to m)

s n m:

Swap the n^th string and the m^th string.

i n m:

Insert the m^th string at the tail of the n^th string.

si n m:

Swap the specified strings first, and then insert.

is n m:

Insert first, and then swap the two specified strings.

t n m:

If the n^th string is equal to the m^th string, do i n m. Otherwise, do s n m.

e:

Exit.

Note:

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

Str::Str(char*);

Str::Str(const Str &);

bool Str::operator==( const Str &) const;

Input

The first line is an integer N indicating the number of input strings.

The following N lines each contains one input string.

Starting from the N+2^th line will be a sequence of commands.

Output

Output the final result of the input strings.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Wild cats take care of each other in the wild. However, when winter comes, the preys are not enough to feed all the cats. Therefore, the cats dine according to the order of their occupations. The order is as follows:
1. elder
2. nursy
3. kitty
4. warrior
5. apprentice
6. medicent
7. deputy
8. leader

In the tradition of the cat society, three different cats serve as the medicent, the deputy, and the leader respectively.
As for the other cats, except that the apprentices have the dining priority of the young over the old, for the other occupations, the old have higher priority. If the occupations and the ages of two or more cats are the same, they will dine in lexicographic order according to their names.

Input

There are multiple test cases.

The first line of each test case contains two integers N and M, indicating the number of cats and the portions of food respectively, where 0<N,M<=10000.

The next N lines are the information of each cat, including name, occupation, and age.
The length of the names will not exceed 30 letters and will contain no spaces.

Output

Please output the cats that could eat the food in order, each name a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Give a postfix expression, which has 4 operators, ‘+’ , ‘-’, '*' , '/',and positive integers. Print the result.

Notice: testcases don't include parentheses so just follow arithmetic rule.

            And you don't need to consider divide 0 or some tricky rules : )

Input

The input contains exactly 1 sequences of postfix expression. It contains operators, ‘+’  ‘-’ '*' '/',and positive integers separated by a space.

The end of the input is 0.

The length of input sequence is smaller than or equal to 40

Output

The output is the result of the expression.

There is a newline symbol in the end

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Implement a Vector class that support n-dimensional vector dot product.

Your task is to complete​

• const int operator[](int index) const;
• int operator*(const Vector& a);

inside the Vector class;

Remember to #include "function.h"!

Input

First line of input is an integer m, where m is the number of testcases.There are m testcases following.

A testcases consists of three lines:

• In the first line of each testcase, there are a string OP and an integer n, where OP is the operation and n is the vector size.
• In the second line of each testcase, there are n integers, representing all the elements inside the first vector, A.
• In the third line of each testcase, there are n integers, representing all the elements inside the second vector, B.

​It is guaranteed that:

• 1 ≤ n, m ≤ 100
• For all the elements x in vector A and B, |x| ≤ 100

Output

For each testcase, according to its operation, output the result of A*B. There is a space after every number.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

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

Maintain a doubly linked list, which supports the following operations:

(1) IH i : Insert a new integer i to the head of the list.

(2) IT i : Insert a new integer i to the tail of the list.

(3) RH : Print and remove the element in the head of the list. If the list is empty, print a blank line.

(4) RT : Print and remove the element in the tail of the list. If the list is empty, print a blank line.

(5) S : Swap the first floor(k/2) elements and the last k - floor(k/2) elements, where k is the total number of elements in the list. For example, if k = 5, the result of swapping a1, a2, a3, a4, a5 will be a3, a4, a5, a1, a2.

To improve the performance, it is suggested that three pointers be maintained in case4: head, tail and middle, where middle points to the floor(k/2) + 1-th element. With the help of these pointers, all of the operations can be done in constant time.

Input

There is only a single set of input and each operation will occupy a line. There will be a space between “IH” and “i”, and “IT” and “i”. The input contains OP operations, and it is terminated by end-of-file (EOF). You may assume that i is a nonnegative integer not greater then 100000. The list is initially empty.
For case1 and case2, 1<=OP<=1000
For case3, 1<=OP<=10000, For each S operation, O(n) is also accepted.
For case4 and case5, 1<=OP<=500000, each operation should be done in O(1).

Output

For each “RH” or “RT” operation, print a line containing the removed integer as commanded by the operation.
For RH and RT operation: if the list is empty, print a blank line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss