# | Problem | Pass Rate (passed user / total user) |
---|---|---|
11711 | Dynamic 3D array |
|
12498 | Partial Judge Example |
|
13361 | Cardcaptor Sakura |
|
14493 | How Not to Name Your Child |
|
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.hDiscuss
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.cPartial Judge Header
12498.hDiscuss
Description
Sakura is a girl with super card magic.
However, you cannot make a living with magic, computer science is all you need.
To make use of her card skills, she tries to write a program to play cards:
There are 10 tables (indexed from 0 to 9) and no cards on them initially.
Given a command S, Sakura has to follow the instructions below:
(1) print: print the status of each table with the format :"table_idx: cards_on_the tables\n", e.g. "0: 1 3 3 4 5\n".
Note that if there are no cards, print "No card".
(2) all num len : Place len cards on each table, and the value on each card is num .
For example, the instruction "all 3 4" changes the status of each table to "table_idx: 3 3 3 3\n";
(3)
place table_idx len
integer_sequence
: Place a stack of cards on table table_idx. len means the number of cards in the stack. An integer sequence integer_sequence of length len is given, in which each integer means the value on the placed card.
For example, the instruction will be like:
place 2 3
3 2 1
And the status of Table_2 will become:
2: 3 2 1
Note that if there are cards already on the target table, the status will be overridden.
(4) swap table_a table_b: Swap the cards on table_a and table_b.
For example:
If the origin status of table 0 and table 1 are:
0: 1 2 3
1: 4 5 6
after "swap 0 1", the status of the two tables become:
0: 4 5 6
1: 1 2 3
This instruction is valid even if one of the tables is empty.
(5) clear: Clean all the tables.
(6) exit: terminates
hint. You can use pointer array to record each table.
Input
Commands separated by a newline character.
Note that:
1 <= the value of each card <= 13
1 <= number of cards on each table <= 10000
Output
Status of each table.
Sample Input Download
Sample Output Download
Discuss
Description
Note: If you don't want to read a long story, please skip to the line that says "End of the Story".
In Taiwan, there is a temple called Lungshan Temple in Wanhua. It is one of Taipei's oldest and most prominent temples. One of the gods worshipped here is Yue Lao, the god of love and marriage who binds the souls of lovers together, ensuring they meet and fall in love. It is said that the success rate here is pretty high. One of the couples, Mr. and Mrs. Chen, also met here and got married a few years afterward.
Well, there had been a lot of things going on since their marriage. A year after settling into their new life together, Mrs. Chen discovered she was expecting their first child. The news filled their home with excitement and joy, and they couldn’t wait to welcome their little one into the world. However, there was one problem: they couldn't come up with a good name for their child. Of course, they couldn't really ask the baby what name it wanted, so they ended up consulting someone else. For most people, that someone else would be some knowledgeable person in a neighborhood, a fortune teller, grandparents at home, or a priest, but for some reason, Mr and Mrs Chen chose to consult me.
"So, you want me to name your child?" I asked, confused.
"Of course!" Mrs. Chen replied eagerly. "We’ve been going back and forth about names, but nothing feels quite right. We really want something special, something that reflects our hopes for our child’s future."
"Wouldn't it be better to ask someone else? You know, someone knowledgable or something," I objected.
"You are studying at NTHU, aren't you? Then there's no one more knowledgeable than you!" Mr. Chen added.
"Seriously? I'm studying computer science, not—"
"—It's okay! Just give him any name you think it's good!"
I sighed. "What kind of name do you want?"
Mrs Chen thought for a while. "Auspicious ones. Something that will lead to a very long life."
"Hm... What about something related to tortoises? I heard it can live up to ten thousand years or something."
"Just ten thousand? So that means he's going to die after ten thousand years?" Mr Chen frowned. "What an unfilial son... you'll die before us, huh...?"
I shook my head slightly. "How long are you planning to live, seriously?"
"As a human, I might live something like eighty years or something, but even at that time, I still want to see him living happily from beyond my grave," Mr Chen said with a serious expression. "Isn't there a name that will make him immortal?"
"That's a tall order!" I exclaimed. "Well, I kinda understand how you feel. If you're looking for something that symbolizes endless life, I can come up with a few."
"Like what?"
"For example, 'Jugemu' means unlimited life, or 'Gokou no Surikire' meaning five kalpa[注1] of rubbing off, or 'Kaijarisuigyo' meaning..." I typed out the names on my laptop.
"Isn't that Japanese?" Mrs. Chen objected.
"It's fine. If anything gives our son a long life, it will do," replied Mr Chen.
"Okay, I've got the list of names here. Have a look at it," I cut in.
"Oh, that's a lot! What should we do? I can't really decide which one to use..." Mrs Chen leaned in to see the names.
"What if we put all of them together into one big name?" Suggested Mr. Chen.
"Heck no! Do you really want to name your kid Jugemu Jugemu Gokou no Surikire Kaijarisuigyo no Suigyoumatsu Unraimatsu Fuuraimatsu Kuunerutokoro ni Sumutokoro Yaburakouji no Burakouji Paipopaipo Paipo no Shuuringan Shuuringan no Guurindai Guurindai no Ponpokopii no Ponpokonaa no Choukyuumei no Chousuke!?" I objected.
"What's wrong with naming him Jugemu Jugemu Gokou no Surikire Kaijarisuigyo no Suigyoumatsu Unraimatsu Fuuraimatsu Kuunerutokoro ni Sumutokoro Yaburakouji no Burakouji Paipopaipo Paipo no Shuuringan Shuuringan no Guurindai Guurindai no Ponpokopii no Ponpokonaa no Choukyuumei no Chousuke?"
"Everything! Just imagine him doing exams! Everyone finished doing the exam, but your Jugemu Jugemu Gokou no Surikire Kaijarisuigyo no Suigyoumatsu Unraimatsu Fuuraimatsu Kuunerutokoro ni Sumutokoro Yaburakouji no Burakouji Paipopaipo Paipo no Shuuringan Shuuringan no Guurindai Guurindai no Ponpokopii no Ponpokonaa no Choukyuumei no Chousuke is still busy writing Jugemu Jugemu Gokou no Surikire Kaijarisuigyo no Suigyoumatsu Unraimatsu Fuuraimatsu Kuunerutokoro ni Sumutokoro Yaburakouji no Burakouji Paipopaipo Paipo no Shuuringan Shuuringan no Guurindai Guurindai no Ponpokopii no Ponpokonaa no Choukyuumei no Chousuke... huff, huff...is that really okay?"
Mrs Chen thought for a moment. "Point taken."
"But we really don't know which one to choose!" Objected Mr. Chen.
"That's why... I'm going to use my programming skills to help you choose the perfect name for your son!" I promised.
[注1]: a long period of time in Hindu and Buddhist cosmology. The exact length varies, but it is generally said to be the time from the creation of the universe to its recreation.
End of the Story
Okay, so here is the problem: I don't know what "perfect" is. There are so many ways to test if something is "better" than the other, and there is no objectively better way. This is why I chose a flexible option: to write a function that selects the best name based on a criterion that will be passed to the function at runtime:
The criterion, which I named comparing_function, is a function pointer that points to a function that takes in two constant string arguments. The criterion function should return a negative value if the first string is considered "better", positive if "worse," and zero if "equal".
Also, there is this utility function:
This function is called every time the number of the old list is getting full. What it should do is create a new list that holds new_capacity strings, move the strings from the original list to the list as well as deallocate the original one, then return the new list.
Lastly, there are two criterion functions I forgot to implement:
This function should compare the two strings in alphabetical order but with the strings written in reverse. The word that comes first is considered better. For example, the word ZEBRA backward is ARBEZ and HORSE backward is ESROH, so ZEBRA should be better than HORSE.
This function should compare the two strings in alphabetical order but the case is only used as a tiebreaker when the spelling is the same. A shorter string whose characters match those of a longer one is also considered coming before. For example, the following strings are in order:
BILL > Bill > bILL > bill >> BILL LOUIS > bill louis >> Louis >> Louisiana
However, I'm already exhausted from reading that name. This is why I'm delegating this task to you: to implement the four functions mentioned.
For your reference, here is the summary of the criteria used.
Criteria Name | Meaning | Example (Bolded one is prioritized) |
---|---|---|
AlphabeticalSum |
The summation of the order of each character in the string. The name with a larger sum is prioritized. |
"KNOWLEDGE" : 11 + 14 + 15 + 23 + 12 + 5 + 4 + 7 + 5 = 96 "ATTITUDE" : 1 + 20 + 20 + 9 + 20 + 21 + 4 + 5 = 100 |
BackwardsString |
The name that, written backward, comes before alphabetically is prioritized. |
"ZEBRA" : ARBEZ, "HORSE" : ESROH |
Conciseness |
The shorter name is prioritized. |
"A": 1 character, "JUGEMU": 6 characters |
Dictionary | The name that comes before alphabetically is prioritized. The case is used as a tiebreaker. |
"ZEBRA" "HORSE" |
EnglishOrder |
The name that comes before alphabetically is prioritized. |
"ZEBRA" "HORSE" |
Length |
The longer name is prioritized. |
"A": 1 character, "JUGEMU": 6 characters |
Qwerty |
The name is compared based on the position of its characters on a QWERTY keyboard. The top row is prioritized over the bottom row, and the key on the left is prioritized over the right on the same row. |
"SUN WUKONG" "ZHU BAJIE" |
ReverseEnglishOrder |
The name that comes after alphabetically is prioritized. |
"ZEBRA" "HORSE" |
ScrabbleScore |
The name that has a higher score for Scrabble, calculated by the sum of the points of each tile, is prioritized. The points tor the tiles are as follows:
|
"KNOWLEDGE" : 5 + 1 + 1 + 4 + 1 + 1 + 2 + 2 + 1 = 18 "ATTITUDE" : 1 + 1 + 1 + 1 + 1 + 1 + 2 + 1 = 9 |
Zhuyin |
(Limited to the name written in Hanyu Pinyin) The name that comes before in bopomofo is prioritized. It is guaranteed this won't appear when there's a name written in other systems than Hanyu Pinyin in the list. Please see Figure 1 for the Zhuyin - Pinyin conversion table. |
"SUN WUKONG" : ㄙㄨㄣ ㄨ ㄎㄨㄥ "ZHU BAJIE" : ㄓㄨ ㄅㄚ ㄐㄧㄝ |
Figure 1: Zhuyin - Pinyin conversion table.
Input
The input contains a list of commands. There are three types of commands:
ADD command:
[NAME]
This command indicates that the program should add a name to the list, namely at the very end. Each name has at most 999 characters, spaces included.
QUERY command:
[CRITERION]
This command indicates that the program should search for the best name in the list based on the criterion. If two strings are "equal", the one that came before is prioritized. It is guaranteed that the QUERY command will be called only when there is at least one name in the list.
END command:
This command appears exactly once in the last line of the test case. It indicates the program should terminate.
Output
The best names found from the queries, all trailed by an end-line character.