| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10996 | Josephus with Fibonacci number |
|
| 11010 | List class |
|
| 11020 | Binary search trees using polymorphism |
|
| 11021 | Encoding and decoding |
|
| 11410 | Implement a vector 2 |
|
| 11920 | Matrix Chain Multiplication |
|
| 12224 | Doubly Linked List |
|
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
main.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
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.cppPartial Judge Header
10996.hTags
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.cppPartial Judge Header
11010.hTags
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
main.cpp
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.cppPartial Judge Header
11020.hTags
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 ‘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
function.h
function.cpp
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.cppPartial Judge Header
11021.hTags
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
由於實際的code有做其他檢查，因此為了讓各位方便閱讀，請參考簡化版本的function.h與main.cpp（請點連結）
Vectors are sequence containers representing arrays that can change in size.
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.
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
There are seven 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
- insert: inserts elements (If there is no capacity for new elements, the new capacity is max (old capacity + old capacity / 2, old capacity + count of inserting elements).) (If a vector has two elements, inserting three elements at position two means push back three times.)
- 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.)
- resize: changes the number of elements stored (If the value of new size is greater than the value of old size, the value of new elements will be 0. If the value of new size is greater than the value of old capacity, the value of new capacity will be new size.)
Each commands is followed by a new line character ('\n').
Output
Implement Vector (constructor, push_back(), pop_back(), capacity(), size(), reserve(), resize(), insert() and destructor).
Sample Input Download
Sample Output Download
Partial Judge Code
11410.cppPartial Judge Header
11410.hTags
Discuss
Description
**[2018/5/12 02:12 PM] : Sorry for the confusion (get_row, get_col) in the original code! The partial code provided has been improved for clarity and all submissions to this problem has been rejudged! For new submissions, please check out the new partial code! Sincerely apologize for the inconvenience caused!**
There are few Matrix stored in MatrixChain Class , please implement the calc function to get chain multiplication of them.
Your task is to implement the following three functions:
Matrix Matrix::operator*(const Matrix &a) const
Matrix Matrix::operator=(const Matrix &a)
Matrix MatrixChain::calc(int l, int r) const
Definition of Chain Multiplication: Given l, r and an array arr of matrices, calculate the result matrix of arr[l] * arr[l+1] * ... * arr[r-1]
Hint : Σ(A[r][k] * B[k][c]) = C[r][c], where C is a matrix with r rows and c columns.
Input
Input will be done by main.cpp so don't worried about it
int T means T matrices
for T : 0 < T < 11
then T matrices with row , col , and each of elements value
for row , col: 0 < row , col < 11
for value of Matrix elements: 0 < value < 11
Finally, give l, r to get the calc() function's answer.
Output
output will also be done by main.cpp so don't worried about it
it will output the calc function's answer .
Sample Input Download
Sample Output Download
Partial Judge Code
11920.cppPartial Judge Header
11920.hTags
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.