Description

The Josephs problem is notoriously known. For those who are not familiar with the problem, among n people numbered 1, 2, . . . , n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give the message about the incident.

The persons are eliminated in a very peculiar order; m is a dynamical variable, which each time takes a different value corresponding to the Fibonacci numbers succession (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...). So in order to kill the i-th person, Josephus counts up to the i-th Fibonacci number.

For example, there are 6 people in a circle, and the sequence of counting is Fibonacci number succession (1, 1, 2, 3, 5 …).

In the beginning, the step to kill m = 1. The sequence of killing people is as follows.

1.............................(kill 1, and m is changed to 1)

2.............................(kill 2, and m is changed to 2)

3, 4.........................(kill 4 ,and m is changed to 3)

5, 6, 3.....................(kill 3 ,and m is changed to 5)

5, 6, 5, 6, 5.............(kill 5)

Then print 6 as answer.

 

Let’s solve this problem using C++. You have been provided with the following class definitions:

 

class Node

{

   friend class Josephus;

   public:

        Node():next( NULL ){

        }

          Node( const int &info ) //constructor

      :number( info ), next( NULL )

      {

      } //end ListNode constructor

   private:

          Node *next;

        int number;

};//end class Node

 

class Josephus

{

    public:

         Josephus();

         ~Josephus();

         Josephus(const int &);

         int kill(); // return the survival’s position

 

    private:

        void generatecircularlinkedList(const int &); // generate circular linked-list

        void generateFib(const int &); // generate a Fibonacci sequence table

        int sequence[50]; // store Fibonacci number

        int noOfPeople;

        Node *head;

};

 

REQUIREMENTS:

In this practice, you are asked to implement the following member functions:

Josephus class:

• constructor
• destructor
• int kill();
• void generatecircularlinkedList(const int &);
• void generateFib(const int &);

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.

function.h

#ifndef FUNCTION_H #define FUNCTION_H #include <iostream> class Node { friend class Josephus; public: Node():next( NULL ){ } Node( const int &info ) //constructor :number( info ), next( NULL ) { } //end ListNode constructor private: Node *next; int number; };//end class Node class Josephus { public: Josephus(); ~Josephus(); Josephus(const int &); int kill(); // return the survival’s position private: void generatecircularlinkedList(const int &); // generate circular linked-list void generateFib(const int &); // generate a Fibonacci sequence table int sequence[50]; // store Fibonacci number int noOfPeople; Node *head; }; #endif // FUNCTION_H

main.cpp

#include <iostream> #include "function.h" using namespace std; int main(){ int numofpeople; while(cin>>numofpeople){ Josephus Jose(numofpeople); int survival = Jose.kill(); cout<<survival<<endl; } }

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

Each line contains a number n<=45, which is the number of people. Input is terminated by EOF.

Output

The output will consist in separate lines containing the position of the person which life will be saved.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10996.cpp

Partial Judge Header

10996.h

Tags

Discuss

Description

A queue is an abstract data type that serves as a collection of elements, where nodes are removed only from the head of the queue and are inserted only at the tail of the queue. Two principal operations can be used to manipulate a queue: enqueue, which inserts an element at the tail, and dequeue, which removes the element at the head of the collection.

Let’s see how the queue data structure can be realized in C++.We have an approach to implement queue: linked list. Thus, we define a class as follows:

 class List_queue {

    public:

        List_queue();

        ~List_queue();

        void enqueue(const int &);

        void dequeue();

        void print();

    private:

        ListNode *head;

        ListNode *tail;

};

where List_queue implements the queue data structure.

REQUIREMENTS:

Implement the constructor, destructor, enqueue(), dequeue() and print() member functions of the List_queue 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.

function.h

#ifndef FUNCTION_H #define FUNCTION_H #include <iostream> class ListNode { friend class List_queue; //make List_queue a friend public: ListNode( const int &info ) //constructor : data( info ), nextPtr( NULL ), prevPtr( NULL ) { } //end ListNode constructor private: int data; //data ListNode *nextPtr; // next node in list ListNode *prevPtr; }; //end class ListNode class List_queue { public: List_queue(); ~List_queue(); void enqueue(const int &); void dequeue(); void print(); private: ListNode *head; ListNode *tail; }; #endif

main.cpp

#include<iostream> #include<string.h> #include "function.h" using namespace std; int main(){ List_queue L_queue; char command[10]; int n; while(cin>>command){ if(strcmp(command,"dequeue")==0){ L_queue.dequeue(); }else if(strcmp(command,"enqueue")==0){ cin >> n; L_queue.enqueue(n); }else if(strcmp(command, "print") == 0){ L_queue.print(); cout << endl; } } return 0; }

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

• “enqueue integerA” represents inserting an element with int value A at the tail of the queue.
• “dequeue” represents removing the element at the head of the queue.
• “print” represents showing the current content of the queue.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output should consist of the current state of the queue.

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

Sample Input  Download

Sample Output  Download

Partial Judge Code

10997.cpp

Partial Judge Header

10997.h

Tags

Discuss

Description

Let’s implement a list class.

• Task 1:

First you are asked to implement class OWList (standing for “one-way list”). You have definitions of classes ListNode and OWList as follows:

         class ListNode
         {
                friend class OWList; //make OWList a friend
                friend class TWList; //make TWList a friend

          public:
                ListNode( const int &info ) //constructor
                : data( info ), nextPtr( NULL )
                {
                } //end ListNode constructor

           private:
               int data; //data
               ListNode *nextPtr; // next node in list

           }; //end class ListNode

           class OWList
           {
           public:
                //default constructor
                OWList();
                //destructor
                ~OWList();
                //insert node at front of list
                void insertAtFront( const int &value );
                //remove node from front of list
                void removeFromFront();
                //is List empty?
                bool isEmpty() const;
                //display contents of List
                void print() const;

            protected:
                ListNode *firstPtr; //pointer to first node
                ListNode *lastPtr;  //pointer to last node
             }; // end class OWList

            Requirement: Implement the member functions

             1. “OWList::OWList();”: initializes the two pointers firstPtr and lastPtr as NULL.

             2. “OWList::~OWList();”: deletes allocated dynamic memory space.

             3. “void OWList::insertAtFront( const int &value );”

             4. “int OWList::removeFromFront();”

             5. “bool OWList::isEmpty() const;”

             6. “void OWList::print() const;”

• Task 2:

Implement another class TWList (standing for “two-way list”), which is derived from class OWList:

        class TWList:public OWList
        {
        public:
             //default constructor
             TWList()
             :OWList()
              {
                    /*It will still work correctly if you omit the constructor call of the base class in the above member                            initializer list. The compiler will invoke this default constructor of OWList implicitly.*/
              }
              //destructor
              ~TWList()
              {
                     /*You don't need to delete the list again because the

                        compiler will invoke the destructor of the base class OWList to do this.*/
              }
              //insert node at back of list
             void insertAtBack( const int &value );
              //delete node from back of list
             void removeFromBack();

          };

            Besides the functions inherited from OWList, TWList has two more functions: insert a node at the end of             the list and remove a node from the end of the list.

           Requirement: Implement the member functions

            7. “void TWList:: insertAtBack( const int &value );”

          8.“int TWList:: removeFromBack();”

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.

#ifndef FUNCTION_H

#define FUNCTION_H

#include <iostream>

class ListNode

{

    friend class OWList; //make OWList a friend

    friend class TWList; //make TWList a friend

 

public:

    ListNode( const int &info ) //constructor

    : data( info ), nextPtr( NULL )

    {

    } //end ListNode constructor

 

private:

    int data; //data

    ListNode *nextPtr; // next node in list

}; //end class ListNode

 

 

class OWList

{

public:

    //default constructor

    OWList();

    //destructor

    ~OWList();

    //insert node at front of list

    void insertAtFront( const int &value );

    //remove node from front of list

    void removeFromFront();

    //is List empty?

    bool isEmpty() const;

    //display contents of List

    void print() const;

 

protected:

    ListNode *firstPtr; //pointer to first node

    ListNode *lastPtr;  //pointer to last node

 

}; // end class OWList

 

class TWList:public OWList

{

public:

    //default constructor

    TWList()

    :OWList()

    {

        /*It will still work correctly if you omit the constructor call of the base

          class in the above member initializer list. The compiler will invoke this

          default constructor of OWList implicitly.*/

    }

    //destructor

    ~TWList()

    {

        /*You don't need to delete the list again because the compiler

          will invoke the destructor of the base class OWList to do this.*/

    }

    //insert node at back of list

    void insertAtBack( const int &value );

    //delete node from back of list

    void removeFromBack();

};

#endif

#include <iostream>

#include <string>

#include "function.h"

using namespace std;

int main()

{

    TWList integerList;

    int command;

    int value; // store node value

 

    while (cin >> command)

    {

        switch(command)

        {

        case 1: // insert at beginning

            cin >> value;

            integerList.insertAtFront(value);

            break;

        case 2: // insert at end

            cin >> value;

            integerList.insertAtBack(value);

            break;

        case 3: // remove from beginning

            integerList.removeFromFront();

            break;

        case 4: // remove from end

            integerList.removeFromBack();

            break;

        }

    }

    integerList.print();

    cout<<endl;

}

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 types of command:

• “1 integerA” represents inserting a node with int value A at the head of the list.
• “2 integerB” represents inserting a node with int value B at the end of the list.
• “3” represents removing the node at the head of the list
• “4” represents removing the node at the end of the list

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output should consist of the final state of the list. 

Sample Input  Download

Sample Output  Download

Partial Judge Code

11010.cpp

Partial Judge Header

11010.h

Tags

Discuss

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

Create a class Matrix to represent a N * N matrix.

Provide public member functions that perform the following tasks:

1. Matrix addition.
2. Matrix subtraction.
3. Matrix Multiplication.
4. Adding cell value by 1 (module 10). That is, if after adding 1, a cell value becomes 10 we change it to 0.
5. Matrix Transpose.

Input

The first line has an integer N (1<=N<=50), which means the size of the matrix. The total number of elements in the matrix is thus N * N.

 

For the next 2N lines:

• The first N lines specify the elements of the first matrix a.
• The following N lines specify the elements of the second matrix b.

All elements in matrix are in the range of 0-9.

All elements in the same line are separated by a space.

Output

Output the answer of each task.

In the matrix, all of the integers in the same line are separated by a space, and a newline character at the end of the line.

Ex:

1 2 3"\n"

4 5 6"\n"

7 8 9"\n"

Note : In main function, there is already a newline character between each matrix.

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

11407.cpp

Partial Judge Header

11407.h

Tags

Discuss

Description

Create a class Polynomial. The internal representation of a Polynomial is an array of terms. Each term contains a coefficient and an exponent, e.g., the term 2x⁴ has the coefficient 2 and the exponent 4.

 

Provide public member functions that perform each of the following tasks:

1. Adding two Polynomial.
2. Subtracting two Polynomial.
3. Multiplying two Polynomial.

Input

There are four lines.

The first two lines represent the greatest power and the corresponding coefficients of the first polynomial.

The last two lines represent the greatest power and the corresponding coefficients of the second polynomial.

The greatest power is in the range of 0-25.

Note that the coefficients are in descending order and each element is separated by a space.

Output

Output the coefficients of the sum, difference and product of these two polynomials in descending order.

If the result of coefficient is 0, just print it.

ex:

2

1 2 1

0

0

The answer will be :

1 2 1

1 2 1

0 0 0

Note that there is a new line character at the end of each answer.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11408.cpp

Partial Judge Header

11408.h

Tags

Discuss

Description

Create a class Matrix to represent an N x N matrix.

Provide public member functions that perform or derive:

1. Interchanging two rows.
2. Rotating Matrix by 90° clockwise.
3. Rotating Matrix by 90° counter clockwise.
4. Checking if Matrix is symmetric or not. If yes, print “yes”, otherwise, print “no”.

Hint:

• Symmetric

A matrix A = (a_ij) is symmetric if its entries are symmetric with respect to the main diagonal, that is, a_ij = a_ji, for all indices i and j.

The following 3 x 3 matrix is symmetric:

1 7 3

7 4 -5

3 -5 6

Input

The first line contains an integer N (2<=N<=50), which means the size of the matrix. The total number of elements in the matrix is thus N x N.

For the next N lines, each line contains N integers, specifying the elements of the matrix.

The last line has two integers, which mean two row indices for performing row exchange.

All of the integers in the same line are separated by a space.

Output

Print out the corresponding results with a new line character at the end of each result.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11414.cpp

Partial Judge Header

11414.h

Tags

Discuss

Description

Warning: You are not allowed to use:

1. any static variables

2. any variables which is not inside a function

3. malloc and free

The storage of the vector is handled automatically, being expanded and contracted as needed. Vectors usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a vector does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted.

REQUIREMENTS:

Implement the push_back(), pop_back(), reserve() and destructor member functions of Vector classes.

Note:

If the value of size is equal to the value of capacity, and you need to change the value of capacity (reallocate memory) when you push_back a new element. The rule of increasing capacity is: new capacity = max(old capacity + 1, old capacity * 3).

The constructor of vector will not create an array (which means size and capacity is 0).

Input

here are five kinds of commands:

• pop_back: removes the last element
• push_back: adds an element to the end
• capacity: returns the number of elements that can be held in currently allocated storage
• size: returns the number of elements
• reserve: reserves storage (Increase the capacity of the container to a value that's equal to new capacity. If new capacity is greater than the current capacity, new storage is allocated, otherwise the method does nothing.)

Each commands is followed by a new line character ('\n').

Output

The output should consist of the current state of the vector.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11420.cpp

Partial Judge Header

11420.h

Tags

Discuss

Description

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

---

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.

---

REQUIREMENTS:

Implement the destructor, insert(), search(), and height() member functions of both the Array_ BST and List_ BST classes.

Input

There are four kinds of commands:

• “I A”: insert a node with int value A(A>0) 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 in Level-order.
• “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 (in both Array and LinkedList method) of each command.

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

But there's already a new line character in the main function, so you don't have to do anything.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11432.cpp

Partial Judge Header

11432.h

Tags

Discuss