3117 - I2P(I)2024_Hu_Mid2_Practice Scoreboard

Time

2024/11/04 21:00:00 2024/11/18 18:00:00

Clarification

# Problem Asker Description Reply Replier Reply Time For all team

# Problem Pass Rate (passed user / total user)
12498 Partial Judge Example
13018 Diagonally sorting
13346 DomoMaze
14109 HUTI
14498 Hilbert Curve
14502 Audrey's Perfect Math Class
14503 Fake Cardcaptor

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




13018 - Diagonally sorting   

Description

Given a NxM array, please sort each diagonal line in ascending order from top-left to bottom-right.

 

For example, given 4x4 array, you should sort these diagonal lines:

This problem is partial judge, you need to implement the function:

// Sort each diagonal line of arr (which size is row x col)

void array2d_sort(int row, int col, long long arr[][500]);

 

Input

The first line contains two integers, N, M. 

The next N lines contain the array, each element in the array is separated by a space.

1 ≤ N, M ≤ 500

-1010 ≤ element in the array ≤ 1010

 

Output

Output the diagonally sorted array, with each element in the array separated by a space, and print out a newline after each row.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13018.c

Partial Judge Header

13018.h

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




14109 - HUTI   

Description

There is a well-known method to describe personality, which is MBTI(Myers-Briggs Type Indicator).

One day, TAs of I2P(I) want to develop their own TI, which is called "HUTI".

We'll use a integer to record the index of each personality type.

To check which type is the most unique one, given a type sequence, the most unique one  is the one with an odd number of occurrences

For example, the unique number in [1, 3, 2, 3, 2] is 1.

 

Following the above rule, we'll check N students and the results will be used to determine the most unique type in the class.

 

Note:

Use an "XOR" operation in this problem.

If you need more details, you can check : this 

Input

The input is composed of two parts.

The first line is N (1<=N<=100000001).

The following N lines will be the type indexes (The integer will be less or equal to 100000000).

Output

The unique type ended with a new line character.

Sample Input  Download

Sample Output  Download

Tags




Discuss




14498 - Hilbert Curve   

Description

This is a Hilbert Curve

Hilbert Curves

Your task is to print it the N-th pattern of the Hilbert Curve,

Here are the example of the 1st pattern, 2nd pattern, and the 3rd pattern:

The black part will be print using '#', while the empty part will be print by empty space

Your task is to set the board either 1 or 0, 1 if the position is black, 0 if it's not

 

NOTE: This is a partial judge question, you only need to modify the header file

As this is a partial judge question, you don't need to really worry about the input and output format

Input

There will be only 1 input N

1 <= N <= 10

Output

The entire N-th pattern

You can try to download the output pattern since the Sample IO doesn't have a good alignment text format

It should looks like this:

Sample Input  Download

Sample Output  Download

Partial Judge Code

14498.c

Partial Judge Header

14498.h

Tags




Discuss




14502 - Audrey's Perfect Math Class   

Description

Ms. Audrey has something to teach Josh, Vaness, Bill, and you!

As her student, you don't know how to solve her homework

Given Math Equation in prefix form, try to figure out the infix equation with the least amount of necessary parenthesis

Stream Baldi's PERFECT Basics In Education And Learning by airdefence |  Listen online for free on SoundCloud

e.g. given prefix form * - 20 30 50

the infix form will be (20-30)*50

((20-30)*50)is wrong since there is an unnecessary parenthesis

The opreator only consist of +, -,  and *

Input

There will be multiple testcase, each testcase have only 1 line input

Hint: Try to use getline function and char * as the array to scan the string, and scan it until EOF as we don't know the length of the string and how many testcases

Every number shown in the string are in range [0, 9999]

 

Testcase 1-2: only operator +

Testcase 3-4: operator and -

Testcase 5-6: operator +-,  and *

Output

For each testcase, print the infix equation, ended by a newline character

Sample Input  Download

Sample Output  Download

Tags




Discuss




14503 - Fake Cardcaptor   

Description

You have heard about Cardcaptor Sakura Question, but it's too easy. Maybe we can make it a little bit complex?

There are MAX_ARRAY maximum tables and MAX_ELEMENTS maximum elements for each table. Your problem is to modify the functions below:

[1] placeFunction

Param:
index size
a0, a1, ..., asize-1

Push a new element to specified index from behind
If pushing a new element exceed the maximum limit of elements, ignore the elements

Before Commands After
2: 5 5 5 1 2 5
1 2 3 4 5

1 5 3
8 8 8
2: 5 5 5 1 2 3 4 5
5: 8 8 8

 

[2] deleteFunction

Param:
index

To delete the table from specified index

Before Commands After
2: 5 5 5 1 2 3 4 5
5: 8 8 8
2 5 2: 5 5 5 1 2 3 4 5

 

[3] swapFunction

Param:
index1 index2

Swap table of index1 and index2

Before Commands After
2: 10 11
5: 8 8 8

3 2 5

3 2 7

5: 10 11

7: 8 8 8

 

[4] reverseFunction

Param: None

Reverse the order of existing (non empty) table
e.g. if the table only exist (non empty) index 3, 5, 6, 23 you need to reverse the order as
3->23, 5->6, 6->5, 23->3, and the remaining of the tables will still remains empty

Before Commands After

5: 1 2 3 4 5

8: 9 9 9

200: 50 77

4

5: 50 77

8: 9 9 9

200: 1 2 3 4 5

 

[5] popFunction

Param:
index pop_num

Pop the last elements of the table[idx] pop_num times
If it exceed the amount of existing elements, then you can stop in remove all

Before Commands After

5: 1 2 3 4 5

8: 9 9 9

200: 50 77

5 8 4

5 5 2

5: 1 2 3

200: 50 77

 

[6] shiftFunction

Param:
shift_num

Shift the table index by shift_num
If it's positive, shit to the right, and if it's negative shift to the left

Before Commands After

5: 1 2 3

200: 50 77

6 -10

190: 50 77

995: 1 2 3

 

[7] sortFunction
Param:
index

Sort the table[idx] from lowest to highest

Before Commands After
2: 3 7 4 6 5
5: 8 8 8
7 2

2: 3 4 5 6 7

5: 8 8 8

 

[8] printFunction
Param: None

Print the non empty table with a index as the header, and ignore the empty one
e.g. if the only non empty table are index 2 and 6
then your print format will be
2: a[2, 0], a[2, 1], ... 
6: a[6, 0], a[6, 1], ... 
idx:[space]num1[space]num2...[space]numn-1[newline]
If all table are empty, print "Empty QQ" followed by '\n'

This is a partial judge, you only need to implement the functions and scan the given parameters

 

Hint: You need to really optimize the pointers to pass some of the testcases

Input

There are T instructions

For each instruction, the input will be idx param

param will be unique based on the functions describe

0 <= Index <= MAX_ARRAY-1

0 <= ai, size, pop_num <= MAX_ELEMENTS

-105 <= shift_num <= 105

Output

See the print function format in the description

Sample Input  Download

Sample Output  Download

Partial Judge Code

14503.c

Partial Judge Header

14503.h

Tags




Discuss