Description

Given a link list structure named Node.

typedef struct _Node {

    int data;

    struct _Node *next;

} Node;

Given a list, rotate the list to the left by k places, where k is non-negative and k is smaller than the count of nodes in linked list.

For example: 
Given 1->2->3->4->5->NULL and k = 3, 
return 4->5->1->2->3->NULL.

Input

The input contains 2 sequence of positive integers.The first sequence is to create a linked list of integers, except the last one, which is -1, indicating the end of the sequence. The second line is an integer k. 

Output

The output contains the sequence of resulting linklist.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

An example of a multivariable linear inequality is like

where the ai's are coefficients, the xi's are unknowns, and the operation can be "less than(<)", "greater than(>)", or "greater than or equal to."

This problem ask you to list all the solutions of a specific kind of multivariable Linear Inequality, where all the unknowns are non-negative integers, all coefficients are 1, and it has constraints at both side.  A mathematical representation is like:

Input

Three numbers in a line, L, U, and n.

• L is the exclusive lower bound.
• U is the inclusive upper bound, is always larger than L, and less than 20.
• n is the total number of unknowns, which is less than 20.

In other words, they are all the parameters we need to calculate the solution of the following inequality.

Output

The output should be all the solutions listed in ascending order.  See the definition and example output below.

Solution
A solution is a set of non-negative numbers separated by space and ended with a newline(\n).

Ascending order
For any solution S1(x1, x2, ...) and the solution S2(y1, y2, ...) next to it,

If they share the same prefix of numbers,

then the first number not in the common prefix in S2 MUST larger than that in S1.

Otherwise,

 

Appendix: Properties and Facts

The total number of solutions of the multivariable integer linear inequality

is

since it is the number of combinations with repetition(重複組合).

So you can verify if the number of lines of your output, which is the number of solutions,  is 

because the solution set of 

is the difference set of

and

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Determinant is a value computed from all the elements of a square matrix.  A determinant of an N-by-N matrix can be recursively computed from N determinant (N-1)-by(N-1) sub-matrices (minors).  You may check the examples below (from Wikipedia):

4-by-4 example:

3-by-3 example:

2-by-2 example:

In other words, you may calculate the determinant value by expanding the original determinant along the first row, multiplying each element by its corresponding minor,  multiplying each product by the elements in the alternating series 1, -1, 1, -1, ... accordingly, and then summing up all the products.

For more details you may check:

https://en.wikipedia.org/wiki/Determinant#n_.C3.97_n_matrices
or
https://people.richland.edu/james/lecture/m116/matrices/determinant.html

Input

The first line contains an integer n (2 <= n <= 8), specifying the size of the square matrix A. Then following next n lines, each line containing n integers, define the entries of the matrix A. The range of values in the entries is from -4 to 4.

Output

For each case, output one line with the determinant of matrix A.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A matrix is a two-dimensional object, but the memory is one-dimensional.  Also, the ways to allocate memory are very different from each other, e.g. malloc v.s. static declaration.  Thus, how to store a matrix in the memory and how to allocate required memory are important issues.  

In this exercise, you will learn how to store and manipulate given matrices in different types of variables.  The memory format of interests are basically the following,

1. Static two-dimensional array
   char STDA[MAXROW][MAXCOL];
2. Dynamic two-dimensional array - type 1
   char (*DTDA1)[MAXCOL];
   This is a pointer to a character array which has length MAXCOL
3. Dynamic two-dimensional array - type 2
   char *DTDA2[MAXROW];
   This is an array of pointers to characters
4. Dynamic two-dimensional array - type 3
   char **DTDA3;
   This is a pointer to a pointer to a character

The Basic Flow of This Program

NOTE: This is a partial judge problem, so you should finish the unimplemented functions.  Please read the given source and header carefully.

1. get the dimension of the matrix (provided)

   1. if the given dimension is 0-by-0, see the final section "Special Input." Answer the questions and return.  These questions help you construct the concept of pointers and their usage.  It is recommended that you finish the general part first and then do this part. (you have to implement it)

2. allocate memory for the three different types of dynamic formats (one provided; you have to implement the rest two)

3. read the input matrix into type-3 variable, DTDA3, for the matrix (you have to implement it)

4. do a flip upside-down(上下顛倒) operation on DTDA3 and store the result to DTDA2 (you have to implement it)

   1. print DTDA2 (you have to implement it)

   2. print a split line (provided)

5. do a flip left-right(左右翻轉) operation on DTDA2 and store the result to DTDA1 (you have to implement it)

   1. print DTDA1 (you have to implement it)

   2. print a split line (provided)

6. do a rotation operation of 180 degrees on DTDA1 and store the result to STDA (you have to implement it)

7. free the three dynamic variables (all provided)

8. print STDA (provided)

Input

The input contains all the information you need, a.k.a dimension and data, to store a complete matrix.

The first line has two positive integers that are less than 10 and separated by a space.  They represent nrow, the number of rows and ncol, the number of columns.

The following nrow lines contain the data, ncol characters per line, with one newline('\n') character at the end of each line.  The characters are alphabets(A-Z, a-z), numbers(0-9), and punctuations(,./?[}...).

Testcase Generator (You don't need this in your code)

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<ctype.h>

int main(int argc, char *argv[]){
        if(argc != 3)
                return -1; 

        srand(time(NULL));
        int nrow = atoi(argv[1]);
        int ncol = atoi(argv[2]);
        printf("%d %d\n", nrow, ncol);

        for(int i = 0; i < nrow; i++){
                for(int j = 0; j < ncol; j++){
                        char ch; 
                        ch = rand()%128;
                        do{ 
                                ch = rand()%128;
                        }while(!isalnum(ch) && !ispunct(ch));
                        putchar(ch);
                }   
                putchar('\n');
        }
}

In order to use this program, you should first build it into an executable gen.exe, and then run it in the command line prompt(終端機命令列) with the nrow and ncol you want to test.  For example:

C:\Document and Settings\Users\ABC> gen.exe 3 5

or you can directly generate an input testcase file using redirection:

C:\Document and Settings\Users\ABC> gen.exe 3 5 > input.txt

Output

The program should output totally three matrices separated by split lines (see example).  All the three matrices are in the same format as the input matrix: nrow lines and ncol characters plus one newline at the end per line.  The split line is ncol '=' characters and a newline at the end of it.  The final output should be the same character matrix as the input one.

Special Input

There will be one special test case, which gives you only the first line: 0 and 0.  In this case, you have to answer the following multiple-choice and yes-or-no questions.  Assuming nrow = 3 and ncol = 5 in all the questions.

For multiple-choice questions, you should output ONLY the number of the option and then a newline character, there will be only one answer among all the choices.

For yes-or-no questions, you should output "yes" or "no" following by a newline.

1. How many bytes does malloc() allocate in the function alloc_DTDA1()?
   1. 15
   2. 48
   3. 80
   4. 256
2. How many times should the malloc() be called in the function alloc_DTDA2()?
   1. 3
   2. 5
   3. 15
   4. 16
3. How many times should the malloc() be called in the function alloc_DTDA3()?
   1. 3
   2. 4
   3. 5
   4. 6
4. The number that malloc() is called in alloc_DTDA3 shoule be the same as the number that free() is called in free_DTDA3.
5. The function flipUD_DTDA3_to_DTDA2 can be applied not only from DTDA3 to DTDA2, but also from DTDA2 to DTDA3. (Hint for 5~7, just try to compile & run it!)
6. The function flipLR_DTDA2_to_DTDA1 can be applied not only from DTDA2 to DTDA1, but also from DTDA1 to DTDA2.
7. The function rotate180_DTDA1_to_STDA can be applied not only from DTDA1 to STDA, but also from STDA to DTDA1.
8. If one change the prototype from "void show_DTDA2(char *DTDA2[MAXROW], int nrow, int ncol)" to "void show_DTDA2(char *DTDA2[], int nrow, int ncol)" in function.h, the original implementation of show_DTDA2 does NOT work.(Hint for 8~10, just try it! And notice that in English you should say "yes, it works" or "no, it doesn't work")
9. If one change the prototype from "void show_DTDA2(char *DTDA2[MAXROW], int nrow, int ncol)" to "void show_DTDA2(char **DTDA2, int nrow, int ncol)" in function.h, the original implementation of show_DTDA2 does NOT work.
10. If one change the prototype from "void show_DTDA1(char (**pDTDA1)[MAXCOL], int nrow, int ncol)" to "void show_DTDA1(char (**pDTDA1)[10], int nrow, int ncol)" in function.h, the original implementation of show_DTDA1 does NOT work.
11. There are 15 elements in the given 3-by-5 matrix.  Which variable holds all the elements in a continues area?
    1. STDA
    2. DTDA1
    3. DTDA2
    4. DTDA3
    5. all of them
    6. none of them
12. Assume that the given matrix is of dimension MAXROW-by-MAXCOL.  Which variable holds all the elements in a continues area?
    1. STDA and DTDA1
    2. DTDA2 and DTDA3
    3. both of them
    4. none of them

Notice that you should provide the output of exactly 12 lines to the special case. 

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

This problem will give you a sequence of positive integers.  Use this sequence to create a linked list to store those integers.  Next, the problem will give you another sequence of positive integers, p0, p1,…pk-1.  Delete the nodes that the data is equal to one of p0, p1, …pk-1 of the linked list. If the node is not existing,do nothing.  And show the final results.

The framework of the program is provided.

1. Create a linked list from the input  (createList)
2. while there are still some data pi
3. read in pi
4. delete node that data is equal to pi  (deleteNode)
5. print the remaining list (printList)
6. free the list (freeList)

You will be provided with main.c and function.h. main.c contains the implementation of function printList, and freeList, and function.h contains the definition of node and the interface of createList() and deleteNode(&head, pi).  You only need to implement createList() and deleteNode(&head, pi) in function.c, in which head is the head of the linked list, and pi is the data of the node to be deleted.

For OJ submission, you only need to submit your createList and deleteNode implementation to the submission block. (Choose c compiler) 

Input

The input contains 2 sequences of positive integers.  The first sequence is to create a linked list of integers, and the second sequence is the nodes to be deleted.  Each sequence is ended by -1. 

Output

The output contains the sequence of resulting linklist.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Caesar's cipher is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after Julius Caesar, who used it in his private correspondence.

The cipher illustrated here uses a left shift of 3,
so that each occurrence of E in the plaintext becomes B in the ciphertext.
(https://en.wikipedia.org/wiki/Caesar_cipher)

But a problem of the Caesar's cipher is that in most case, the occurrence each alphabet has its frequency, and some of them are significantly higher than others' in an article. For example, the letter 'E' appears much more than other letters, and the frequency is typically more than 12%. Then there are less 'A' and 'T', which may be 8%. If the frequency of the letters in an article is analysised, one may easily break the Caesar's cipher.

In this problem, you are given an article in ciphertext in each test case. You have to find the most frequent letter in the ariticle, and restore the ariticle from the ciphertext to its plaintext.

Hint:

1. You may have to store the ciphertext lines you get, so you can recover it later.
2. You can use an array int number[128]={0} to count the occurrences of each letter in the ciphertext. There are uppercases as well as lowercases, and they are treated the same.
3. Then you find the most frequent letter. Try to shift and turn it to 'E' or 'e'.
4. Let everything that is not a letter remain the same.
5. In the sample input, you should find 16 'B's in the ciphertext. So you shift 3 to get the plaintext.

Input

The input is a ciphertext.

There are no more than 10 lines in the input, and there are no longer than 100 characters in each line.

Output

Print the plaintext after you break the Caesar's cipher.

Remain all the format (space, newline and non-alphabet characters) the same as the ciphertext.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In this problem, you are given an array, and you are asked to operate several swapings to these elements.

The operation is simple. You will be asked to "Swap N elements in location S and location T". There are several operations, and you have to operate them one by one. In a operation, you may assume that there will not be any overlaps in the ranges from location S and T, and the range will always fit the array size.

Hint:

You may wrote a simple function void swap_array( int *loc_S, int *loc_T, int N ) to do the operation.

Input

There is ony one in case in the test case.

The first line contains an integer M, which is the size of array. M is not larger than 20.

The second line has M integers, which is the original contains of the array. These integers are ranged in [0,99].

The third line contains an integer O, denoting the number of operations. There will be no more than 10 operations.

The following O lines contains 3 integers, N, S and T. You have to swap N integers from location S to location T. S and T are in the range [0,M-1].

Output

Print the final status of the array.

You have to separate elements by spaces in between, and remember to add the newline symbol at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In this problem, we link alphabets into a necklace. For example, imagine a string necklace -F-A-E-D-C-B-G- is made of alphabets {A, B, C, D, E, F, G}, and G is linked to F. In the necklace, each alphabet will appear at most once. Unfortunately, we can only see fractions of the necklace. But we are still lucky enough to put these fractions back to the original necklace.

From the previous example, we can only see the fractions {FAE, BGF, DCB, ED}, and these information is enough to fix the necklace FAEDCBGF. Note that G is also linked to F, that is why we have the fraction BGF.

In this problem, we are given fractions, and we are going to put these fractions together. Any 2 fractions could have only 1 overlap alphabet, and there is exactly one solution for this problem.

Input

The first line on input contains a integer N, denoting the numbers of fractions. There are at least 2 fractions.

The second line is the fitst fraction, and we start to fix the necklace here.

The following N-1 lines contains other fractions. These fractions may be listed out of order.

Each fraction is made of uppercase alphabets 'A'-'Z', and the length is at least 2. Since there will not be any alphabets appear twice in the necklace, N is not greater than 26.

Output

Print the necklace. In our example, print "FAEDCBGF\n" as the answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We assume the final exam assets you by three problems.
Each problem worth 100 points, so there is 300 points in total.
There are n students in this class, and their student ID are counted from 1 to n.
This problem is sort the students according to the following rules.

1. sort them by the sum of scores of all three problems
2. If there are two students which get same order in rule 1, the one with more scores in the first problem would get higher order.
3. If there are two students which get same order in rule 2, the one with less student ID would get higher order.

In this problem, you are asked to implement a function that compares two students.

Input

The first line contains a integer n.
There are n lines following, each contains the score of the three problems.
Line i of the n lines represent the score of student whose ID is i.

Output

Print the order of the students in terms of student ID.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Given n digits from 0 to 9, you are going to combine them into a decimal number.
For example, if 2 and 9 are given, 29 and 92 are valid numbers.
However no valid number could start with 0 except 0 itself.
For example, if 2 and 0 are given, only 20 is valid while 02 is not.

This problem ask you to find a minimum number that is valid.
Noted that all digits must be used.

Input

The first line contains a integer n. (n<=7)
The next line contains n digits.

Output

The minimum number that is valid.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss