Description

Array.cpp
// overloaded assignment operator;
// const return avoids: ( a1 = a2 ) = a3
const Array &Array::operator=( const Array &right )
{
   if ( &right != this ) // avoid self-assignment
   {
      // for Arrays of different sizes, deallocate original
      // left-side Array, then allocate new left-side Array
      if ( size != right.size )
      {
         delete [] ptr; // release space
         size = right.size; // resize this object
         ptr = new int[ size ]; // create space for Array copy
      } // end inner if

      for ( size_t i = 0; i < size; ++i )
         ptr[ i ] = right.ptr[ i ]; // copy array into object
   } // end outer if

   return *this; // enables x = y = z, for example
} // end function operator=

// determine if two Arrays are equal and
// return true, otherwise return false
bool Array::operator==( const Array &right ) const
{
   if ( size != right.size )
      return false; // arrays of different number of elements

   for ( size_t i = 0; i < size; ++i )
      if ( ptr[ i ] != right.ptr[ i ] )
         return false; // Array contents are not equal

   return true; // Arrays are equal
} // end function operator==

// overloaded subscript operator for non-const Arrays;
// reference return creates a modifiable lvalue
int &Array::operator[]( int subscript )
{
   // check for subscript out-of-range error
   if ( subscript < 0 || subscript >= size )
      throw out_of_range( "Subscript out of range" );

   return ptr[ subscript ]; // reference return
} // end function operator[]

// overloaded subscript operator for const Arrays
// const reference return creates an rvalue
int Array::operator[]( int subscript ) const
{
   // check for subscript out-of-range error
   if ( subscript < 0 || subscript >= size )
      throw out_of_range( "Subscript out of range" );

   return ptr[ subscript ]; // returns copy of this element
} // end function operator[]

// overloaded input operator for class Array;
// inputs values for entire Array
istream &operator>>( istream &input, Array &a )
{
   for ( size_t i = 0; i < a.size; ++i )
      input >> a.ptr[ i ];

   return input; // enables cin >> x >> y;
} // end function

// overloaded output operator for class Array
ostream &operator<<( ostream &output, const Array &a )
{
   // output private ptr-based array
   for ( size_t i = 0; i < a.size; ++i )
   {
      output << setw( 12 ) << a.ptr[ i ];

      if ( ( i + 1 ) % 4 == 0 ) // 4 numbers per row of output
         output << endl;
   } // end for

   if ( a.size % 4 != 0 ) // end last line of output
      output << endl;

   return output; // enables cout << x << y;
} // end function operator<<

Polymorphism
  In the base class
  virtual void foo();
  In the derived class
  virtual void foo() override;

Abstract class and pure virtual function
  virtual void foo() =0;

Prefix/postfix operators
  complex &operator++();  // prefix
  complex operator++(int); // postfix

Operator overloading
  Binary operators
  /*1.non-static member function */
     complex operator+ (const complex&);
  /* 2. non-member function */
     friend complex operator* (const
                      complex&, const complex&);
  Unitary operators
  /*1.non-static member function */
      complex operator-();
  /*2. non-member function */
      friend complex operator~(const complex&);

Inheritance
  class A {
  // A is a base class }
  class B: public A {
  // B inherits A.
  // B is a derived class}

Dynamic allocation
  int *ptr = new int;
  delete ptr;
  int *ptr = new int[100];
  delete [] ptr;

String object
  #include<string>
  using namespace std;
  ...
  string str1 = "Hello";
  string str2 = "World";

Standard C++ Library - <string>

Standard C++ Library - <sstream>

For example(1):
stringstream ss{“Hello”};    // constructor
string str = ss.str();    // a = “Hello”

For example(2):
stringstream ss;
ss<<”75”;
ss<<”76”;
int num;
ss>>num;    // num = 7576

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In computer science, Base64 is a binary-to-text encoding method. Here is how Base64 encoding works.
Given a string that contains ASCII characters:

1. First, you need to turn each character to its ASCII number then to its 8-bits binary number,
2. Second, connect all the binary numbers, from the first binary, and replace every 6 bits by its corresponding Base64 character, where such mapping is provided in the Base64 index table below.
3. Last, if the total length of all the binary numbers (in terms of bits) is not a multiple of 6, add zero until the total length is a multiple of 6, and for every 2 zero you add, add a '=' character to your encoded string.

ouo.

The ASCII code table is as follows:

The Base64 index table is as follows: (From WIKI)

Sample Input 1:
Turn the string "Man" to ASCII numbers:
M = 77, a = 97, n = 110.

Turn ASCII numbers to 8-bits binary numbers:
77 = 01001101, 97 = 01100001, 110 = 01101110,
010011 / 010110 / 000101 / 101110

Replace every 6 bits by the corresponding character as the table above:
010011 = T / 010110 = W / 000101 = F / 101110 = u

Base64 encoding of "Man" is "TWFu"

Sample Input 2:
Turn the string "Ma" to ASCII numbers:
M = 77, a = 97.

Turn ASCII numbers to 8-bits binary numbers:
77 = 01001101, 97 = 01100001.
010011 / 010110 / 0001

The length is not a multiple of 6, add zero until it becomes a multiple of 6. So we add 2 zero:
010011 / 010110 / 000100

Replace every 6 bits by the corresponding character as the table above:
010011 = T / 010110 = W / 000100 = E

For every 2 zero you add, add 1 '=' to the Base64 encoding result. So we add 1 '=':
Base64 encoding of "Ma" is "TWE="

Sample Input 3:
Turn the string "M" to ASCII numbers:
M = 77.

Turn ASCII numbers to 8-bits binary numbers:
77 = 01001101.
010011 / 01

The length is not a multiple of 6, add zero until it becomes a multiple of 6. So we add 4 zero:
010011 / 010000

Replace every 6 bits by the corresponding character as the table above:
010011 = T / 010000 = Q

For every 2 zero you add, add 1 '=' to the Base64 encoding result. So we add 2 '=':
Base64 encoding of "M" is "TQ=="

The class inheritance hierarchy of this problem is given below:

class Codec {
protected:
  bool encoded;
  string code_str;
public:
  Codec(string& code_str): code_str(code_str), encoded(false) {}
  virtual void encode() = 0;
  virtual void decode() = 0;
  virtual void print(ostream& os) const = 0;
  virtual bool is_encoded() const = 0;
};

class Base64Codec: public Codec {
private:
  // Given 6-bits binary number, return with the Base64 encode character
  char encodeCharacter(int binaryNumber) const;
public:
  // Inherit from base class
  Base64Codec(string& code_str): Codec(code_str) {}
  // TODO: Encode the code_str
  void encode() override;
  // Decode the code_str
  void decode() override;
  // Print the code_str
  void print(ostream& os) const override;
  // Get code_str status
  bool is_encoded() const override;
};

In this problem, you only need to implement the member function encode() of class Base64Codec.

Note:

1.  We have implemented the encodeCharacter(int binaryNumber) function in class Base64Codec for you, whose details are further explained below:

Given a binaryNumber in decimal, representing a 6-bits binary number, encodeCharacter() returns the corresponding character to Base64 encoding.

Example:
binaryNumber = 19(decimal) = 010011(binary),
encodeCharacter(binaryNumber) returns character 'T'

2. You should choose 'C++11' on submission.

Input

The input contains 1 line: a string S.

The string will only contain characters A~Z, a~z, 0~9, space, comma(',') and period('.')

It is guaranteed that:
1 <= |S| <= 2000

Output

The output contains only 1 line: the Base64 encoding of the given string.

With a new line character after your output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Tim Brown published a game “Rolling Balls”.
In this game, the player’s target is to roll balls with different colors into a moving bag as more as possible. A ball can be represented by its color (r, g, b).

Unfortunately, some unscrupulous players always want to cheat in the game.
Therefore, Tim hires you to make a cheating detection system CDSystem, which monitors and simulates the game progress to figure out any impossible data modification.

Your task is to complete a data structure called MultiSet, which can be implemented using Binary Search Tree as MultiSet_Tree.
In this problem, a MultiSet is used to represent a moving bag, into which balls with different colors can be rolled.

MultiSet

MultiSet is a data structure that supports the following operations:

1. Insert(x): insert an element x into the set
2. Delete(x): remove one element x from the set if there’re some x in the set
3. Search(x): return the amount of x in the set

Example:
The MultiSet MS={a,b,y,y}. Search(a) = 1, Search(y) = 2, Search(x) = 0.
After Insert(x) and Delete(y), MS={a,b,x,y}. Then, Search(y) = 1, Search(x) = 1.

MultiSet_Tree

MultiSet_Tree is MultiSet implemented using Binary Search Tree, where the tree nodes store the elements and their amounts in the set. The Insert and Delete operations of MultiSet_Tree can be further explained as follows:

• Insert(x): 

• Delete(x):

MultiSet_Tree Node Greatness/Smallness: Colors of Balls

In this problem, a MultiSet_Tree node represents a specific ball color (r, g, b).
To implement Binary Search Tree, the greatness/smallness (<, >, ==) between two colors is determined sequentially below:

1. Compare the r values of the two colors.
2. If the r values equal, compare the g values of the two colors.
3. If the g values equal, compare the b values of the two colors.
4. If all the r, g, b values are the same, the two colors are equal.

In this partial judge problem, you have to complete:

1. Color: operators <, >, ==, =, where the assignment operator = is needed when you make/modify MultiSet_Tree Nodes.
2. Node: Constructor, Destructor
3. MultiSet_Tree: Constructor, Destructor, Insert, Delete, Search

More Hints on Case 3 of MultiSet_Tree Delete Operation

Supposing Node x with amount ==1 is to be deleted, three possible sub-cases should be considered:

1. Node x has 2 children: replace x by the Node with the largest key among the keys less than x.
2. Node x has 1 child: replace x by its child Node
3. Node x has no child: replace x by NULL.
   
   

Input

The first line gives the number of test cases T.
Each case consists of one integer N and N lines of operations.

Each operation opi is with one of the following formats:

• "+ r g b": Roll a ball with color (r,g,b) into the bag.
• "- r g b": Take away a ball with color (r,g,b) from the bag. If there’s no such ball, just do nothing.
• "? r g b": Print the number of balls with color (r,g,b).
• "PrintSet": Print all nodes (key, amount, level) of MultiSet_Tree in the level-order traversal, where the key is color (r, g, b).

It’s guaranteed that:

• 1 ≤ T ≤ 200
• 0 ≤ N ≤ 5,000
• 0 ≤ r, g, b ≤ 255
• 1^st testcase = sample input
• 2^nd,3^rd testcases only contain operations “+ r g b” , "? r g b", "PrintSet"
• 4~6^th testcases contain operations “+ r g b”, “? r g b”, "- r g b", "PrintSet"

Output

For each test case, output one line with “Case #x:”, where x is the test case number (starting from 1).
Then print the result of each “? r g b”/“PrintSet” for one line.
Remember '\n' for the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss