Description

We want to write a program to check whether we win the lottery or not.

Input

The first input character indicates the algorithm we want the program to use (students are required to implement three algorithms in a program).
I: iterative
R: recursive
S: STL

A number following the character declares the total number of sets of winning numbers. 
For example, in the sample input, there are three sets of winning numbers. 
This number can be 1 to 999.

Corresponding unsorted winning numbers follow the number.

A number following the winning numbers declares the total number of lotteries we bought. 
For example, In the sample input, there are two sets of our bought lotteries. 
This number is equal to or greater than 1.

Corresponding unsorted lotteries follow the number.

The 28th test case is just the same as the following sample input.

Output

Most of the information from input are repeated, except ...

Winning numbers are sorted, both internal to each set and among the sets.

Our bought lotteries are sorted, only internal to each set. 
We don't need to perform among-set sorting for our lotteris.

Whether we win the lottery (six numbers are the same to a set of winning numbers) is shown.
Y means yes, and N means no. 

Furthermore, please also show which set of winning numbers (after sorting) is matched.  (1-based instead of 0-based)

The 28th test case expects just the same as the following sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We want to write a program to evaluate sparse matrix expressions.  Data structure techniques including Infix to postfix conversion, sparse matrix operations (addition, multiplication, and transposition) and expression evaluation are needed by this program.

Input

The first integer indicates how many sparse matriics are defined (i.e., are assigned values). 
This integer can take value between zero and 26 (including zero and 26).
Please note that this integer is unrelated to the number of distict operands (i.e., matrix names) appeared in the arithmetic expressions that the program needs to handle.

For each defined matrix, firstly, a character (capitalized A~Z) indicates the name of the matrix.
Following the name, the first line comprises three integers indicating the number of rows, columns, and nonzero terms of the matrix, respectively.
For example, a line of "100 20 30" indicates that the matrix has 100 rows, 20 columns, and 30 nonzero terms.
For simplicity, we can assume the dimension is at most 100 * 100.

Next, there are multiple lines corresponding to said number of nonzero terms, each line corresponding to a nonzero term.
For example, a line of "5 3 -4" denotes that the entry with the row index equal to 5 and the column index equl to 3 of the matrix is -4.
Please note that row and column indices are zero-based, and the value of matrix entry is of the (signed) integer type.

After the said number of matrics are defined, an integer describes the number of expressions the program needs to handle.

Next, there are multiple lines, and each line comprises an arithmetic expression. 

Arithmetic expressions can comprise the following components:

Operands:

Captalized character A to Z
Please note that even if the number of sparse matrics defined (the first integer of the inputs) is zero, an arithmetic expression still comprises operands. 
In this case, the program only performs infix to postfix conversion but does not perform expresion evaluation.
As long as the number of sparse matrics defined (the first integer of the inputs) is nonzero, it is guaranteed that in the test cases, all operands in the expressions have their values defined.

Operators:

+ : add
- : subtract
* : multiply
' : transpose

Delimeters:

( : left parenthesis
) : right parenthesis
 
The inputs end here.  The inputs comprise only one group of matrix definitions and expressions as described above.
 

Output

For each expression:
First, the program is required to output the expression using post-fix notatoins.
Second, if the number of defined matrics is not zero, the program is required to evaluate the expression and output the evaluation results.

The format of the evaluation results is the same as the sparse matrix representation used in the inputs:
A line indicates the number of rows, columns, and non-zero terms of the resulting matrix.
For each nonzero terms, a line indicates its row index, column index, and value.

Please note that zero terms are required to be eliminated.
Please also note that there is no space characters at the end of each output line, and the last output line comprises a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We want to implement a templated circular buffer class, circular_buffer<T>, that supports push_back(), pop_front(), size(), and the [] operator.

A circular buffer behaves similar to a circular queue introducted in the Data Struecutre textbook except that a newly inserted element may replace an old element if the buffer is full.  Specifically, if a circular buffer is full, the front element of the buffer is popped before a new element is inserted.

Please use the following partial code to complete this homework.

#include <iostream>

using namespace std;

/* Code for our templated circular buffer class goes here */

int main()
{
    int capacity;
    cin >> capacity;
    circular_buffer<int> cbi(capacity);

    int N;
    cin >> N;
    for(int i=0; i<N; i++){
        string cmd;
        cin >> cmd;
        if(cmd=="push_back"){
            int data;
            cin >> data;
            cbi.push_back(data);
        }else if(cmd=="pop_front"){
            cbi.pop_front();
        }else if(cmd=="print"){
            for(int j=0; j<cbi.size(); j++){
                cout << cbi[j] << endl;
            }
            cout << "----" << endl;
        }
    }
    return 0;
}

Input

Please note that the partial code can handle input and output already.  We do not need to rewrite this part of input/output handling code.  We only need to focus on the circular buffer class.  Input and output format are listed for reference only.

The first input integer indicates the capacity of the capacity of the instantiated circular buffer.

The second input integer indicates the number of commands used to test the buffer.

Commands include

push_back k : insert an interger, k, using the push_back() operator

pop_pront : remove an element, using the pop_front() operator

print : print out all elements in the buffer using the [] operator and a loop.

Output

Please note that the partial code can handle input and output already.  We do not need to rewrite this part of input/output handling code.  We only need to focus on the circular buffer class.  Input and output format are listed for reference only.

Upon a print command all elements in the buffer are printed out, starting at the front and working toward the back.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We want to use KMP Algorithm to perform string matching. 

Please refer to Section 2.6.2 of "Fundamentals of Data Structures in C++, 2nd Edition" by Horowitz et al. for the details about the algorithm.  

Please note that some modifications to algorithm provided by the textbook are required:

1. We need our program to report all matched patterns, instead of only the first one.  This requirement means that our program should appropriately leverage the failure function knowledge to resume the search routine not only after a mismatch but also after each succesful pattern match.   
2. We need our program to show the procedure of the searching algorithm.

Input

The first input integer is the number of string pairs. 

String pairs follow the integer.

Each string pair comprises 1) a pattern string and 2) a content string.  We want to search the content string for the existence of the pattern string.

Output

Our program needs to print 1) the pattern string, 2) the failure function of the pattern string, 3) the content string, 4) the procedure of the searching algorithm, and 5) the number of patterns found in the content string.

The 4) procedure part uses four types of symbos,  '~', '=', 'o', and 'x', to denote four possible situations confronted by the searching algorithm. 

KMP Algorithm uses two pointers to iteratively compare the the pattern string and the content string.
'=' denotes that the two charcters pointed by the two pointers are matched.
'o' denotes that the two charcters pointed by the two pointers not only are matched but also result in a matched pattern.
'x' denotes a mismatch between the two pointers.
'~' denotes a partial-matched character that the failure function table informs the algorithm.

The following figure shows the screenshot of sample output.  In the "Sample Output" section, all the ' ' (space) characters in the sample output are replaced with '.' (period) for the sake of clarity.  Our program should use spaces as delimiters instead of periods.  Usually there are multiple pairs of strings in an input stream.  Our program should use two newline characters to seperate the outputs corresponding to different string pairs.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Please convert a postfix expression to prefix expression.

Each test case contains only one postfix expression.

Input

Each input is a postfix expression.

We use only uppercase English alphabets as the name of variables in the expression,

and use only '+', '-', '*', '/' as possible operators.

The following are examples for our postfix expression:

AB+

AB/CD*+

Output

Each output is a prefix expression with respect to previous postfix expression

For example, if the postfix expression is AB+, the according prefix expression is +AB

Note that each output should not append a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Please convert a prefix expression to postfix expression.

Each test case contains only one postfix expression.

Input

Each input is a prefix expression.

We use only uppercase English alphabets as the name of variables in the expression,

and use only '+', '-', '*', '/' as possible operators.

The following are examples for our prefix expression:

+AB

+/AB*CD

Output

Each output is a postfix expression with respect to previous prefix expression

For example, if the prefix expression is +AB, the according postfix expression is AB+

Note that each output should not append a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We are going to compare two directories in this problem.

Files

All files in this problem are empty files, so all files are identical.

Directories

Directories are containers for files and other directories.

Two directories are considered identical if everything found in one directory exists and is identical to the one with the same name in the other directory.

Input

• positive integer N at the first line
• N lines of path
• positivge integer M
• M lines of path path

paths

• /a and /A are different paths
• the slash / is used in problem as the separator
• paths always starts with a slash /
• if a path ends with a slash /\ , it indicates the last object in the path is a directory, otherwise it is a file.

For example, /a/example/of/path should be intepreted as:

create a directory named "a" in the root directory "/" if it does not exist
create a directory named "example" in "/a/" if it does not exist
create a directory named "of" in "/a/example/" if it does not exist
create a empty file named "path" in "/a/example/of/"

And

a/b/c/d/
a/b/e/f/
a/b/e/g

would give us:

a/
└── b/
    ├── c/
    │   └── d/
    └── e/
        ├── f/
        └── g

Output

M lines, each line contains a character i or d indicating either the two paths' content is identical or different.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We want to write a program to generate mazes using minimum spanning tree methods.  Our maze is a matrix of blocks.  Each block can be a wall or a path.  The ability to generate mazes is the key technique to develop computer games.  We also visualize the maze using text.

Input

The first integer indicates the number of rows of the required maze matrix.  This number is always odd.

The second integer indicates the number of columns of the required maze matrix.  This number is always odd, too.

Next, a string of characters is the pattern we use to represent a wall block.

Next, a string of characters is the pattern we use to represent a path (i.e, non-wall) block.

Next, an integer indicates the number of edges that follow. 

Each edge contains four integers:
the row index of the starting point,
the column index of the starting point,
the row index of the ending point, and
the column index of the ending point.
For example, 5 5 5 7 means an edge from (5, 5) to (5, 7) (which associates with a total of three blocks) in the maze.

These edges are associated to some randomized, distinct edge costs.  The costs are omitted in the imput.  Edges are listed in ascending order of edge costs in the input.   

Output

Our maze is a matrix of blocks.  Each block can be a wall or a path.

We create a maze by constructing the minimum cost spanning tree (MST) rooted at (1, 1) according to the edge cost order.  In the matrix, tree edges are paths, and other places (except the entrance and exit at the first column in the second row and the last column in the second last row) are walls.  MSTs can be obtained using Kruskal's, Prim's, or Sollin's algorithms as described in the textbook.  Since edge costs are assigned distinct and are totally ordered, any algorithm should result in the same MST.  If you have no preferences, the Prim's algorithm could be relatively easier to implement.

Sample Input  Download

Sample Output  Download

Tags

Discuss