Description

Suppose that you have an infinite number of containers with different sizes, already filled with water. Given another empty container with size N liters, you need to find out all the possible methods to fill this N-liter empty container using the provided smaller containers. Note that, to avoid water wastage, if you choose to use a container, all the water in this container should be poured.

For example, assume that we have containers in 1, 5, and 10 liters. To get the 17 liters of water, all the possible methods are listed below:

1. 1 container of 10 liters, 1 container of 5 liters, and 2 containers of 1 liter.
2. 1 container of 10 liters, 0 containers of 5 liters, and 7 containers of 1 liter.
3. 0 containers of 10 liters, 3 containers of 5 liters, and 2 containers of 1 liter.
4. 0 containers of 10 liters, 2 containers of 5 liters, and 7 containers of 1 liter.
5. 0 containers of 10 liters, 1 container of 5 liters, and 12 containers of 1 liter.
6. 0 containers of 10 liters, 0 containers of 5 liters, and 17 containers of 1 liter.

Note that

1.      This problem involves three files.

• function.h: Function definition of filliing and showResult.
• function.c: Function describe of filling and showResult.
• main.c: A driver program to test your implementation.

You will be provided with main.c and function.h, and asked to implement function.cpp.

2.     For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose C compiler) 

       Step 2. Check the results and debug your program if necessary.

function.h

main.c

 Hint 

You can use the following incomplete code of function.c to solve this problem.

function.c

Input

The input contains three lines.

The first line contains an integer M (0<M<=5) which represents the number of different size containers.

The second line contains M numbers, S1 ,S2 , …, SM. Si represents the size of the i-th container. Note that these M numbers are in decreasing order.

The third line contains an integer N (0<M<100) which represents the size of the empty container.

Output

Display all the possible methods to fill the empty container. Each line represents a method in the format “(C1,C2,…,CM)”, where Ci represents the number of the size Si container.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Given a set of n≧1 elements, the problem is to print all possible permutations of this set. For example, if the set is (1,2,3), then the set of permutations is {(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,2,1), (3,1,2)}.

<Hint1>

Looking at the case of four elements (1,2,3,4). The answer can be constructed by writing

1. ‘1’ followed by all the permutations of (2,3,4)
2. ‘2’ followed by all the permutations of (1,3,4)
3. ‘3’ followed by all the permutations of (1,2,4)
4. ‘4’ followed by all the permutations of (1,2,3)

<Hint2>

A recursive method to implement the above idea is as follows:

Consider the case of (1,2,3,4), that is, n=4.

1. Place the set elements in a global array, and set the position index “k” as 0.
2. Use a for-loop to “swap” (or exchange) the 1^st element with the 1^st element, the 2^nd element, the 3^rd element, and the 4^th element, respectively.
   • In each loop-iteration:
     1. increment the position index “k” by 1 (for considering only the remaining elements in the following recursive call);
     2. use the updated k to recursively call your permutation function;
     3. note that because you use a global array, remember to swap back the two elements after the iteration.
3. In a recursive-call path, when k reaches n, it means that you get a possible permutation.

Note that

1.      This problem involves three files.

• function.h: Function definition of show, Swap and Perm.
• function.c: Function describe of show, Swap and Perm.
• main.c: A driver program to test your implementation.

You will be provided with main.c and function.h, and asked to implement function.c.

2.     For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose c compiler) 

       Step 2. Check the results and debug your program if necessary.

function.h

#ifndef FUNCTION_H #define FUNCTION_H void show(int n); void Swap(int k, int i); void Perm(int k, int n); char list[10]; #endif

main.c

#include <stdio.h> #include "function.h" int main(void) { int num, i; scanf("%d",&num); for(i=0; i<num; i++) list[i]='1'+i; Perm(0,num); return 0; }

function.c

#include <stdio.h> ​#include "function.h" void show(int n) { int i; printf("(%c", list[0]); for (i=1; i<n; i++) { printf(",%c", list[i]); } printf(")\n"); } void Swap(int k, int i) { /*your code*/ } void Perm(int k, int n) { /*your code*/ }

Input

The decimal number n that represents the number of elements in the set.

(1≦n≦5)

Output

In the output you should print all the permutations.

Be sure to add a newline character '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

There are N integer pointers, indexed from 0 to N-1 (N<100). Each pointer initially points to an integer of value 0.

There are two kinds of instructions.
The instruction “S n k” is used to set the integer, which pointer n points to, to be k. For example, Set 1 10 means that the integer that pointer 1 points to is set to 10.
And the instruction “E n m” means that pointer n and pointer m exchange the positions that they point to.

For example, pointer 1 points to 5 and pointer 2 points to 7. “E 1 2” means that pointer 1 points to pointer 2 points to and at the same time pointer 2 points to the pointer 1 points to. After “E 1 2”, pointer 1 points to 7 and pointer 2 points to 5.

Note that you don't have to change all the pointers if one pointer changes its target. The following table is an example.

Finally, output all the values that pointers 0 to N-1 point to in order.

Note that

1.      This problem involves three files.

• function.h: Function definition of execInstruct.
• function.c: Function describe of execInstruct.
• main.c: A driver program to test your implementation.

You will be provided with main.c and function.h, and asked to implement function.c.

2.     For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose c compiler) 

       Step 2. Check the results and debug your program if necessary.

main.c

#include <stdio.h>
#include "function.h"

#define SIZE 100

int main() {
        int *ptrArr[SIZE];
        int dataArr[SIZE] = {0};
        char inst;
        int dataNum, instNum;
        int param1, param2;
        int i;

        /* input */
        scanf("%d %d", &dataNum, &instNum);

        /* initialize the ptrArr */
        for (i = 0; i < dataNum; i++)
                ptrArr[i] = &dataArr[i];

        for (i = 0; i < instNum; i++) {
                scanf(" %c %d %d", &inst, &param1, &param2);

                execInst(ptrArr, inst, param1, param2);
        }

        /* output */
        for (i = 0; i < dataNum - 1; i++) {
                printf("%d ", *ptrArr[i]);
        }
        printf("%d", *ptrArr[i]);

        return 0;
}

function.h

#ifndef FUNCTION_H
#define FUNCTION_H
void execInst(int *ptrArr[], char inst, int param1, int param2);
#endif

Input

The first line contains two positive X and Y. X indicates the number of parameters. Y indicates that there are Y instructions needed to be done.

The next Y lines contain the instructions.

Output

All the values that pointers 0 to pointer N-1 point to in order. Each value is seperated by a blank ' '.

# Note that there is no '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Given a link list structure named Node.

typedef struct _Node {

    int data;

    struct _Node *next;

} Node;

Use this structure to implement a increasing integer link list.

You will be provided with main.c and function.h, and asked to implement function.c.

For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose c compiler) 

       Step 2. Check the results and debug your program if necessary.

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" void printList(Node *head); void freeList(Node*); int main() { Node *head = NULL; Node *temp; int data; while(1){ scanf("%d", &data); if (data >= 0) { insert_increase_list(&head, data); } else break; } printList(head); freeList(head); return 0; } void freeList(Node *head) { Node *temp; for(temp=head; temp!=NULL; temp=head) { head = head->next; free(temp); } } void printList(Node *head) { Node *temp; for(temp = head; temp!=NULL; temp=temp->next) { printf("%d ", temp->data); } printf("\n"); }

function.h

#include <stdio.h> #include <stdlib.h> typedef struct _Node { int data; struct _Node *next; } Node; void insert_increase_list(Node**, int);

Input

A non negative integer data per rows, if input is smaller then 0 then exit the while loop and exit the program.

Output

Please follow the output of program

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

According to Wikipedia,  the definition of rectangle is as follows: "In Euclidean plane geometry, a rectangle is a quadrilateral(四邊形) with four right angles(直角). It can also be defined as an equiangular quadrilateral, since equiangular means that all of its angles are equal (360°/4 = 90°)."

In this problem, you are asked to calculate the number of rectangle pairs that intersect to each other among a set of given rectangles.  All rectangles are located in a 2-dimensional euclidean space(二維空間), and all their edges are parallel to either the X- or the Y-axis.

Input

The first line contains one number N, where 2 <= N <= 128, standing for the number of given rectangles.

Each of the following N lines describes a rectangle and has 4 integers separated by space, representing

1. the x coordinate of the bottom-left vertex
2. the y coordinate of the bottom-left vertex
3. the width (the length of the edge that is parallel to the x-axis), positive
4. the height (the length of the edge that is parallel to the y-axis), positive

 Notice that each of the 4 numbers is representable by an int type in C language.

Output

The output should contain only one number, representing the number of rectangle pairs that intersect to each other.

Notice that if the area of overlapping part is zero, then the pair should NOT count.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

As described in Wikipedia, Pascal's triangle is a triangular array of the binomial coefficients. The element k on row n of Pascal’s triangle can be calculated by the following relation:
C(n, 1) = 1, for n = 1, 2, …
C(n, n) = 1, for n = 1, 2, …
C(n, k) = C(n-1, k-1) + C(n-1, k),  for k = 2, 3, … and for n = 2, 3, …

Given a nonnegative integer M, display the Pascal’s triangle from row 1 to row M.
Use '%10d' to print each element. Print a newline '\n ' at the end of each row.

(Note that the sample output print only 1 blank within each element, which is wrong. You should use '%10d'.)

Input

A positive integer M (1<=M<=30)

Output

Print the Pascal triangle from level 1 to level M.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an article as input. You have to count the number of each word, and prints the list of words in alphabetical order.

An article is made of paragraphs and words. In this problem, Word Count refers to an useful tool that counts the numbers of appearances of different words in an article. In this problem, we have provide a function that parse the input article and fetch each word. Slightly different from other partial judge you have seem before, your submission should have a main function and all memory you need, and include the "function.h" to use our fetch_word() function. Function fetch_word() is define as following:

    const char *fetch_word() ;

Each time you call this function, it returns a const pointer which points to the address of a word, and make sure the end of the returned word is ended by character '\0'. Typically, you have to copy characters from the returning value of fetch_word() to your 2D array (or other memory layout) if necessary, and increase the counter for the specific word. If there is no more words in a article, the function returns NULL, and you should start preparing output the results.

Note: If you try to use a pointer to safe the return value, remember to use the const char* type, like "const char* word = fetch_word();".

After you count the numbers of words, you should sort and print all words as a report. The format will be describeb in Output.

Input

Input is an article. Words are splited by blanks (spaces, tab and new line) and some punctuations(標點符號). The whole input contains only one ariticle. There are no more than 100 different words in a ariticle, and no words are longer than 30 characters.

Output

Print the pair <word number> in each line like the sample output, and seperate word and number by a space. All words should be count as all characters is lowercase(英文小寫). Non-alphabetical characters (like numbers and punctuations) just remain the same. You just have to count all words we fetch for you.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

This problem will ask you to do some operations on a list. These operations contains insert, erase, print, remove and show. The position of first node is 0.

Input

The input consist of a number of operations. The first line specifies a non-negative integer N that specifies the number of operations. Each operations (I, E, P, R and S) are separated by a newline character (\n).

I stands for “insert”, following by a non-negative integer (insert position) and a non-negative integer (insert value, 0<=insert value<65536). Insert a node at insert position with insert value.

E stands for “erase”, following by a non-negative integer (start position) and a non-negative integer (end position). End position must be greater than or equal to start position. Erase multiple nodes from start position to end position (excluding end position). If start position is equal to end position, do not erase end position.

If any input positions in the two operations above is greater than or equal to the length of the list, treat the input position as the next position of the last position at the list.

For example, input is

I 0 0

I 1 1

S

Output should be

0 1

P stands for “print”, following by a non-negative integer (print position). Print the value of the node at print position.

If print position is greater than or equal to the length of the list, treat the input position as the last position at the list.  If the
linked list is empty, do not print anything.

R stands for “remove”, following by a non-negative integer (remove value). Remove the nodes in the list with the value that is equal to remove value.

S stands for “show”. Print the value of all nodes in the list. Separate every prints by a whitespace character. If the list is empty, do not print anything.

For example, input is

5

E 1 1

E 1 2

P 2

R 1

S

Output should be nothing.

Output

Print a space after doing P or S operations (if P or S has printed something).

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

In this problem, you are asked to output a sequence of integer number (i.e. 0, 1, 2, 3 ......) in the "spiral form".

A square is an area with NxN grids. You put the first number (i.e. 0) in the position according to the input. Then, you put the next number  to the right (or left) of the previous one, and you will reach the right (or left) border of the square. Any time you can't find an empty place on current direction, you turn "right" (or "left") and place the next number until your direction is opposite to origin direction which you reach this grid.

Sample IO shows four testcases, your input has only four integer and output N*N number.

Input

There are four integer numbers for the input. The first number N (1<= N <= 20) denotes the size of the edges of the square. The second number decides the direction of this case (0 means clockwise, and 1 means anticlockwise). The third and forth number mean the initial position in which row and column.

Output

Print the content in the square. There should be N lines in the output.

If the gird is not reached, the content should be 0. (note: the content of initial position is also 0)

note: print a space before each number, and print '\n' in the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Please implement insertion sort algorithm to sort a sequence of number in ascending order, and show the sequence of number after each insert phase.

insertion sort (wiki): https://en.wikipedia.org/wiki/Insertion_sort

Input

There are 2 lines input.

The first line contains a integer n, indicating the total number of integers would be sorted. (n <= 1000)

The second line consists of the integers being sorted.

Output

Show the sequence of number after each insert phase.

If the input has n numbers, the output would have n-1 lines.

note: print a space before each number, and print '\n' in the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss