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

Tags

Discuss

Description

This is a partial judge problem.

In this problem, you have to implement some power function in class special_power:

• special_power(int n)  default constructor
• int fpow(int x)  return xⁿ % 880301
• int fpow(int x, int m)  return xⁿ % m
• int fpow()  return 2ⁿ % 880301
• string fpow(string s)  return sⁿ
• string fpow(string s, int m)  return sⁿ % m

Note that n is a member in class special_power.

The definition of sⁿ: 

Repeat the elements of s n times, and connect them

For example:

• abcd⁴ = aaaabbbbccccdddd
• csst³ = cccssssssttt

The definition of sⁿ % m:

Repeat the elements of s n times, and connect them.

If the length of sⁿ is longer than m, ignore the remaining elements.

For example:

• abcd⁴ % 10 = aaaabbbbcc
• csst³ % 4 = cccs

Input

The input has only one line, contains three integer x, n, m and one string s.

For all testcase:

• 1 <= x, m <= 10⁹
• 1 <= n <= 10⁶
• 1 <= |s| <= 1000
• (1/6) 1 <= xⁿ, 2ⁿ < m <= 880301, 1 <= |s| * n <= m
• (1/6) 1 <= xⁿ, 2ⁿ < m <= 880301
• (1/6) 1 <= |s| * n <= m

Output

The output has five lines.

The 1st line, output the result of xⁿ % 880301

The 2nd line, output the result of xⁿ % m

The 3rd line, output the result of 2ⁿ % 880301

The 4th line, output the result of sⁿ

The 5th line, output the result of sⁿ % m

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

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

There is a template function unique() in STL (Standard Template Library), which takes two iterators \(begin, end\) as parameters, removes all except the first element from every consecutive group of equal elements in the left-closed-right-open range hold by the two iterators \([begin, end)\) and return the iterator to the new end, i.e., the next of the last element not removed.

For instance, in the first of the sample input, since \(k=1\), it's equivlent to the ordinary unique(). So for the string "qqq", you should return the itrerator next to the first 'q'.

And in this problem, your task is to extend this feature more generally, i.e., remove all excpet the first \(k\) elements from every consecutive group.

Note

You should do it in place, returning valid iterator between origin range. Try to use constant extra space only.

If you want to run the code locally, you have to name your implementation Main.cpp. For more detail, please read instructions in the header.

Input

Since this problem is judged partially, you needn't be concerned about the format of input.

In case your're interested, there are several test cases, each of which contain four lines: the first line is two integers \(n, k\) and the following lines are a sring, \(n\) intergers and \(n\) floating point numbers.

\[0<n<10^6\]

\[0<k\leq n\]

Output

Since this problem is judged partially, you needn't be concerned about the format of output.

In case your're interested, for each test case, the judge code would print out the result after calling k_unique() for the sting, integers and floating point numbers.

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

Most of the problem are as same as Polynomial Calculator (https://acm.cs.nthu.edu.tw/problem/13890/), the only difference is that you think if a calculator can only calculate f(x) is too weak, so you decide to add a function: differential.

There is one more function in class Function:

Function *differential(): this is used to return the differential function, and it needs all its derived class to override it.

Differential Formula:

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, it's guarantee no x in 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 an integer 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) and f'(x).

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

This problem involves processing a prefix expression by constructing its syntax tree. The syntax tree is built using a base class STNode and two derived classes: OperandNode (for operands) and OperatorNode (for operators).

The program should:

1. Convert the given prefix expression into its equivalent postfix expression by performing a postorder traversal of the syntax tree
2. Evaluate the prefix expression using the provided values for variables A to Z

Your tasks are:

1. Override the printNode() and eval() functions in the derived classes
   • There are three operators, &, | and ^, which represent bitwise AND, bitwise OR and bitwise XOR, respectively
2. Implement the destructor of class OperandNode and OperatorNode to properly delete all nodes in the tree
3. Implement makeNode(char) of both derived classes
   • In OperandNode, the function should take name (the variable name) as input
   • In OperatorNode, the function should take op (the operator) as input
4. Overload the << operator to enable printing a node using cout

Hint: How to overload "cout <<" to print anything?
Hint: You may get RE or MLE if the destructor is not implemented correctly

Input

The first line contain one integer $T$, representing the total number of testcases.

Following $2T$ lines, each testcase consists of $2$ lines

• The first line contains 26 integers, representing the values of variables A to Z, respectively.
• The second line contains a string $S$, representing a prefix expression

Constraints

• $1 \leq T \leq 1000$
• $\text{Sum of }|S| \leq 5 \cdot 10^5$
• Variable name is a single capital alphabet

Output

For each test case, output exactly two lines:

1. The first line should display the postfix expression converted from the given prefix expression.
2. The second line should display the evaluated result of the prefix expression.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss