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

There are N numbers in a queue.  The origin sequence is from 1 to N. (1 is the head). The operation “Move a b” means to move all the numbers in front of a (including a) and then insert them in front of b without changing order.  Given several such operations and output the final status of the sequence.

Input

There will be only one test case. The test case begins with an integer N indicating the number of people.  There are several operations followed.  The format is “Move a b” (without quote) you can assume that the position of a is in front of the position of b.  The test case is terminated by “Exit” (without quote).

subtask 1 : 1<=N<=100, you can use O(N) algo for each operation.

subtask 2 : 1<=N<=100, you can use O(N) algo for each operation.

subtask 3 : 1<=N<=100000, you need use O(1) algo for each operation.

subtask 4 : 1<=N<=1000000, you need use O(1) algo for each operation.

Output

Output the numbers from the first one to the last one, and separate two consecutive numbers by a space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You need to write a program to simulate a queue of names.  Each name is a string consisting of English letters only.  There are three operations:

1.         “Push [name]”, which means to enque name in the queue.

2.         “Pop”, which means to deque. If the queue is empty, this operation takes no effect.

3.         “Front”, which means to print out the name in the front of queue. If the queue is empty, print "empty" (without quotes).

Case1 : #operation <= 10^2, There will be no "Pop" and "Front" command when queue is empty.
Case2 : #operation <= 10^3. There will be no "Pop" and "Front" command when queue is empty.
Case3 : #operation <= 10^4.
Case4 : #operation <= 10^6.

Input

Each line contains one of the following operations. “Push [name]” (without quotes), “Pop” (without quotes), “Front”(without quotes). The length of each name is at most 10.

Output

For each “Front” operation, print out the name in the front of the queue.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an integer sequence, say {6, 1, 3, 4, 5, 2}, can we sort the sequence by keeping swapping the first number with its two neighbors: the second number and the last number ? 

For example, Swap the first number 6 and with the last number 2 to get {2, 1, 3, 4, 5, 6}, and then swap the first number 2 and the second number 1 to get {1, 2, 3, 4, 5, 6}, and we get the sequence sorted.

In function.h we define a class called SwapSort. A constructor and a member function show_solutions are implemented. Your task is to complete the implementation of the following two functions:

1. set<State> extend(State s);
A State is defined as using State = vector<int>;
For some State s, we may extend it by swapping the first number with the second one, or swapping the first number with the last one. Therefore, from State s we may generate two new states, and insert them into a set.

2. void solve(int steps);
This function tries to solve the problem in a number of swaps specified by steps. The found solutions are stored in the class member set<list<State>> _solutions;

Notice that, no duplicate states are allowed in a solution.

You need to implement the two functions in function.cpp

main.cpp

#include "function.h" int main() { State s;// = {2, 1, 3}; int e; while (cin >> e) { // press Ctrl + Z to end the input s.push_back(e); } SwapSort prob1(s); prob1.solve(4); prob1.show_solutions(); cout << "\n"; }

function.h

#ifndef _SWAPSORT_ #define _SWAPSORT_ #include <iostream> #include <vector> #include <set> #include <list> #include <algorithm> using namespace std; using State = vector<int>; class SwapSort { private: set<list<State>> _paths; set<list<State>> _solutions; set<State> _explored; public: SwapSort(State init) { list<State> ls; ls.push_back(init); _paths.insert(ls); } void show_solutions() { if (_solutions.size()==0) { cout << "No solution.\n"; } else { for (auto p : _solutions) { for (auto s : p) { for (auto i : s) { cout << i << " "; } cout << "-> "; } cout << ".\n"; } } } set<State> extend(State s); void solve(int steps); }; #endif

function.cpp

#include "function.h" set<State> SwapSort::extend(State s) { set<State> SS; // your code here return SS; } void SwapSort::solve(int steps) { while (steps>0) { set<list<State>> oldPaths; set<list<State>> newPaths; for (auto p : _paths) { // your code here } for (auto p : oldPaths) { _paths.erase(p); } for (auto p : newPaths) { _paths.insert(p); } --steps; } }

Input

An integer sequence, separated by spaces. End by EOF.

Output

The output will be generated by function.h

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Given two vectors of numbers, output their intersection set.

Note: the numbers of vectors need not to be unique.

Input

There are multiple test cases. Each case contains four lines. The first line begins with an integer N. The second line contains N integers, representing the numbers in the first set. The third line has one integer M, and the fourth line contains M integers, represent the numbers in the second set. All the numbers are 32 bit signed integers. The input is terminated if N = 0.

For case 1, 1 <= N, M <= 10³
For case 2, 1 <= N, M <= 10⁴
For case 3, 1 <= N, M <= 10⁵
For case 4, 1 <= N, M <= 10⁶

Output

For each test case, print the intersection of the two sets. Output them in ascending order. If the intersection of the two sets is an empty set, print “empty” (without quotes).

Note: There's a newline character at the end of each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

This problem will help you understand how to use std::map.

http://en.cppreference.com/w/cpp/container/map

Notice, this time, first and last is [first, last].

目前有五個測資，第三筆測資不算，答題測資看另外四筆

Input

The input consist of series of command. Each commands is insert, range output or range erase.

insert: inserts a string (cmd) with the key (key) to map. If the key has already existed, insert the cmd at the begining of string (the string which the key belongs).

For example,

insert 0 "abc"

insert 1 "def"

the map should contain "abc", "def".

insert 0 "xyz"

the map should contain "xyzabc", "def".

range output: outputs the string from key (first) to key (last). Output a space character (' ') after printing an element.

range erase: erase the string from key (first) to key (last).

operator<<: outputs all strings in map. From the smallest key to biggest key. Output a space character (' ') after printing an element.

Output

Complete insert, output, erase and operator<<.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

A string is said to be a SM string if it matches one of the following rules:

(1) An empty string is a SM string.

(2) If strings S1 and S2 are both SM strings, then S1S2 is SM string.

(3) If a string S is SM string, then {S}, [S], (S) and <S> are SM strings.

(4) If a string S is SM string, then "sm"S is a SM string.

Given a string consisting of parentheses, determine if it is a SM string.

Input

The input consists of several lines.

Each line contains a string S(1 <= |S| <= 10^6 ), where S consists of only '{', '}', '[', ']', '(', ')' and "sm".

Output

For each strings S, output "SM" if it is a SM string, "MS" if not.

There should be a '\n' in the end of each line.

Sample Input  Download

Sample Output  Download

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