Description

In this problem, you are asked to design two functions
    1.

unsigned*** new_3d_array(unsigned n,unsigned m,unsigned k);

malloc an n*m*k 3D unsigned array, and then return its address. The main function will check the correctness of your array.

    2.

void delete_3d_array(unsigned ***arr);

Free the memory space of your array that was previously allocated by using malloc. Be careful about the memory uage of your program allocated dynamically so as to avoid MLE.

The two functions have been declared in function.h, and you are asked to complete the function definitions in function.c.

Your program should construct the 3D array by using only three malloc function calls. Notice that malloc is a time-consuming operation.

Note: 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.

Input

Please refer to the main function.

The input only has one line, consisting of five positive integers t,n,m,k,r separated by space characters, where t is the number of tests, (n,m,k) represents the array size, and r is a parameter for testing. 

Note that n*m*k<=10000000 and t*n*m*k<=60000000

Output

In order to test your array's correctness, we will use your array to do some computations and output the results.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Input

The first line contains a string s, which consists of only lowercase Latin characters. The second line contains a integer Q. The next Q lines, each contains two characters A and B.

Output

Print the resulting string in one line after applying the Q operations.

(remember to print a new line character)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Today, as usual, the cookie monster is picking the cookies to eat for this meal. He is so tired and unable to select the cookies he wants since he was busy preparing for his midterm and didn’t sleep last night. As his good friend, you decided to help him so he doesn’t need to worry about his lunch.

There are n cookies in the shop. For each cookie, there is a number di, representing how yummy the ith cookie is. In general, the larger di is, the more delicious the ith cookie is. However, due to some unknown reasons, the cookie monster especially loves cookies that contain the digit 7 in their di. For example, the digit ‘7’ appears twice in 7927 and appears once in 70. If there are more digits ‘7’ appearing in di for a cookie, the cookie monster would tend to choose that cookie first.

Moreover, here’s your cookie-choosing strategy:

• For any two cookies, always choose the one that with more ‘7’ appears in di first.
• If there are two cookies containing the same amount of ‘7’ in their di, choose the one with larger di.

However, the number di does not directly be marked on the wrapper of the cookie. Instead, there is a string si printed on each wrapper, specifying the value of di. The format of si would be like this:
t1|t2|...|tm, where ti is a number shown in hexadecimal.
And the value of di is the concatenate of all decimal notations of ti, for i = 1, 2, …, m. For example, if si = 2C|4|A, then di = 44410.

Now the cookie monster wants to choose k cookies at most for this meal, help him choose the cookies he is going to eat.

Input

The first line contains two integers n, k, representing the number of cookies in the shop and the amount cookies you are going to choose, respectively.
The next n lines each contains a string, The 1+ith line specifies the value of si.

Constraints:
1 ≤ n ≤ 1000
1 ≤ di ≤ 10³⁰⁰
1 ≤ k ≤ n
1 ≤ ti ≤ 7FFFFFFF16 (= 214748364710)
1 ≤ |si| ≤ 250

Output

Output k lines, the value of di for each cookie you choose, in the order that the smaller value prints first.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Just before the deadline for Doraemon to submit his final project to the eeclass system, another power outage occurred, causing him to lose all of his homework files. It seems that fate has determined that Doraemon will have to retake the course next year...

Fortunately, the government is making efforts to assist Doraemon's university in addressing this power issue by establishing a new electrical substation! The electrical grid for the campus consists of n-1 cables connecting all of the n locations, ensuring that any two locations can be connected. (This structure is also known as a tree, you can refer to the link for more detail.) 

The campus will be divided into different areas based on the location of the electrical substation after its construction. To maintain a balanced distribution of locations in each area and ensure a stable power supply, the goal is to identify the optimal location for the electrical substation where the maximum number of locations in each area is minimized.

The graph above represents the layout of the electrical grid for the campus. Each circle represents a location, and each line connecting the locations represents a power cable with a distance of 1 unit. The blue numbers next to the circles indicate the index number of each location, and the English letter inside each circle represents the area split by the substation.

If we establish the substation at location index number 9 (left graph), we have:
Area A: 3 locations, Area B: 2 locations, Area C: 3 locations, Area D: 4 locations, Area E: 3 locations => max(3, 2, 3, 4, 3) = 4

If we establish the substation at location index number 10 (right graph), we have:
Area A: 12 locations, Area B: 2 locations, Area C: 1 location => max(12, 2, 1) = 12

Therefore, it seems that establishing the electrical substation at location No. 9 might be better than location No. 10.

Template

#include <stdio.h>
#include <stdlib.h>
#define N 100001

int cable[N][2], neighborCount[N], *neighbor[N];
int n;

void readGraph() {
    scanf("%d", &n);
    for (int i=0; i<n-1; i++) {
        scanf("%d %d", &cable[i][0], &cable[i][1]);
        neighborCount[cable[i][0]]++;
        neighborCount[cable[i][1]]++;
    }
    for (int i=1; i<=n; i++) {
        neighbor[i] = (int*)malloc(neighborCount[i] * sizeof(int));
    }
    int neighborIndex[N] = {};
    for (int i=0; i<n-1; i++) {
        int u = cable[i][0], v = cable[i][1];
        neighbor[u][neighborIndex[u]++] = v;
        neighbor[v][neighborIndex[v]++] = u;
    }
}

int main() {
    readGraph();
    // Test the following code
    /*
    for (int i=1; i<=n; i++) {
        int neighborCnt = neighborCount[i];
        printf("%d connects to ", i);
        for (int j=0; j<neighborCnt; j++) {
            printf("%d ", neighbor[i][j]);
        }
        printf("\n");
    }
     */
    return 0;
}

Utilizing the provided readGraph() function can help in managing the preprocess of the given graph:

• neighborCount[i] stores the number of neighbors for the i-th location.
• neighbor[i] is a dynamic array with a size equal to neighborCount[i], and it stores the index number of neighbors for the i-th location.

Try uncommenting the code in the main() function to see how it works.

Input

The first line contain one positive integer n (1 ≤ n ≤ 10⁵) - the number of locations in the electrical grid.
Each of the following n-1 lines contains two integers u and v (1 ≤ u, v ≤ n) - a power cable connecting location index numbers u and v. It is guaranteed that the provided graph is a tree.

Output

Output one line contain one integer - the number of the location that is the best choice for establishing the electrical substation.
It's guaranteed that there is only one optimal location.

Sample Input  Download

Sample Output  Download

Tags

Discuss