| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11711 | Dynamic 3D array |
|
| 12458 | Writing APP |
|
| 13369 | Fibonacci Sequence |
|
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
11711.cPartial Judge Header
11711.hTags
Discuss
Description
APP stands for "Another Palindrome Problem".
Given a string str with length n and an integer k, is it possible to transform str to a palindrome(回文) by removing at most k characters?
Explanation of sample io
You are given str = "fadicaf" and you can remove 3 characters at most. In this case you can remove 'd', 'i', and get "facaf", which is a palindrome. Therefore please output "Yes". Note that there may be multiple ways to transform str to a palindrome.
Maybe useless hints
Maybe useful hints
Draw the recursion tree, and then observe how many recursive function calls with same arguments are re-calculated. Is it possible to store the result of each recursive function call once it is calculated? If so, is it possible to use the results you have stored instead of re-calculate?
Input
The first line is two integers n, k, which are string length and max number of characters you can remove.
The second line is a string str.
-
1 <= n <= 1000
-
1 <= k <= 20, for the 1-5 th test case
-
1 <= k <= 1000, for the 6 th test case. Some tricks must be applied to pass this test case.
-
str is of length n, consisting of lower case characters (a-z) only
Output
Output "Yes" (without quotation mark) in a line if str can be transformed to a palindrome by removing at most k characters, otherwise output "No" (without quotation mark) in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In this problem, you are asked to help us develop a method to compute the n-th term, Fn, of the fibonacci sequence. The fibonacci sequence is a recursive sequence defined as Fi=Fi-1+Fi-2, where we let F0=0, F1=1 in this problem. This recursive relation can be written as a matrix multiplication:
and this is the general form of Fn and Fn+1:
This problem is a partial judge problem. You are asked to design a function to calculate (Ab % m) where A is a 2x2 matrix and b,m are integers. Then, using your function and the matrix equation above, we are able to compute our desired Fn of the fibonacci sequence. For the details, please check the main() function carefully.
The power computation for integers ...
Given integers a, b and m, calculating the answer of (ab % m) may be trivial for you because it can be solved by using a single for loop:
, or a recursive way:
if (b == 0) return 1;
return a * pow(a, b-1);
}
However, this isn't the best way to do so since its time complexity is O(b). In other words, it requires b times of steps, so it may not be able to finish the task in a second if b is large (e.g. b <= 1018).
Therefore, we have another better algorithm to achieve it. Define a function P(a,b)=ab. For P(a,b), we don't need the answer of P(a, b-1). Instead, we are interested in the answer of P(a, b/2). To explain why, we discuss in two cases of P(a,b):
- b is even: ab = ab/2 * ab/2
- b is odd: ab = ab/2 * ab/2 * a
The code below is a demonstration of this simple algorithm.
if (b==0) return 1;
int t = pow1(a, b/2);
if (b%2 == 0) t = t * t % m;
else t = t * t % m * a % m;
return t;
}
Next, we want to analyze the time complexity, or, the steps required to solve this problem. Since pow(a,b) will only call the function pow(a,b/2) once, there're log2(b) of steps. Therefore, the time complexity is O(log(b)), which is much more efficient than the original method O(b).
Note that the following implementation can give the right answer, but the time complexity is still O(b). It is recommended to figure the reason out with your thoughts.
if (b==0) return 1;
if (b%2 == 0) return pow2(a, b/2) * pow2(a, b/2) % m;
else return pow2(a, b/2) * pow2(a, b/2) % m * a % m;
}
In this problem ...
In this problem, for us to compute Fn of the fibonacci sequence, you are asked to design a function to calculate (Ab % m) where A is a 2x2 matrix and b,m are integers.
This function has the following prototype, as declared in function.h:
}
- Note 1: The 2x2 matrix A is represented as a 1-D long long int array of length 4, which is in the following format:
.
- Note 2: Please malloc a 1-D long long int array of length 4 in matrix_pow() to store the computed (Ab % m), and return the address of this malloced dynamic array as the function's return value.
- Note 3:
A0=
, the 2x2 identity matrix.
- Note 4: You can consider to define/implement other function(s) in your function.c to help complete the design of your matrix_pow(), if you feel necessary.
Input
The input only consists of two integers n and m, where 0 <= n <= 1018, 0 < m <=2*109.
Output
Output Fn % m in a single line.