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.c

Partial Judge Header

11711.h

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

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 string S of length m. The more times this pattern S appears as a substring within a puzzle, the more he likes it! We'll call the number of occurrences of S the preference level.

 

Please help rearrange these n puzzles (P₁ to P_n) 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 two positive integers n and m.

The following n lines each contain a string P_i.

The last line contains a string S of length m.

Constraints

• 1 <= n <= 1000
• 1 <= | P_i |, m <= 10000
• All strings contain only lowercase English letters.

Subtasks

• testcases 1 ~ 2: n <= 10, | P_i |, m <= 100
• testcases 3 ~ 4: | P_i | <= 200, m <= 100
• testcases 5 ~ 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: 
For testcases 5 ~ 6, please refer to the following polynomial. This technique is called rolling hash, which converts a string into a number within a fixed range, allowing string comparison in O(1) time:

(a₁ * m^n-1 + a₂ * m^n-2 + a₃ * m^n-3 + ... + a_n-1 * m¹ + a_n * m⁰) mod P (m is a small prime number like 37, P is a big prime number like 10⁹ + 7)

more reference:

• Slides
• Wikipedia
• sprout（資訊之芽）
• https://hackmd.io/@Lssh-Algorithm/HJzBUtXmO

 

Sample Input  Download

Sample Output  Download

Discuss