Description

Define a class Time that has three data members hour, min, and sec of int type. All data members MUST NOT be declared public. Overload necessary operators to make the following main() work. The I/O format for >> and << follows the standard time format: 11:23:17, which represents 11 o'clock 23 minutes 17 seconds. Do not change main(), otherwise you may lose penalty points!! Submit everything including main().

int main() { //DO NOT CHANGE MAIN
    Time t1, t2(10, 3, 27);
    cout << t1 << endl << t2 << endl;
    cin >> t1;
    cout << t1 << endl;
    return 0;
}

Input

5:23:30

Output

0:0:0
10:3:27
5:23:30

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The idea of quicksort is taking one element (called the pivot) from an array and compare it with all other elements to divide them into two groups: (1) smaller than (or equal to) the pivot and (2) bigger than the pivot. Here is an example.

If we take 37 as the pivot, then we can divide this array into two groups: {23, 7, 10, 10, 2} and {93, 82, 49, 55, 70}. We then rearrange the array as follows.

Now {23, 7, 10, 2} and {93, 82, 49, 55, 70} are arrays of smaller size to be sorted. We can use recursive calls to sort them. Note that the orders within the sets {23, 7, 10, 10, 2} and {93, 82, 49, 55, 70} are unimportant. As long as these two sets are correctly divided, quicksort will work correctly. You can always use the first element in the array as the pivot. However, this is not a requirement since choosing which element to be the pivot does not affect the correctness of quicksort.

The sample code for quicksort is given as follows.

#include <iostream>
using namespace std;
 
int partition(int arr[], int start, int end) {
    int pivot = arr[start];
    int count = 0;
    for (int i = start + 1; i <= end; i++) {
        if (arr[i] <= pivot)
            count++;
    } 
    // Giving pivot element its correct position
    int pivotIndex = start + count;
    swap(arr[pivotIndex], arr[start]); // defined in <iostream>
     
    // Sorting left and right parts of the pivot element
    int i = start, j = end;
    while (i < pivotIndex && j > pivotIndex) {
        while (arr[i] <= pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i < pivotIndex && j > pivotIndex) {
            swap(arr[i++], arr[j--]);
        }
    } 
    return pivotIndex;
}
 
void quickSort(int arr[], int start, int end) {
    // base case
    if (start >= end)
        return;

    // partitioning the array
    int p = partition(arr, start, end);
 
    // Sorting the left part
    quickSort(arr, start, p - 1);
 
    // Sorting the right part
    quickSort(arr, p + 1, end);
}

What you need to do

Modify the given quicksort as a C++ template, and write a main function to test it with the Time class. You need to overload some relational operators (< <= > >= ==) to make it work. You are allowed to modify anything you like.

Input

6
4:20:38 4:26:0 3:49:9 9:34:01 5:13:58 3:49:22

Output

3:49:9 3:49:22 4:20:38 4:26:0 5:13:58 9:34:1

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Define a derived class GlobalTime from Time that includes an int representing the offset of a time zone with respect to the Greenwich Mean Time. For example, Taiwan's time zone is GMT+8, and we store this extra data member +8 in GlobalTime. Overload related operators and implement related member functions to make the following main() work. You can modify the Time class but you cannot declare data members in public section in any class (otherwise you'll lose penalty points.) Do not change main(), otherwise you will lose penalty points, too.

int main() { // DO NOT CHANGE MAIN !!!
    GlobalTime gt1(10, 3, 27, 3), gt2;
    cin >> gt2;
    Time &t1 = gt1;
    t1.output();
    cout << endl;
    Time &t2 = gt2;
    t2.output();
    cout << endl;
    return 0;
}

Input

11:13:7-8

Output

10:3:27+3
11:13:7-8

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given two sequences s1 and s2 (of any type). Find their longest common subsequence(s) (LCS). For example, let s1 = {3, 6, 5, 7, 7, 1, 4, 8} and s2 = {4, 45, 7, 7, 1, 9, 3, 6}. Their LCS is {7, 7, 1} of length 3. Implement this function as a template that works on any class T, and call your function template with int. The I/O format is as follows.

• Input an integer indicating the length of the sequence.
• Each element of a sequence is separated by a whitespace.
• The user first inputs two sequences. Then s/he inputs a mode as follows.
  • If mode is len then your program should only output the length of the LCS.
  • If mode is seq then your program should output all LCSs. If there are more than one, then your program should output them in lexicographic order.

Sample Input1

14
343 5 3 434 1 2 3 4 5 6 7 8 9 10
13
9 2348 32 5 1 2 3 4 5 6 88 9934 0
len

Sample Output1

6

Sample Input2

14
343 5 3 434 1 2 3 4 5 6 7 8 9 10
13
9 2348 32 5 1 2 3 4 5 6 88 9934 0
str

Sample Output2

1 2 3 4 5 6

Sample Input3

10
18 3 1 4 7 7 5 3 9 6
11
8 78 5 3 9 2 9 1 4 7 10
str

Sample Output3

1 4 7
5 3 9

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss