2424 - I2P(I)2021_Hu_Hw8 Scoreboard

Time

2021/11/11 16:00:00 2021/11/22 18:15:00

Clarification

# Problem Asker Description Reply Replier Reply Time For all team

# Problem Pass Rate (passed user / total user)
11711 Dynamic 3D array
12498 Partial Judge Example
13342 Domo to omoD
13345 Domo run!
13346 DomoMaze

11711 - Dynamic 3D array   

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

Tags

Jinkela



Discuss




12498 - Partial Judge Example   

Description

This is the partial judge example (another method for online judge), you are asked to design a function below:

int call_add(int a, int b);

(implement a function to add two pass value togeter)

Note: for OJ partial judge 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.

/* the content below is what you need to copy and submit to oj*/

int call_add(int a, int b){

        return a + b;

}

More information about the different of partial judge and normal judge

Input

Please refer to the main function.

The input only one line, contain two number a and b  (1 < a < 10, 1< b < 10)

Output

Output a + b. 

Sample Input  Download

Sample Output  Download

Partial Judge Code

12498.c

Partial Judge Header

12498.h

Tags




Discuss




13342 - Domo to omoD   

Description

Domo is a brilliant dog. When he gets enough sleep, he will be happy.

 

Unfortunately, he got some problems with his homework this evening. He mistakes 'postfix' as 'prefix', which makes him can't go to sleep until he corrects his homework.

 

Given a prefix expression, please convert it to the postfix expression or Domo will be punished since he didn't finish his homework.

 

Prefix: The operator appears in the expression before the operands. Simply of the form (operator operand1 operand2). 

Postfix: The operator appears in the expression after the operands. Simply of the form (operand1 operand2 operator). 
 

Take an Example: (A+B) * (C-D)

Prefix:   * + A B - C D

Postfix: A B + C D - *

 

This problem is testing your recursion skill, so don't consider if the expression is valid or not (such as divided by zero)

 

Input

The first line contains a prefix expression, in which each element is separated with a blank.

 

It's guaranteed that the number of elements will not exceed 500.

 

Output

Print the corresponding postfix expression from the given prefix expression, and separate each element with a blank.

 

You don't need to print a newline character in this problem, I apologize for any inconvenience.

Remember to print a newline character at the end of each line.

 

Sample Input  Download

Sample Output  Download

Tags




Discuss




13345 - Domo run!   

Description

Domo is a brilliant dog. By the way, he is pretty good at running races.

 

This day, Domo attends another running race. But this race uses a special rule for all participants.

 

The distance each participant needs to run is different, it depends on the permutation of the participant's name and the minimum one in alphabetical order.

 

For example, there's a participant called "cab". Since all the permutations in "cab" in alphabetical order are:

 

 

We need to calculate the distance between the minimum one in alphabetical order and the original name, which is "abc" and "cab" respectively.

 

As a result, the distance "cab" need to run in this competition is 4.

 

Now, given a series of names, please calculate the distance they need to run, so we can know if Domo has a chance to win first place.

 

Hint: If you find it hard to pass test cases 7 and 8, try to find out why recursion takes a lot of time and see if there is a solution without using recursion!

 

Input

The first line contains an integer T - the number of participants in this race.

For the following T lines, each line contains a string S - the name of each participant.

 

The variable range of each test case is different.

For the test case 1 ~ 2, 1 ≤ T ≤ 102, 1 ≤ the length of S ≤ 5.
For the test case 3 ~ 6, 1 ≤ T ≤ 103, 1 ≤ the length of S ≤ 8.
For the test case 7 ~ 8, 1 ≤ T ≤ 104, 1 ≤ the length of S ≤ 15.

 

Note that each participant's name is in lower case, and will not have any repetitive letters. For example, "Domo" is invalid, since the letter 'o' is repeated... Wait, how does Domo attend this competition?

 

Output

Print the distance each participant needs to run one per line.

 

Sample Input  Download

Sample Output  Download

Tags




Discuss




13346 - DomoMaze   

Description

Domo is a brilliant dog. By the way, his grandfather is also a brilliant dog, and he has built a giant maze in the forest years ago, which is called "DomoMaze".

 

One day, Domo loses his ball called Wilson in this maze. He wants to take Wilson back, and your task is to find out how many ways Domo can reach the position where Wilson is.

 

This DomoMaze can be described as a two-dimensional array. With width W and length L, Domo is at the position (0, 0) in the beginning, and Wilson is at the position (W-1, L-1).

 

Each time Domo moves, he can choose one of three ways below:

1. from (i, k) to (i+1, k)
2. from (i, k) to (i, k+1)
3. from (i, k) to (i+1, k+1)

 

Also, there are some portals in the maze. If you step into a certain position (i, k) where has a portal, you will be immediately teleported to the position (i-2, k-2), and the portal you used will disappear

It is guaranteed that the position (i-2, k-2) is in the DomoMaze, and the portal will not appear at (W-1, L-1).

 

Given the size of DomoMaze and the position of all portals, please find out how many ways Domo can find Wilson.

 

Hint: Try to separate the answer to { passing 0 portal, passing 1 portal, passing 2 portals }, and sum all conditions to find the final answer!

 


We introduced a method called Dynamic Programming.

The main idea is to use the answer of sub-problems to find out the answer to the original problem.

 

For example, a DomoMaze is given below:

 

We can calculate how many ways Domo can reach for every position. Obviously, for each position whose index of row or column is 0, there is only 1 way Domo can reach.

 

Next, we can calculate the ways Domo can reach the position (1, 1) with the following equation:

f(1, 1) = f(0, 0) + f(1, 0) + f(0, 1)

 

Hence, there are 3 ways Domo can reach the position (1, 1).

 

Last step, find the ways Domo can reach (1, 2), which is:

f(1, 2) = f(0, 1) + f(1, 1) + f(0, 2)

 

You can search dynamic programming on the internet for details if you still have questions.


Reference

 

English:

Dynamic Programming - GeeksforGeeks

Tabulation vs. Memoization

What is the difference between bottom-up and top-down?

 

Mandarin:

演算法筆記 - Dynamic Programming

 

Input

The first line contains two integers W (1 ≤ W ≤ 15) and L (L ≤ 15) - the width and the length of DomoMaze

For the next W lines, each line has L numbers either 1 or 0 - 0 for empty, and 1 for the portal.

 

The variable range of each test case is different.

For test cases 1 ~ 4, there is no portal in the DomoMaze.
For test case 5, there is one portal in the DomoMaze.
For test case 6, there are two portals in the DomoMaze.

 

Output

The output only contains a number and a newline character - the number of ways Domo can reach where Wilson is.

 

It's guaranteed that the answer will not be greater than 231-1.

Sample Input  Download

Sample Output  Download

Tags




Discuss