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

If you are not familiar with partial judge , please check this handout

---

A. Definition of Binary Search Trees

A binary search tree (BST) is a binary tree, whose internal nodes each store a key and each have two sub-trees, commonly denoted left and right. The tree additionally satisfies the property: the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in the right sub-tree.

Based on the above property of BSTs, when a node is to be inserted into an existing BST, the location for the node can be uniquely determined. For example, if a node with key 6 needs to be inserted into the following BST

the BST will become

 

B. Implementation of the BST Data Structure

There are two approaches to BST implementation: array and linked list.

1. Array:

An approach to storing a BST 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. Using this technique, the tree 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 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. Detailed C++ Implementation for BST

Let’s see how the BST data structure can be realized in C++.We have two different approaches to BST implementation: array and linked list. Thus, we define four classes and use polymorphism as follows:

function.h

#ifndef function_h #define function_h #include <iostream> #include <math.h> using namespace std; class BST{ public: BST():Height(0){} virtual ~BST() {} virtual void insert(const int &) = 0; virtual bool search(const int &) const = 0; virtual void print() const = 0; int height() const { return Height; }// An empty tree has height of 0. A tree with only root node has height of 1. protected: int Height; }; class Array_BST : public BST{ public: Array_BST(); virtual ~Array_BST() {} virtual void insert(const int &) override; //root node is stored at index 1. virtual bool search(const int &) const override; virtual void print() const override{ int k = pow(2, height()); for (int i = 1; i <= k-1; i++) { if (array[i] != 0) cout << array[i] << " "; } } private: int array[1025]; }; class ListNode{ friend class List_BST; //make List_BST a friend public: ListNode(const int &info):key( info ),left( NULL ),right( NULL ) //constructor { }//end ListNode constructor private: int key; ListNode *left; ListNode *right; };//end class ListNode class List_BST : public BST{ public: List_BST(); virtual ~List_BST() { deleteTree(root); } virtual void insert(const int &) override; virtual bool search(const int &) const override; virtual void print() const override{ int i; for(i = 1; i <= Height; i++){ printGivenLevel(root, i); } } private: ListNode *root; // private member functions ListNode* createLeaf(int key) const; //new a ListNode and return its address /* clean a tree.*/ void deleteTree(ListNode *root); void printGivenLevel(ListNode* Ptr, int level) const { if (Ptr == NULL) return; if (level == 1) cout << Ptr->key << " "; else if (level > 1) { printGivenLevel(Ptr->left, level-1); printGivenLevel(Ptr->right, level-1); } } }; #endif /* function_h */

main.cpp

#include <iostream> #include <string.h> #include "function.h" using namespace std; void BSTManipulator(BST& bstobj1,BST& bstobj2, char cmd ){ int n; if (cmd == 'I') { cin >> n; bstobj1.insert(n); bstobj2.insert(n); }else if (cmd == 'S'){ cin >> n; if (bstobj1.search(n)) { cout << "yes" << endl; }else{ cout << "no" << endl; } if (bstobj2.search(n)) { cout << "yes" << endl; }else{ cout << "no" << endl; } }else if (cmd == 'H'){ cout << bstobj1.height() << endl;; cout << bstobj2.height() << endl;; }else if (cmd == 'P'){ bstobj1.print(); cout << endl; bstobj2.print(); cout << endl; } } int main(){ Array_BST A_bst; List_BST B_bst; char cmd; while (cin >> cmd) BSTManipulator(A_bst, B_bst, cmd); return 0; }

REQUIREMENTS:

Implement the constructor, insert(), search() member functions of both the Array_ BST and List_ BST classes and createLeaf(), deleteTree() of List_ BST class.

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.

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 four kinds of commands:

• “I A”: insert a node with int value A into the BST
• “S A”: if the integer A exists in the BST, print “yes”; otherwise, print “no”.
• “P”: show the current content of the BST.
• “H”: print the BST’s height.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output shows the result of each command.

When the BST is empty, you don’t need to print anything except a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11020.cpp

Partial Judge Header

11020.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

Before starting this homework, you are recommended to read the extra handout, in order to better understand the meaning of inheritance!

 

If you are not familiar with partial judge , please read this handout

---

Niflheimr loves to play mobile games.

Based on his experience, he categorized all mobile game players into 2 categories:

• NTDWarrior, who spend a lot of money on games.
• PoorPlayer, who can't afford to buy items in the cash shop inside the game, unless they sell their kidney(腎) QQ.

Similarly, he categorized all mobile games into 2 categories:

• GTCGame, which provides shops for NTDWarrior to use cash to buy items inside the game. (GTC stands for game time card)
• FreeGame, in which there is no cash shop for game players.

Now Niflheimr get some information about a few players:

• power(for all Player), which means the basic gaming skill the player own.
• dad_money (for NTDWarrior only), which means how much money the player can get every month from his/her dad. (He/She must have a rich daddy~)
• kidney(for PoorPlayer only), which is the only way the PoorPlayer can get money for playing GTCGame.

Moreover, the winner of each kind of games can be decided by the following rules:

• GTCGame

  • The total_power for each player should be calculated as follow:

    • NTDWarrior: power + 100 *dad_money
    • PoorPlayer: power + 100000 * kidney

• FreeGame

  • The total_power for each player is equal to his/her power, i.e. the value of dad_money or kidney are not concerned.

• For all games, the winner can be decide as follow:

  • If no one has total_power greater than or equal to the difficultyof theGame, then the result of the game is Failed.
  • Otherwise, if the total_power of two players are the same, the result is Draw.
  • Otherwise, the winner is the player with higher total_power.

For each given game and its players, Niflheimr wants to know who will win the game.

Input

Input consists of several testcases.

First line of input is an integer N, indicating # of testcases.

Then N testcases follows. Each testcase consists of three lines:

First line and second line of each testcases are alike, in the following format:

name_type_power_extra, where '_' indicates a space character, and

• name is a string, represent the name of the player
• type is an integer, 0 if the player is a PoorPlayer , 1 if the player is a NTDWarrior
• power is an integer, represent the power of the player
• extra is an integer, represent dad_money if the player is NTDWarrior, or kidney if the player is PoorPlayer

The third line contains two integers difficulty and type

• difficulty is the difficulty of the game
• type is the type of the game, 0 if the game is FreeGame, 1 if the game is GTCGame

Output

For each testcase, print out the result of each game.

See the above description and void print_result(int result_code, string winner) defined within Game class.

You are recommended to utilize void print_result(int result_code, string winner) for output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11919.cpp

Partial Judge Header

11919.h

Tags

Discuss