Description

The task is to define the class ‘RleCodec’ for run-length encoding.

About implementing the virtual function:

We have the base class ‘Codec’ as an interface. The member functions in ‘Codec’ are pure virtual functions. Therefore we need to implement those virtual functions in the derived class ‘RleCodec’. The functions ‘decode’, ‘show’, ‘is_encoded’ are already done. The only function you need to complete is ‘RleCodec::encode’ in ‘function.cpp’.

In ‘main.cpp’, we see two functions having an argument of type ‘Codec&’:

    std::ostream& operator<<(std::ostream& os, Codec& data);

    void encode_decode(Codec& data);

Since ‘RleCodec’ is a derived class of ‘Codec’, we may pass an object of ‘RleCodec’ to the above two functions by reference as if it is an object of ‘Codec’. Calling ‘data.show(os);’ will invoke the virtual function of the corresponding derived class.

About run-length encoding:

The rule of run-length encoding is simple: Count the number of consecutive repeated characters in a string, and replace the repeated characters by the count and a single instance of the character. For example, if the input string is ‘AAADDDDDDDBBGGGGGCEEEE’, its run-length encoding will be ‘3A7DBB5GC4E’, because there are three A’s, seven D’s, … etc. Note that we do not need to encode runs of length one or two, since ‘2B’ and ‘1C’ are not shorter than ‘BB’ and ‘C’.

In ‘function.h’, we add the class ‘DummyCodec’ as a sample of implementing a derived class of the base class ‘Codec’. You do not need to change anything in ‘function.h’. The only function you need to write for this problem is the function ‘RleCodec::encode’ in ‘function.cpp’.

Hint: std::stringstream could be useful in solving this problem. Please refer to ‘RleCodec::decode’ for how to use std::stringstream.

You only need to submit ‘function.cpp’. OJ will compile it with ‘main.cpp’ and ‘function.h’.

We have already provided partial function.cpp belowed.

Note that if you can't use "auto".

For codeblock, go to the codeblock menu Settings --> Compiler ... --> Compiler flags and check Have g++ follow the C++11 ISO C++ language standard [-std=c++11]

For command line compiler, use g++ myprog.cpp -std=c++11 -o myprog

main.cpp

#include <iostream> #include "function.h" std::ostream& operator<<(std::ostream& os, Codec& data) { data.show(os); return os; } void encode_decode(Codec & data) { if (!data.is_encoded()) data.encode(); else data.decode(); } int main() { std::string input_string; std::cin >> input_string; DummyCodec dummy{input_string}; encode_decode(dummy); std::cout << "Dummy encoding: "; std::cout << dummy << std::endl; encode_decode(dummy); std::cout << "Dummy decoding: "; std::cout << dummy << std::endl; RleCodec rle{input_string}; encode_decode(rle); std::cout << "RLE encoding: "; std::cout << rle << std::endl; encode_decode(rle); std::cout << "RLE decoding: "; std::cout << rle << std::endl; }

function.h

#ifndef _FUNC_H #define _FUNC_H #include <iostream> #include <string> class Codec { public: virtual void encode() = 0; virtual void decode() = 0; virtual ~Codec() { } // Do nothing virtual void show(std::ostream& os) const = 0; virtual bool is_encoded() const = 0; }; class DummyCodec: public Codec { public: DummyCodec(std::string s): encoded{false}, code_str{s} { } void encode() { encoded = true; } void decode() { encoded = false; } void show(std::ostream& os) const { os << code_str; } bool is_encoded() const { return encoded; } private: bool encoded; std::string code_str; }; class RleCodec: public Codec { public: RleCodec(std::string s): encoded{false}, code_str{s} { } void encode(); void decode(); void show(std::ostream& os) const { os << code_str; } bool is_encoded() const { return encoded; } private: bool encoded; std::string code_str; }; #endif

function.cpp

void RleCodec::encode() { // Your code here encoded = true; } void RleCodec::decode() { //No cheating : ) }

 

 

Input

A line contains of several characters .

Output

There are four lines.

The first and second lines are dummy encoding and decoding. You don't need to implement it.

The third and forth lines are RLE encoding and decoding.

Each line is followed by a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11014.cpp

Partial Judge Header

11014.h

Tags

Discuss

Description

Warning: You are not allowed to use malloc and free

Giving a bass-class Shape3D and 4 derived class : Sphere （球體）, Cone （圓錐）, Cuboid （長方體）, Cube （立方體）

You need to calculate the volume of each shape.

PS:

V of Sphere: V = 4/3 π r³

V of Cone: V = 1/3 π r² h

 

note : Remember to do some basic check, if the input is illegal (e.g.  length < 0, pi < 0 .....)  then the volume should be 0.

You don't need to consider the scenario like Cuboid -1 -2 3, volume would be 0 instead of 6.

Hint1: Be careful the type of volume is double.  4/3=1 (int),  so it should be 4.0/3.0

Hint2: You only need to implement the constructors.

Hint3: Note that Cube inherited Cuboid not Shape3D.

 

 

Input

There are only 4 shapes in this problem :

• Sphere, following by its radius and pi. (e.g. Sphere 30 3.14)
• Cone, following by its radius of bottom plane, height and pi. (e.g. Cone 3 100 3.14)
• Cuboid, following by its length, width and height. (e.g. Cuboid 2 3 7)
• Cube, following by its length. (e.g. Cube 2)

Output

Ouput the total volume of all the shapes.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11443.cpp

Partial Judge Header

11443.h

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

12715.cpp

Partial Judge Header

12715.h

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

13131.cpp

Partial Judge Header

13131.h

Tags

Discuss

Description

Kuo is curious about the casino after watching the movie, Twenty One.

 

There is a casino which opens N days this month.

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

There will be two kinds 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. Twenty One. It means there will be some players playing twenty one.

Everyone's name is composed of at most 4 English letters.

 

In a Twenty One game：

There will be one banker, one guard, and one server. They have banker_ski, guard_ski, and server_ski skill respectively.

There will be K players playing twenty one; however, ignore those who are blacklisted or not in the casino.

Each of the players places their bets bet_i first, then draw some cards.

The banker draws the cards last.

Let A be the sum of the i-th player's cards, B be the sum of the banker's.

Then:

1. A > 21 and B > 21, nothing happens.
2. A <= 21 and (B > 21 or A > B), the i-th player wins.
3. B <= 21 and (A > 21 or B >= A), the i-th player loses.

 

For the banker:

• If the i-th player wins, the banker has to pay bet_i dollars to the i-th player.
• If the i-th player wins and ski_i < banker_ski, the banker has to pay the i-th player 10 * (the sum of the i-th player's cards) as a bonus.
• Furthermore, if the i-th player wins and the sum of the i-th player's cards is equal to 21, the banker has to pay 2*(bets + bonus) to the i-th player. (bonus may be equal to 0)
• For example, if the sum of the i-th player's cards is 21, ski_i < banker_ski, and bet_i = 1000, then the banker has to pay (1000+10*21)*2 to the i-th player.
• Whenever a player becomes bankrupt, the banker calls the guard to kick the player out and gives the guard 100 dollars.
• Whenever a player is seen to be a cheater; that is, 3*ski_i < the amount of money including the bets and the bonus the banker has to pay to the player, the banker calls the guard to kick the player out and gives the guard 100 dollars.

 

For the guard:

• When the guard has to kick i-th player who is a cheater out, if guard_ski < ski_i, the guard has to pay (ski_i - guard_ski) dollars to the i-th player; if guard_ski >= ski_i, the guard doesn't have to pay.
• When the guard has to kick a bankrupt player out, the guard doesn't have to pay.

 

For the player:

• If the i-th player loses, the i-th player has to pay bet_i dollars to the banker.
• If the i-th player loses but bet_i >= the amount of money the i-th player has now, the i-th player only has to pay all the money they have. In this case, the i-th player becomes bankrupt.
• If the i-th player is not in the casino or is already kicked out of the casino, ignore any of the i-th player's bets and cards.
• Whenever the i-th player wins this time and have more than server_ski dollars whether the player cheats or not, the i-th player will pay the banker 2000 dollars and the server 1000 dollars to buy some wine. (The player will have more than 3000 dollars when buying wine.)

 

The banker,  the guard, and the server have 0 dollars at the beginning of each Twenty One game.

After each Twenty One game, the money the banker gets will be the casino's income.

 

If a player is kicked out of the casino by the guard, the player will be blacklisted.

If a person whose amount of money is less than or equal to T, this person will be charged nothing, kicked out, and blacklisted at once.

Those blacklisted are not permitted to enter the casino. 

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

If the amount of income on this day is bigger or equal to a number U, the boss of the casino, JN will feel happy and clear the blacklist.

 

You can use this code to draw cards.

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 U — it means there will be Q events, the entrance fee is T and the U mentioned in the description this day.

The next Q lines are one of the following:

1. Guest <Someone> <Money> <Skill>
2. Twenty One

For a Twenty One event：

The first line of the block contains three numbers — banker_ski, guard_ski, and server_ski.

The second line of the block contains a number K — the number of players.

For the next 2K lines, i = 1, 2, ..., K,

There will be a string name_i and a number bet_i in the 2i - 1 line — the i-th player's name and the bets they place.

There will be some numbers c₁, ..., c_t in the 2i line — the cards the i-th player has.

The last line of each block will be some numbers c₁, ..., c_t — the cards the banker has.

 

N, Q <= 100

K <= 200

server_ski >= 10^4

• testcase 1 to 6：T = 0, U = 10⁹, server_ski = 10⁹, all number is within the range of int.
• testcase 6 to 9：U = 10⁹, server_ski = 10⁹, all number is within the range of int.
• testcase 11 to 12：server_ski = 10⁹, all number is within the range of int.
• testcase 13 to 15：All number is within the range of int.

 

Output

For every Twenty One game：

The first line of output should contain three numbers banker_money, guard_money, and server_money — the money the guard, the banker, and the server gets.

Each of the next N lines should contain a string name_i and money_i — the name of the player and the money they have after playing, in the order of the time they enter the casino.

 

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

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

Sample Input  Download

Sample Output  Download

Partial Judge Code

13214.cpp

Partial Judge Header

13214.h

Tags

Discuss

Description

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

 

Whenever an animal's HP turns into 0 or negative, it becomes dead and you should print "<its name> dead" right away.

 

You have to perform the following operations:

• Birth <name> <species>
  • An animal with name <name>, species <species>, and HP 10 is born.
  • Print "<name> birth" right away.
  • （Note that the animals will be numbered by the order they are born.）
• Infromation <i>  
  • If the i-th animal is alive, print its name, species, and HP.
• Talk <i> 
  • If the i-th animal is alive and 
    • cat, print "Meow".
    • fish, print "?".
    • bird, print "Suba".
    • human, print "Hello, world".
• Breath <i> <x> 
  • If the i-th animal is alive, increase the HP of the i-th animal by x.
• Sleep <i> <x>
  • If the i-th animal is alive and its HP is less than or equal to 100, multiply its HP by x.
  • （Note that its HP may become larger than 100 after this operation.）
• Work <i> <x>
  • If the i-th animal is alive, decrease its HP by x.
  • （Note that it may become dead after this operation.）
• Eat <i> <j>
  • If the i-th animal and the j-th animal are both alive and
    • 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 （which means the j-th animal dies）.
    • 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 （which means the i-th animal dies）.
    • Otherwise, do nothing. 

 

Input

The first line of the input contains a number Q — the number of operations.

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

 

Q ≤ 400000

1 ≤ x ≤ 10 in operation Breath, Sleep and Work.

 

Output

Whenever there's an operation "Birth <name> <species>", print "<name> birth".

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

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

Whenever an animal becomes dead, print "<its name> dead".

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

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

13450.cpp

Partial Judge Header

13450.h

Tags

Discuss

Description

Mr. Kuo is an adventurer. One day, he finds a sequences of operations and an empty set S.

Each operation is one of the following two types,

1. Insert x：insert x into S. Duplicate element is legal.
2. Query x k：Among the elements of S that are greater or equal to x, what is the k-th smallest value？

 

Mr. Kuo is curious about the answer to each operation 2, so he asks for your help.

 

Hint：You can refer to C++ upper_bound function. 

Input

The input consists of multiple lines.

Each line is given in one of the following two format：

1. Insert x
2. Query x k

 

There will be at most 100000 operations in the sequences.

1 ≤ x ≤ 10⁹

1 ≤ k ≤ 5

 

Output

For each operation of type 2, print the k-th smallest value among the elements of S that are greater than or equal to x.

If there are less than k elements of S that are greater than or equal to x, then print "-1".

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

 

Sample Input  Download

Sample Output  Download

Tags

Discuss