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

Maintain a doubly linked list, which supports the following operations:

(1) IH i : Insert a new integer i to the head of the list.

(2) IT i : Insert a new integer i to the tail of the list.

(3) RH : Print and remove the element in the head of the list. If the list is empty, print a blank line.

(4) RT : Print and remove the element in the tail of the list. If the list is empty, print a blank line.

(5) S : Swap the first floor(k/2) elements and the last k - floor(k/2) elements, where k is the total number of elements in the list. For example, if k = 5, the result of swapping a1, a2, a3, a4, a5 will be a3, a4, a5, a1, a2.

To improve the performance, it is suggested that three pointers be maintained in case4: head, tail and middle, where middle points to the floor(k/2) + 1-th element. With the help of these pointers, all of the operations can be done in constant time.

Input

There is only a single set of input and each operation will occupy a line. There will be a space between “IH” and “i”, and “IT” and “i”. The input contains OP operations, and it is terminated by end-of-file (EOF). You may assume that i is a nonnegative integer not greater then 100000. The list is initially empty.
For case1 and case2, 1<=OP<=1000
For case3, 1<=OP<=10000, For each S operation, O(n) is also accepted.
For case4 and case5, 1<=OP<=500000, each operation should be done in O(1).

Output

For each “RH” or “RT” operation, print a line containing the removed integer as commanded by the operation.
For RH and RT operation: if the list is empty, print a blank line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12224.cpp

Partial Judge Header

12224.h

Tags

Discuss

Description

"Cat or Dog? that's a good question. " Shakespeare never said, 2019.

In this questions there are three types of animals class have to be implemented. (Cat , Dog and Caog)
Coag is a kind of special animal mixed in Cat and Dog.

Dog can only throwball
Cat can only play with carton.
Caog do those things both.

when Dog / Caog playing throwball output "it looks happy!\n"

when Cat  / Caog playing with carton output "it looks so happy!\n"

and also there's a zoo can count how many animals are in the zoo.

In this questions you have to implement 3 class (cat , dog and caog) based on the sample code.

Input

All input data would be finish in given main functions.

First number N would be N animals ( N < 10)

the following Ai numbers would types of animals.

And the T would be T instructions ( T < 30) 

the following Ti would be index and instructions

 

Output

 

When Animals born Zoo will auto output which kind of animal is born and how many animals in the zoo.

When Animals dead Zoo will auto output which kind of animal isdeadand how many animals in the zoo.

when Dog / Caog playing throwball output "it looks happy!\n"

when Cat  / Caog playing with carton output "it looks so happy!\n"

when Barking:

Cat would "meow!\n"

Dog would "woof!\n"

Caog would "woof!woof!meow!\n"

Sample Input  Download

Sample Output  Download

Partial Judge Code

12257.cpp

Partial Judge Header

12257.h

Tags

Discuss

Description

When failed to unlock user account of smart phone, ipad, laptop, you will be unable to access them again. Furthermore, some machines make fun of you.

Mr.Yuan decides to create a new login system “200M” which generates a random number as password when the user tries to access it.
Because it’s almost impossible to login successfully in one try, the user can ask machine whether the password P is greater/less than a certain number x for at most 200 times.

As a CS student, you found the system “200M” has serious security issues.
To show how serious it is, you decided to write a program to hack “200M” for T times.
For each time attacking “200M”, you can make some queries to “200M” and guess the password.
If you guess correctly, the next round will be started. Otherwise, just make more queries and guess until success.
Once the number of query+guess has been more than 200, the login system “200M” will freeze your login account which means you can’t access it again.

Your task is to design a strategy to hack “200M” base on the answer of it and the decision you have made before.

This problem is partial judge. You’re asked to complete functions of class Engineer:

• Constructor, Destructor
• void init(): Initialization when start a new attack.
• MakeQuery(char* query_str): Make a query (string) to “200M” base on your history.
  ( or just random guess password if you’re the chosen one. )
• GetAnswer(bool ans): Get the answer from Machine and do something.

Query satisfies following format:

• query_str = “op x”
• op is one of "greater", "less", "guess"
• x is an integer in the range of int
• ex:
  • "greater 10", "guess 71", "less -22" are legal
  • "Greater 10", "guess 0.5", "less 99999999999", "guess33" are illegal.

If you want interact with “200M” by yourself, use the function.cpp below:

#include "function.h"

Engineer::Engineer(){ 
    // TODO
}

Engineer::~Engineer(){
    // TODO
}
void Engineer::init(){
    // TODO
}

void Engineer::MakeQuery(char* query_str){
    // Interactive Version
    char op[100];
    int x;
    scanf("%s %d", op, &x);
    sprintf(query_str, "%s %d", op, x);
    
    // Determine the query string by history
    // TODO

void Engineer::GetAnswer(bool ans){
    // TODO
}

Input

An integer T, denoting the number of attacks.
It’s guaranteed that:

• 1 ≤ T ≤ 10,000
• 1st testcase:  0 ≤ P ≤ 10
• 2nd testcase: 0 ≤ P ≤ 1,000
• 3rd testcase: 0 ≤ P ≤ 10,000
• 4th testcase: P ∈ range of int.

Output

It's unnecessary to handle output by yourself.

There’re 2 kind of print function in main.cpp:

• printf("..."): print the messages on “stdout”, OJ judges the result by this.
• fprintf(stderr, "..." ): print the messages on “stderr”, OJ ignores the messages of “stderr” while judging.
• both of “stdout”, “stderr” will be shown on cmd prompt
• The part of “stderr” can be different for every person.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12762.cpp

Partial Judge Header

12762.h

Tags

Discuss

Description

There is a function called "the one function",
the function is defined as:
F(N, M) = 1, if M <= N,
F(N, M) = F(N, M-1) + F(N, M - 2) + ... + F(N, M - N), if M > N

Given you N, M, tell the result of F(N, M) module 1000000009.

ouo.
Updated at: 2020/05/17 19:00, sorry for the typo in the description.

This is an exercise of operator overloading,
it is recommended that you can follow the partial judge code to finish your work.
There are 8 member functions and 1 additional function that you should implement.
Read the comments carefully to better understand the structure of the partial judge code.

You should choose 'c++11' as the option of submission.

For sample input 1,

N = 3, M = 5,
so F(3, 1) = F(3, 2) = F(3, 3) = 1,
and F(3, 4) =  F(3, 3) + F(3, 2) + F(3, 1) = 3
and F(3, 5) = F(3, 4) + F(3, 3) + F(3, 2) = 5
and F(3, 5) % 100000009 = 5,
so the output must be 5.

Input

The input contains 1 line,
the first line contains 2 numbers N, M.

It is guaranteed that:
1 <= N <= 100
1 <= M <= 10^9

Output

The output contains 1 line.

Output the answer of F(N, M), and a newline character at the end of line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12767.cpp

Partial Judge Header

12767.h

Tags

Discuss