Description

Given a set of strings, perform the operations according to the following commands, and output the final result of the given set of strings.

Commands:

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.

e: Exit.

Consider a set of strings:

ab

cd

ef

And a sequence of commands:

s 0 1

i 1 2

The result will be:

cd

abef

ef

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

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

"int" is too small to store large numbers!

That's why you decided to implement your own data type, BigInt.

You need to implement 7 basic functions:

1. Constructor. It is initalized by a string representing a non-negative integer without leading zeroes (despite "0" itself).
2. Destructor.
3,4,5,6. ++x, x++, --x, x--, as in the C/C++ standard.
7: char* to_s(): returns a duplicate of the number in char*, e.g., "123".

UPDATE:

Note that you don't need to implement negative numbers. When the number is 0 and you have to decrement it, you can ignore the operation.

Input

The first line contains an integer T, representing the number of testcases that follow.

For each testcase, a non-negative integer less than pow(10, 1023) is given in the first line.

An integer Q follows, representing the number of operations regarding the testcase.

Q lines follow, each in the form of "B++", "++B", "B--", or "--B", the effect of which is the same as specified in the C/C++ standard.

Output

For each operation, print the result in one line, without leading zeroes.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

A. Definition of Max-Heap

A heap is a complete binary tree.

A max-heap is a complete binary tree in which the value in each internal node is greater
than or equal to the values in the children of that node.

B. Implementation of the Max-Heap Data Structure

1. Array:

An approach to store a max-heap 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. With this technique, the tree shown 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 parent and 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. Method to push/pop an element

1. PUSH 

• put the new element in the last place of the heap.
• compare with the parent, swap them until the parent is greater or equal to the new element. 
• example: push 11 to this heap
• 
• 
• 
• 
• 
• 
• 

2. POP

• put the last element to the top(root) of the heap.
• compare with the greater child, swap them until all child is smaller than it. 
• example: 
• 
• 
• 
• 
• 
• 
• 
• 

REQUIREMENTS:

Implement the constructor, push(), max(), pop() member functions of both the Array_MAX_HEAP and List_MAX_HEAP classes and deleteTree() of List_MAX_HEAP class.

Hint

For easy to solve this problem, you can call findparent(int cnt, ListNode *root) to return a ListNode which is the parent of node[cnt] in List_MAX_HEAP class.

Input

The first line contains an integer n.

Each of the next n lines has an instruction.

The instruction will be either:

• A_push: push a new element a_i into the array_max_heap.
• L_push: push a new element a_i into the list_max_heap.
• max: show the max element. if the max-heap is empty, print -1.
• A_pop: show and pop the max element in the array_max_heap. if the max-heap is empty, print -1.
• L_pop: show and pop the max element in the list_max_heap. if the max-heap is empty, print -1.
• size: show the size of the heap.

For all testcase:

1 <= n <= 1000, 0 <= a_i < 2³¹

(2/6) only A_push, L_push or size instruction

(2/6) only A_push, L_push, size or max instruction

(2/6) contains all instruction

Output

For max, A_pop or L_pop instruction, print the max element in the heap.

For size instruction, print the size of the heap.

Remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss

Description

There are N animals consisting of cats, fish, birds, and humans in a beautiful world.

Each animal has an unique name.

Initially, the HP of each animal is 0.

You have to perform the following operations:

• Name <i>：Print the name of the i-th animal.
• Species <i>：Print the species of the i-th animal.
• HP <i>：Print the HP of the i-th animal.
• Talk <i>：If the i-th animal is
  • human, print "Hello, world".
  • bird, print "Suba".
  • fish, print "?".
  • cat, print "Meow".
• Breath <i> <x> ：Increase the HP of the i-th animal by x.
• Sleep <i> <x>：If the HP of the i-th animal is less than or equal to 100, multiply its HP by x.
  • （Note that its HP may become larger than 100 after this operation)
• Eat <i> <j>：
  • If the i-th animal is cat and the j-th animal is fish,
  • or the i-th animal is bird and the j-th animal is fish,
  • or the i-th animal is human and the j-th animal is fish or bird,
    • then increase the HP of the i-th animal by the HP of the j-th animal
    • and turn the HP of the j-th animal into 0.
  • If the i-th animal is human and the j-th animal is cat,
    • then turn the HP of the i-th animal into 0.
  • Otherwise, do nothing. 

Input

The first line of the input contains a number N Q — the number of animals in the world and the number of operations.

Each of the next i = 1, 2, ..., N lines contains two strings — the species and the name of the i-th animal.

The next Q lines is one of the operations described in the statement.

N ≤ 1000

Q ≤ 300000

1 ≤ x ≤ 10 in operation Breath and Sleep

1 ≤ i, j ≤ N in every operation

Output

Whenever there's an operation "Name <i>", print the name of the i-th animal.

Whenever there's an operation "Species <i>", print the species of the i-th animal.

Whenever there's an operation "HP <i>", print the HP of the i-th animal.

Whenever there's an operation "Talk <i>", print the corresponding sentences according to the problem statement.

Remember to print '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Kuo-chan is given a sequence A and a constant K as his birthday present from Yang-chan.

Kuo-chan is allowed to perfrom the following operation:

1. push x — push x to the tail of A
2. pop — remove the median value of A （the median value of A is A[ (|A|+1)/2 ], with index start at 1）
3. programming tanoshi — for every element a in A, assign a % K to a
4. reverse — reverse the whole A, the head becomes the tail and the tail becomes the head

Whenever performing pop operation, the length of A is guaranteed to be odd, hence A won't be empty.

For example, if A = [4, 3, 5], K = 2

push 11　►　A = [4, 3, 5, 11]

reverse ► A = [11, 5, 3, 4]

push 7　►　A = [11, 5, 3, 4, 7]

pop　►　A = [11, 5, 4, 7]

programming tanoshi　►　A = [1, 1, 0, 1] 

Yang-chan is curious about what A is after Kuo-chan performs some operations to it.

Help him find it out!

（Remember to include function.h in your function.cpp file.）

Input

The first line contains three integers N K Q — the length of A, the constant Yang-chan gives Kuo-chan, the number of operations Kuo-chan performs.

The second line contains N integers a₁, a₂, ..., a_N （1 <= a_i <= N） — the elements of A. 

Each of the next Q lines describes the operations. Each line is one of three types:

1. push x （1 <= x <= 10000）
2. pop
3. programming tanoshi
4. reverse

Different testcases have different constraints.

1. N <= 10³, Q <= 2N, K <= 4000, operations: {pop, push}
2. N <= 10³, Q <= 2N, K <= 4000, operations: {pop, push, programming tanoshi}
3. N <= 10⁵, Q <= 2N, K <= 4000, operations: {pop, push}
4. N <= 10⁵, Q <= 2N, K <= 4000, operations: {pop, push, programming tanoshi}
5. N <= 10⁵, Q <= 3N, K <= 4000, operations: {pop, push, programming tanoshi, reverse}
6. N <= 10⁵, Q <= 3N, K <= 4000, operations: {pop, push, programming tanoshi, reverse}

Output

You should print one line containing the elements of A after the operations. For 1 <= i <= |A|, the i-th number should be A[ i ].

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

You might remember that we had a problem to merge two sorted linked lists at the beginning of the semester. Now we've learnt C++ ans thus the problem evolved a bit: templates, operator overloading are introduced, and we also micmic the behaviour of containers and iterators.

We declare the linked_list class with template, which has 2 member types (nested structs / classes), node & iterator.  The former is for our private internal design purposes only, whereas the latter is public to others.

Most of the member functions have been done. You only need implement 3 ones: dereference iterators, forward iterators and merge two sorted linked lists. Make sure to read the instructions in the header carefully.

Input

No parameter. The function would be called when *itr.

No parameter, too. The function would be called when ++itr.

The 2 parameters are the head of 2 sorted linked list.

It's guarantees that the sum of the total length of the linked list is less than 200000.

Output

For the dereference operator of iterator, you should return the reference to which the iterator / node point to.

As for the pre-increment operator of iterator, you should forward that iterator and return the iterator itself.

Lastly, for the merge method of linked list, you should return the head of the merged list. Linear time complexity is expected .

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

You will be given a preordered polynomial f(x). There will be Q queries, for each query x, please calculate the answer of f(x).

This is a partial judge problem, we have already implement a class Function to you. class Function has two functions:

• static Funtion *parse(stringstream &ss):
  used to parse the input, and it's already implemented.
• double eval(double x):
  used to calculate f(x), and this needs all its derived class to override it.

You need to implement the following 6 class inheritted from Function:

• Constant: represent a constant value, ex. 1, 5.3 etc.
  • static Constant *create(double x):
    read a double x as the constant
• Variable: represent variable, in this problem, the only variable is x.
  • static Variable *create(string s):
    read a string s as the variable
• Polynomial: represent polynomial(xⁿ), ex. 5³, x⁷, 9^x.
  • static Polynomial *create(Function *a, Function *b):
    read Function *a and Function *b as the base and exponential of the polynomial, which represent a^b
• Arithmetic: represent a arithmetic formula, ex. 5 + 3, 7 * x, x / 2.
  • static Arithmetic *create(Function *a, char op, Function *b):
    read Function *a, char op, and Function *b, the char op contains '+', '-', '*', '/'
• Sin: represent a sine function sin(f(x)).
  • static Sin *create(Function *a):
    read Function *a, represents sin(a)
• Cos: represent a cosine function cos(f(x)).
  • static Cos *create(Function *a):
    read Function *a, represents cos(a)

Please paste the following code after the code you write, and don't forget to include "function.h"!

Input

The first line contains a preordered polynomial f(x):

• Constants and Variable: constant value or variable x, ex. x, 5.3, 7
• Polynomial operator: ** a b, represent a^b
• Arithmetic operator: op a b, represent a op b, ex. + 5 x means 5 + x. op constains only + - * /
• Trignomotric operator: op a, represent op(a), ex. sin x means sin(x). op contains only sin and cos

The second line contains an integer Q, means the number of queries.

The following Q lines are the queries, each line contains a number x.

The length of the first line won't exceed 1e6, and 1 <= Q <= 2e5.

Each constant and query is between [-100, 100]. It's guarantee that no overflow and divided by 0

Output

For each x, please output the answer of f(x).

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss