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

After watching the movie 21, Kuo is curious about casino.

There is a casino which opens N days in this month.

There will be two kind of events in a day.

1. Guest <Someone> <Money> <Skill>. It means <Someone> enter the casino with <Money> money. <Someone> are their names, <Money> is the amount of money with them, and <Skill> is how well they play. If <Someone> are already in the casino or are blacklisted, ignore this event.
2. Win <Someone> <Money>. It means <Someone> win <Money> money in a play from the casino. <Money> may be positive or negative. If <Someone> are not in the casino or are blacklisted, ignore this event.

Whenever someone enter the casino, they have to pay T entrance fee to the casino. The enterance fee may change every day.

Whenever one become bankrupt, they will be kicked out of the casino and be blacklisted.

If the amout of money someone win in a play exceed (that is, >) twice of their <Skill>, they will be seen as cheaters, kicked out of the casino, and blacklisted. (The casino still has to pay the money they win to them.)

Someone blacklisted are not permitted to enter the casino. In particular, when someone blacklisted wants to enter the casino, they won't be charged the enterance fee.

Note: If someone have to pay X money but they only have Y money where Y <= X, they will only pay Y money and become bankrupt.

At the end of each day, everyone will leave the casino.

Please help Kuo-chan find how much income the casino gets in this month and who are blacklisted.

Input

The first line of the input contains a number N — the number of days in this month.

The following contains N blocks.

The first line of each block is Casino Q T — it means there will be Q events and the entrance fee is T this day.

The next Q lines is one of the following:

1. Guest <Someone> <Money> <Skill>
2. Win <Someone> <Money>

N <= 1000, Q <= 100. 

There will be at most 1000 different people come to the casino; that is, there are at most 1000 people with different names. Therefore, there will be at most 1000 people blacklisted.

All number is within the range of int.

Output

You should print a number U in the first line — how much income the casino gets in this month.

If there are K people blacklisted in this month, you should output their names in K lines in the order they get blacklisted.

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

In computer programming, a naming convention is a set of rules for choosing the character sequence to be used for identifiers which denote variables, types, functions, and other entities in source code and documentation, with the goal of enhancing program readability.

For the naming of identifiers, a common recommendation is "Use meaningful identifiers." A single word may not be as meaningful, or specific, as multiple words. Consequently, some naming conventions specify rules for the treatment of "compound" identifiers containing more than one word. Three most popular naming conventions are explained below:

• kebab case is a naming convention where words are separated by hyphens (“-”). For example, my-variable-name or my-function-name are examples of the kebab case.
• snake case is a naming convention where words are separated by underscores (“_”). For example, my_variable_name or my_function_name are examples of the snake case.
• camel case is a naming convention where the first letter of each word is capitalized and there are no separators. For example, MyVariableName or MyFunctionName are examples of the camel case.

(From Wikipedia, the free encyclopedia, https://en.wikipedia.org/wiki/Naming_convention_(programming))

In this problem, we consider an Integrated Development Environment (IDE) that supports naming convention conversion. We assume that the kebab case is the default naming convention. The IDE can convert to a different naming convention according to a programmer's preference. The IDE can also revert back to the default naming convention for the integration among multiple program files.

We first design the abstract base class ‘Case’ as an interface, which contains two pure virtual member functions: 

• convert: convert to the desired naming convention;
• revert: revert back to the default naming convention, i.e., the kebab case.

#include <iostream>
#include <string>
using namespace std;

class Case{
    protected:
        bool converted;
        string name;
    public:
        virtual void convert() = 0;
        virtual void revert() = 0;
        virtual ~Case(){}
        Case(string s): converted(false), name(s){}
        void show(ostream &os){
            os << name;
        }
        bool is_converted() const{
            return converted;
        }
};

class SnakeCase : public Case{
    public:
        SnakeCase(string s): Case(s){}
        void convert(){
            converted = true;
            for(int i = 0; i < name.length(); i++){
                if(name[i] == '-') name[i] = '_';
            }
        }
        void revert(){
            converted = false;
            for(int i = 0; i < name.length(); i++){
                if(name[i] == '_') name[i] = '-';
            }
        }
};

class CamelCase : public Case{
    public:
        CamelCase(string s): Case(s){}
        void convert();
        void revert();
};

In ‘function.h’, we also add the class ‘SnakeCase’ as a sample of implementing a derived class of the base class ‘Case’.

You are asked to implement another derived class ‘CamelCase’ by overriding the two virtual functions, convert and revert.

Note
It is highly recommended to practice std::stringstream in this problem. Here is a simple code that shows you how to use stringstream:

#include <iostream>
#include <sstream> // header file for stringstream
using namespace std;
int main(){
    string s;
    stringstream ss;
    getline(cin, s);
    ss << s;
    while(!ss.eof()){
        string t;
        getline(ss, t, ' ');
        cout << t << "\n";
    }
    return 0;
}
/*
- Sample Input
This is a sentence for testing this code.
- Sample Output
This
is
a
sentence
for
testing
this
code.
*/

For more information, please refer to this article.

Input

A line contains only lowercase letters and hyphens.

Output

The Snake case and the Camel case for the input string. Please refer to the sample output for details.

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

In this problem, you are asked to implement some functions of a queue with random access.

You are asked to implement a class IQueue with the following functions:

1. IQueue::IQueue(): Default constructor. Already implemented.
2. IQueue::IQueue(IQueue const& rhs): Copy constructor. Construct a new queue with the same elements as rhs.
3. IQueue::IQueue(IQueue&& rhs): Move constructor. Construct a new queue by moving the elements from rhs.
4. IQueue& IQueue::operator=(IQueue const& rhs): Copy assignment operator. Assign the elements of rhs to the current queue.
5. IQueue& IQueue::operator=(IQueue&& rhs): Move assignment operator. Move the elements from rhs to the current queue.
6. IQueue::~IQueue(): Destructor.
7. void IQueue::Push(int val): Push val to the back of the queue.
8. void IQueue::Pop(void): Pop the front element of the queue.
9. int& IQueue::Front(void): Return a reference to the front element of the queue.
10. int& IQueue::operator[](size_t pos): Return a reference to the element at index pos of the queue. It is guaranteed that pos is in the range \([0, size)\), so you don't need to check for out of range errors.
11. int& IQueue::At(size_t pos): Return a reference to the element at index pos of the queue. If pos is out of range, throw an std::out_of_range exception with the message "Out of range".
12. void IQueue::Swap(IQueue& rhs): Swap the elements of the current queue with rhs.
13. bool IQueue::Empty(void): Return true if the queue is empty, false otherwise.
14. size_t IQueue::Size(void): Return the number of elements in the queue. Already implemented.
15. void IQueue::DoubleCapacity(void): Double the capacity of the queue.

Note: The capacity of the queue is the maximum number of elements that can be stored in data. The size of the queue is the number of elements currently in data. When Push is called and the size of the queue is equal to the capacity, you should double the capacity of the queue.

Warning: You should use C++11 or later versions, or else you will get Compile Error! The move constructor and move assignment operator are added in C++11.

Hints:
What is an lvalue?
Value categories
Move Constructors in C++ with Examples
std::move

Input

This is a partial judge problem, input and output are handled by main.cpp.

Constraints

• \(10 \leq N \leq 10^5\) (\(N\) is the number of commands)
• For IQueue::Pop(void) and IQueue::Front(void), the queue is not empty.
• For IQueue::operator[](int pos), the index pos is in the range \([0, size)\).

Output

This is a partial judge problem, input and output are handled by main.cpp.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss