| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11756 | Dynamic 2D array |
|
| 14505 | Arrange Big orange cat's puzzle II |
|
Description
In this problem, you are asked to design two functions
1.
unsigned** new_2d_array(unsigned n,unsigned m);
malloc an n*m 2D unsigned array, and then return its address. The main function will check the correctness of your array.
2.
void delete_2d_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 2D array by using only two 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 four positive integers t,n,m,r separated by space characters, where t is the number of tests, (n,m) represents the array size, and r is a parameter for testing.
Note that n*m<=100000000 and t*n*m<=100000000
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
11756.cPartial Judge Header
11756.hTags
Discuss
Description
Last time you helped Orange Cat complete his puzzles. This time, he wants to arrange these puzzles on his shelf. He has a particular fondness for a specific pattern, represented here by a interger x. The number of substring [l, r] in each string that satisfy the following conditions are defined as the preference levels:
- r = l + m - 1
- (al * km-1 + al+1 * km-2 + ... + ar-1 * k + ar ) mod y = x , ai represents the ASCII code of the i-th character in string a
example: Assuming the ascii code of string a is like this: a = [1, 2, 3, 4, 5], k = 10, m = 4, l = 2, r = 5, y = 1000, the result of the polynomial above is: (2 * 103 + 3 * 102 + 4 * 101 + 5) mod 1000 = (2345) mod 1000 = 345.
When a substring with length m satisfies the above conditions, the preference level increases by 1. In other words, you need to calculate how many substrings with length m in a string satisfy the polynomial conditions above. (For a string "abcdefg", when m = 4, all substrings of length m are: "abcd", "bcde", "cdef", and "defg".)
Please help rearrange these n puzzles (P1 to Pn) by sorting them in descending order based on their preference levels. If two puzzles have the same preference level, maintain their original relative order.
Input
The first line contains five positive integers n, m, k, x, y.
The following n lines each contain a string Pi.
Constraints
- 1 <= n <= 200
- 1 <= | Pi |, m <= 10000
- 1 <= x < y <= 109
- 1 <= k <= 109
- All strings contain only lowercase English letters.
Subtasks
- testcases 1 ~ 2: n <= 10, | Pi |, m <= 100
- testcases 3 ~ 5: | Pi | <= 100, m <= 100
- testcase 6: No additional restrictions.
Output
Output n lines, where the i-th line contains a string representing the puzzle placed in the i-th position.
Please remember to print "\n" at the end, and dont print space (" ") at the end of every line
Hint1:
Please implement string swapping in bubble sort using strcpy to avoid TLE (Time Limit Exceeded).
Hint2:
Please be mindful of overflow.
Hint3:
You can use the following template:
for (int i = 0; i + m - 1 < len; i++) {
int l = i, r = i + m - 1, sum = 0;
for (int j = l; j <= r; j++) {
// do something
}
if (sum == x) {
// do something
}
}