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 ‘QCAQGDQBBQEGQACQDE’, where QCA means that there are 3 A’s and 3 can be encoded as C (the third character in alphabet), QGD means that there are 7 D’s and 7 can be encoded as G (the 7 th character in alphabet), and QBB means we have 2 B’s and 2 can be encoded as B (the second character in alphabet) … etc. Note that every encoding segment starts with a Q.

If there are 27 A’s in a string, it is separated into two segments ‘QZAQAA’, which means the first segment ‘QZA’ represents 26 A’s, and the second segment ‘QAA’ represents 1 A.

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

#include <iostream> #include <string> #include <sstream> #include <cctype> #include "function.h" void RleCodec::encode() { } void RleCodec::decode() { std::stringstream os; std::string int_str; char q = 'A'; char number = ' '; int cnt = 0; for (auto c : code_str) { if (q=='A') { q = c; }else if(number == ' '){ number = c; } else { int_str.push_back(c); int cnt = 0; cnt = number - 'A' +1; for (int i=0; i<cnt; ++i) os << c; int_str.clear(); number = ' '; q = 'A'; } } code_str = os.str(); encoded = false; }

Input

A line contains of several characters .(n <= 100)

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

11021.cpp

Partial Judge Header

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

This is a partial judge problem OwO

There are  people in a row. From left to right, they are numbered from 1 to . The happy value of the -th person is . And there is a ball which is carried by the first person in the beginning. Now they want to play a game called "Happy Ball".

In this game they need to execute  operations. There are 3 types of operations:

1. The person who is carrying the ball need to speak out his/her happy value loudly.
2. The person who is carrying the ball passes the ball to the person on the left side(or right side). This will last  times. The passing direction(i.e to left or to right) will be given and is fixed in one operation. Stop passing if no one is on the corresponding side of the person who is carrying the ball.
3. The person who is carrying the ball leave the row. Before leaving, he/she would pass the ball to the person on the right side(or left side if no one is on the right side).

This game looks not funny, right?

Anyway, you need to write a program to simulate this game. For each first-type operation, output the happy value of the person who is carrying the ball. In this problem, there is a special constraint: the number of second-type operations times the number of third-type operations is less than or equal to Q.

Solve this problem with array and/or linked list(maintaining the people in the row and who is carrying the ball)!

Hint

The following table is the Time Complexity of each type operation of array and linked list.

	the first-type	the second-type	the third-type
array
linked list

It's obvious that array is good at the second-type operation and linked list is good at the third-type operation.

So you could depend on the operations to choose the one which is much better and create it.  

Note

In the following code, nullptr is just like NULL in C. You could treat them as the same.

But nullptr is only available in C++11 and beyond. So compiling/submitting your code in C++11 or beyond.

Partial Code

main.cpp

#include <iostream>
#include "function.h"
using namespace std;
int main() {
    /* I/O optimization */
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int *arr = new int[n + 1];
        for(int i=1;i<=n;i++)    cin >> arr[i];

        int q;
        cin >> q;
        Operation *ops = new Operation[q + 1];
        for(int i=1;i<=q;i++) {
            cin >> ops[i].type;
            if(ops[i].type == 2)    cin >> ops[i].d;
        }

        ContainerBase *solver = create(n, arr, q, ops);
        for(int i=1;i<=q;i++) {
            if(ops[i].type == 1)
                cout << solver->print() << '\n';
            else if(ops[i].type == 2)
                solver->move(ops[i].d);
            else
                solver->remove();
        }

        delete[] arr;
        delete[] ops;
        delete solver;
    }
    return 0;
}

function.h

#ifndef FUNCTION_H
#define FUNCTION_H

/* an abstract class for the container used in this problem */
class ContainerBase {
    public:
        /* for the first-type operation */
        virtual int print() = 0;
        /* for the second-type operation */
        virtual void move(int) = 0;
        /* for the third-type operation */
        virtual void remove() = 0;
        int getSize() { return size; }

        virtual ~ContainerBase() {}
    protected:
        int size;    // the number of elements(people) in the container
};

/* array class deriving from ContainerBase */
class Array final : public ContainerBase {
    public:
        Array() {}
        Array(int n, int *arr) {
            size = n;

            mem = new int[size + 1];
            for(int i=1;i<=size;i++)    mem[i] = arr[i];
            cur = 1;
        }

        virtual int print() override { return mem[cur]; }
        /* TODO */
        virtual void move(int) override;
        /* TODO */
        virtual void remove() override;

        ~Array() { delete[] mem; }
    private:
        int *mem;    // array for maintaining all the elements(the happy value of all the people)
        int cur;    // record who is carrying the ball
};

/* doubly linked list class deriving from ContainerBase */
class List final : public ContainerBase {
    public:
        List() {}
        List(int n, int *arr) {
            size = n;

            cur = new Node(arr[1]);
            Node *back = cur;
            for(int i=2;i<=n;i++) {
                Node *newNode = new Node(arr[i]);
                back->insertBack(newNode);
                back = newNode;
            }
        }

        virtual int print() override { return cur->getVal(); }
        /* TODO */
        virtual void move(int) override;
        /* TODO */
        virtual void remove() override;

        ~List() { for(int i=1;i<=size;i++)    cur = cur->remove(); }
    private:
        /* nested class for the node in linked list */
        class Node {
            public:
                Node() {}
                Node(int newVal) : pre(nullptr), nxt(nullptr), val(newVal) {}
                /* insert a new node after the current node */
                void insertBack(Node *newNode) {
                    nxt = newNode;
                    newNode->pre = this;
                }
                /* remove the current node and return the next node(or the previous node if the next node doesn't exist) */
                Node* remove() {
                    Node *ret = (nxt == nullptr ? pre : nxt);
                    if(pre != nullptr)    pre->nxt = nxt;
                    if(nxt != nullptr)    nxt->pre = pre;
                    delete this;
                    return ret;
                }
                Node* getPre() { return pre; }
                Node* getNxt() { return nxt; }
                int getVal() { return val; }
            private:
                Node *pre, *nxt;
                int val;
        } *cur;    // record who is carrying the ball
};

/* a class for operation */
class Operation {
    public:
        int type,d;
};

/* TODO: create array/linked list based on operations and return it */
ContainerBase* create(int, int*, int, Operation*);

#endif

You need to implement the five functions: Array::move, Array::remove, List::move, List::remove and create.

Input

The very first line contains an integer  – the number of tasks.

The first line of each task contains an integer  – the number of people in the beginning.

The second line contains  integers  – the happy value of all the people.

The third line contains an integer  – the number of operations excuted.

Then  lines follow. The -th line of each task contains an integer  – the type of the -th operation. If  is equal to 2, then an integer  follows. The passing direction of a second-type operation is right when its  is positive or left otherwise. The number of second-type operations times the number of third-type operations is less than or equal to Q.

 

It's guaranteed that:

• The 1st testcase must be identical to the Sample below
• For the first 6 testcases: 

Output

For each task, output one line which represents the happy value of who is carrying ball for every first-type operation.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13205.cpp

Partial Judge Header

13205.h

Tags

Discuss