3141 - I2P(I)2024_Hu_Final_Practice Scoreboard

Time

2024/12/02 20:30:00 2024/12/16 18:00:00

Clarification

# Problem Asker Description Reply Replier Reply Time For all team
# Problem Pass Rate (passed user / total user)
12544 Simple Web Crawer
13391 Domo the Train Conductor
13412 I hate Christmas
13751 Super Idol
14546 Simple Tree Calculator
14547 Take leaves

12544 - Simple Web Crawer   

Status  |  Limits Submit

Description

A Web crawler, sometimes called a spider or spiderbot and often shortened to crawler, is an Internet bot that systematically browses the World Wide Web.

Generally, a Web crawler visits a website, reads the HTML code of the website, gathers information it wants, and probably wants to visit the links it found in this website.

For example, if a Web Crawler visits the wikipedia webpage introducing "Web crawer" (the webpage is shown in the left part of the image) ...

  1. It reads the html code of the webpage (shown in the right part of the image)

  2. It gathers information. For example,

    1. It finds the definition of "Web Crawler"

    2. It finds several links (i.e. the blue words in the webpage), such as links to "Internet bot", "World Wide Web", etc.

  3. It probably wants to visit the links "Internet bot", "World Wide Web", ... one by one to get more information.

In this problem, you are going to implement a simple Web crawler. Given the html code of some website, you are going to output several information :

  • Title of the website

The title of the website is the string placed within <title> and </title>, for example, the title in sample input is "This is the title".

  • Numbers of links in this webpage

A link in html is in the following syntax : <a href="url">link text</a>, where url is the link address and link text is the text of the link.

Refer to the to Sample IO for output format.

Hints

  • What is html code?

    • In this problem, you only need to know that html code are several lines of strings in some special format.

    • html code are tags in the following format : <tagname>contents of tag</tagname>

    • In Chrome, you can press F12 key to see the html code of the website

  • How to read in html codes?

    • Some useful functions you've learned in previous homework 12507 - Searching Remark :

    • char *strtok(char *str, const char *delim) - to break string str into a series of tokens using the delimiter delim, which is defined under string.h

    • char *fgets(char *str, int n, FILE *stream) - to read a string of length n into string str from a file stream stream (e.g. stdin), which is defined under stdio.h

  • How to find title?

    • Why not start with finding the position of <title> and </title> ? The substring between <title> and </title> is the title of the website.

  • How to count links?

    • For every link in html, it must contains the substring </a>. This problem can be solved by counting the number of occurrence of </a>.

 

Input

You will be given a HTML code. Input contains at most 100 lines. Each line contains at most 1000 characters.

Technical Restrictions

Only the following tags will appear in the input :

  • <html> </html>

  • <head> </head>

  • <body> </body>

  • <title> </title>

  • <a> </a>

  • <h1> </h1>

  • <p> </p>

All tags except for <head></head> and <body></body> will be on the same line.

In each case, there will be exactly one <head></head>, one <body></body>, one <title></title>.

It is guaranteed that the contents of tags will not contain '<' or '>'.

Output

For the first line, please output the title of the given website.

For the second line, please output the number of links in the given website.

Remember to add new line character in the end of each line.

Sample Input  Download

Sample Output  Download

Tags




Discuss




13391 - Domo the Train Conductor   

Status  |  Limits Submit

Description

Domo is a train conductor, he wants to adjust the train he's driving.

 

There are five instructions below with the description:

 

1. AddFront num

Add a train carriage with the index num in front of the train.

 

2. AddBack num

Add a train carriage with the index num in back of the train.

 

3. Delete num

Delete all the train carriages with the index num from the train. (If the train has no any carriage with the index num, do nothing)

 

4. DeleteFront

Delete the first element of the train. (If the train is empty, do nothing)

 

5. Swap

Reverse all train carriages. (If the train is empty, do nothing)

 

For example:

AddFront 5 makes the train [4, 1] become [5, 4, 1].

AddBack 5 makes the train [4, 1] become [4, 1, 5].

Delete 5 makes the train [5, 4, 1, 5, 3] become [4, 1, 3].

DeleteFront make the train [1, 2, 3, 4] become [2, 3, 4].

Swap makes the train [2, 6, 3] become [3, 6, 2].

 

The train is empty in the beginning. Given a series of instructions, please print the index of train carriages after all instructions are executed.

 

This is a partial judge problem, you're asked to implement these 5 functions.

 

If you get a TLE:

Try to use the pointer head and back wisely, which can make the AddFront and AddBack instructions faster!

 

If you get an MLE:

Remember to free the nodes you've deleted!

 

Input

The input consists of multiple instructions (1 ≤ number of instructions ≤ 105)

 

the index of each instruction is a positive integer and not greater than 102.

 

Output

The output only consists of a line denoting the train carriage indices after all the instructions.

 

It's guaranteed that the output consists of at least one carriage.

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

13391.c

Partial Judge Header

13391.h

Tags




Discuss




13412 - I hate Christmas   

Status  |  Limits Submit

Description

One day, you become a santa claus and have to send everyone gifts.

 

There is a line of people, and each one has a non-unique number card which represents what gifts they will receive.

(Because you are a smart santa claus, you use linked-list to record the numbers)

However, when you see there are so many couples standing together, you feel so angry and decide to rearrange the order with the following rule:

 

Given the head of the linked list containing multiple groups (the size of each group is k ), reverse the nodes inside each group at a time.

k is a positive integer and is less than or equal to the length of the linked list.

If the number of nodes is not a multiple of k, then the left-out nodes in the end should remain the same order.

You are not allowed to alter the values in each node.

 

For example, when k = 2:

 

Note that it is a partial-judge problem that you need to implement the function:

Node* Solver(Node* head, int k)

Input

The first line is composed of a sequence of integer(1<= val <=100000000), which represents the values of the linked list.

The input stops when read in '-1' ('-1' is not a part of the 2 linked-lists).

The second line is k,  the size of the group that will be reversed.(1 <= k <= length of the linked list)

Output

The values of the group-based reversed linked-list.

The values are separated by a whitespace and the output is also ended with a whitespace.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13412.c

Partial Judge Header

13412.h

Tags




Discuss




13751 - Super Idol   

Status  |  Limits Submit

Description

TWICE is a world-wise famous idol group.

One day, there is a special event for people with fans ID in the range [start, end].

Since you are a CS student, you want to check if there are any special relations between the numbers in this range.

 

The way you check these numbers is easy:

There will be T test cases.

For each test case, given the range [start, end], you must calculate the bitwise AND of all numbers in this range, inclusive.

For example, [5, 7] will be 5 & 6 & 7, which will be 101 & 110 & 111.

The calculated result is 4(100). 

 

Note that for test case 1~3, there will be only 1 test case; for test case 4~5, there will be multiple test cases.

If you got TLE, please consider the bit relation in these numbers instead of using a brute-force algorithm.

Input

The first line is T(1 <= 50).

The next T lines are the test cases. 

For each test case, are 2 unsigned integers start and end(1 <=  start, end <=2147483647), separated by white space.

Output

For each test case, you have to print a '\n' in the end.

Sample Input  Download

Sample Output  Download

Tags




Discuss




14546 - Simple Tree Calculator   

Status  |  Limits Submit

Description

TA too lazy to make the description, yet also too lazy to finish the code

But do you know if you can make a calculator using tree data structure?

I've implement some part, but still not finish

Help the TA finish the code

This question is a partial judge

You need to implement 2 functions that defined in the header file

Input

There is T testcases

The input is the prefix equation contains combination of '&', '|', '^', '1', and '0'. Also you don't need to worry about the format as it's a partial judge

 

Output

The result, either True or False for each testcases

Sample Input  Download

Sample Output  Download

Partial Judge Code

14546.c

Partial Judge Header

14546.h

Tags




Discuss




14547 - Take leaves   

Status  |  Limits Submit

Description

Elephants enjoy taking leaves from trees to eat. At the i-th node of the tree, there are vi​ leaves.

However, trees in computer science differ from real-world trees, the tree has n nodes and n - 1 edges and is rooted at node 1.

If a node is removed, all nodes beneath it (i.e., its subtree) will also be removed.

The problem involves q queries, and each query provides an integer k, asking how many leaves in total (including the leaves at node k) will be removed if node k is removed.

 

(In this problem, "leaves" are used to represent the value of a node, not the actual leaf nodes as defined in a tree structure.)

Input

The first line contains two integers, n and q.

2 ≤ n, q ≤ 1000 (Testcases 1 ~ 2)

2 ≤ n, q ≤ 2 * 105 (Testcases 3 ~ 5)


The second line contain n integers vi, representing the leaves on i-th node.

1 ≤ vi ≤ 1000

 

The following n - 1 lines each line contain two integers u and v, representing that u and v is connected.

1 ≤ u, v ≤ n

It is guaranteed that the graph is a tree.

 

The following q lines each line contain a integer k, answer the sum of leaves on the k-th node's subtree.

1 ≤ k ≤ n

Output

For each query, output the answer of sum of leaves on the k-th node's subtree, followed by a new line character '\n'.

Sample Input  Download

Sample Output  Download

Tags




Discuss