Description

Mr. Kuo is an adventurer. One day, he finds a secret room in a cave.

There is some hint to the password of this room.

Mr. Kuo is given an integer N and a string S = s₁s₂...s_N consisting of L and R.

At first, Mr. Kuo has a string A = "0".

For each i = 1, 2, ..., N :

• If s_i is L, insert i to the left of the "number" i - 1 in A.
• If s_i is R, insert i to the right of the "number" i - 1 in A.

The final contents of A is the password. Please help Mr. Kuo find the password.

For example, N = 3 and S = "LRL", then：

• s₁ = L, insert 1 to the left of 0,   A = "10"
• s₂ = R, insert 2 to the right of 1, A = "120"
• s₃ = L, insert 3 to the left of 2,   A = "1320"

Input

The first line contains one integer T — the number of test cases. Description of the test cases follows.

The first line of each test cases contains an integer N.

The second linef of each test cases contains a string S consisting of L and R of length N.

For each test：

1. T ≤ 100, N ≤ 10
2. T ≤ 100, N ≤ 100
3. T ≤ 100, N ≤ 500
4. T ≤ 100, N ≤ 1000
5. T ≤ 100, N ≤ 10000
6. T ≤ 10, N ≤ 100000

Output

For each test case print a string A — the final contents of the password, seperated by spaces.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We learnt bubble sort in class, which could be implemented so easily:

Short as the codes might be, it doesn't run efficiently at all. It's obvious that he number of comparisons (the if branch) would be executed \(\sum^{i=n-1}_1i\) times. In fact, we could improve the performance slightly since if inside the second for loop there's no any swap required, then the sorting is already done and no longer need to compare or swap any more.

On the other hand, the number of swaps, which equals the number of inversions, is the bottleneck of bubble sort, constraining the time complexity.

So given an array, you are to compute the two number mentioned above: minimum number of comparisons and number of swaps that bubble sort take.

Input

The first line is an integer \(n<10^4\) indicating the length of the array.

The next line contains the \(n\) integers \(a_i\in[-2^{31},2^{31})\) of the array.

Output

Please print two integers, the number of comparisons and number of swaps, separated by a space. Remember to put a '\n' at the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Traveling Salesman Problem (TSP) is a classical problem that we are to find the shortest distance traversing all vertices in a graph from any source and returning to the source, which is considered hard for computers (and maybe human as well).

Nevertheless, the TSP on tree is quite easy: the shortest circuit must visit all edges exactly twice. You could prove this by induction. So let's consider the Open Loop TSP, in which the salesman is not required to return to the source. 

In this problem, your task is the Open Loop TSP on trees, i.e., finding the shortest distance traversing all nodes in a tree from any source without returning to the source.

Input

There's an interger \(n\) in the first line, indicating the number of nodes in the tree.

The next \(n-1\) lines consist of three integers \(a_i,b_i,w_i\) representing that there's an bidirected edge between \(a_i\) and \(b_i\) weighing \(w_i<2^{31}\).

For \(50\%\) of the testcases, \(n\leq5\times10^4\). For the other \(50\%\) of the testcases, \(n\leq10^6\).

Output

Please print the shortest distance traversing all nodes in a tree from any source without returning to the source.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Procat (破貓) has a lot of electrical appliances in his dormitory, such as computer, refrigerator, and electric fan. He wants to connect all the appliances to the power outlet. There is only one power outlet in his dormitory, so he needs to use extension cords and power strips to connect all the appliances to the power outlet.

Extension cords and power strips Procat currently using don't have overcurrent protection. As a friend of Procat, you are very concerned about electrical safety. You want to help Procat to connect all the appliances to the power outlet in a safe way. Luckily, you have some spare power strips with overcurrent protection. But you don't have any spare extension cords.

Power strips you have got one input and two outputs. Power strips can connect to extension cords, but power strips cannot directly connected to each other.

The price of the high-quality extension cord you want to buy is proportional to the current flowing through it. You wants to minimize the total price of the extension cords you needs to buy.

Calculate total price of the extension cords you need to connect all the appliances to the power outlet.

• After connecting all the appliances to the power outlet, it should look like a binary tree. The power outlet is the root of the tree, and the appliances are the leaves of the tree. The power strips are the internal nodes of the tree. The extension cords are the edges of the tree.

Sample

Following figures show examples of optimal ways to connect the appliances to the power outlet in each sample testcase. In each figure, squares represent power strips, circles represent appliances, and edges represent extension cords. The total price of the extension cords is the sum of current flowing through all the edges.

Sample testcase 1:

Sample testcase 2:

• Hint: Huffman Coding

Input

First line contains an integer \(N\), the number of electrical appliances Procat wants to connect to the power outlet.

The second line contains \(N\) integers \(a_1, a_2, \dots, a_N\), the power consumption of the \(N\) electrical appliances.

\(N\)
\(a_1 \quad a_2 \quad \dots \quad a_N\)

Constraints

• \(1 \leq N \leq 10^4\)
• \(1 \leq a_i \leq 10^9\)

Output

Output contains one line, the minimum total price of the extension cords Procat needs to buy. You don't need to output a newline at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

After figuring out the correct map, Procat still doesn't have any idea about the destination of the trip. However, he has decided to visit some restaurants on the way, so that he can bring some food back to his best friend, Jason.

Procat wants to visit these restaurants one by one in a specific order. However, he is not sure if there is a route in the map that meets his requirement. Help Procat to check if there is a route on the map that visits all the restaurants consecutively in the order he wants. Since Procat go cycling everyday, he wants to query the route for multiple times, with different restaurants to visit. You should help him to check the route for each query.

Procat will give you the map in a special format he used in "Same Map" (You should be familiar with it if you have solved the problem yourself). The format is described by the following EBNF:

TREE ::= INT '(' TREE ')' '(' TREE ')'
       | NIL

The tree in the sample testcase is shown in the following figure.

• For the first query, Procat wants to visit the restaurants 1→3→7. However, there is no route that visits all the restaurants consecutively in the order Procat wants.
• For the second query, Procat wants to visit the restaurants 7→3→1. There is a route that meets Procat's requirement, which is highlighted in blue.
• For the third query, Procat wants to visit the restaurants 1→5. Note that the route could start from any vertex in the map, not only from the root.

Input

• The first line contains an integer $n$, the number of vertices in a map.
• The second line contains a string $X$, representing the map in the EBNF format.
• The third line contains an integer $q$, the number of queries Procat wants to make.
• Each of the following $q$ lines contains the following:
  • An integer $m$, the number of restaurants Procat wants to visit.
  • $m$ integers, representing the "name" of the restaurants.

$n$
$X$
$q$
$m_1 \quad r_{1,1} \quad r_{1,2} \quad \ldots \quad r_{1,m_1}$
$\enspace \vdots$
$m_q \quad r_{q,1} \quad r_{q,2} \quad \ldots \quad r_{q,m_q}$

Constraints

• $1 \leq N \leq 10^5$
• length of $X$ and $Y$ won't exceed $10^6$ characters
• $X$ and $Y$ only contains characters (, ) and digits.
• $1 \leq m_i \leq 100$
• $1 \leq q \leq 500$

Output

For each query, print YES if there is a route that visits all the restaurants consecutively in the order Procat wants. Otherwise, print NO. You should print a newline character after each query.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Forevernight is playing cards with his friend SugarHao in their new apartment Mèng Zhú public housing (孟竹國宅).

As a CS student, he wants to play it in a programmer way. He decides to write a program for the purpose of shuffling the cards. Moreover, since Forevernight is really famous in their department, more friends may come while he is shuffling cards, so sometimes he needs to insert new cards into the card stack, too.

In view of the fact that he's taking I2P(II) this semester, his another friend Jason (one of the TAs) commands that he should write the program in a C++ way.

Note: This is a patial judge problem. You're asked to implemet 4 functions in this problem.

• Card* Construct(int n);
  This function would create a linked list with n elements, each node (ie. card) contains a number given by testcase serially in one single line. (Noted that you should get the number from the input by std::cin or scanf on your own.) 

​The function should return a pointer to the first element of the linked list.

Warning: To improve your C++ skills, you should only use C++ operator new to allocate your Card node. We will use another function void Destruct(Card* head); using delete to deallocate the space.

• void cut(int a, int b, Card* head);
  This function should move cards whose index between a and a+b-1 ( [a, a+b) ) to the top of the card stack. Order of the cards inside the moved part shouldn't be changed.
• void add(int idx, int num, Card* head);
  This function should add a new card with number num before card idx.
• void print(Card* head);
  This function should print out the card list from top (index 0) to buttom (largest index), each number followed by a newline character ('\n').

Input

• ADD idx num: Add a new card with number num before card idx.
• CUT a b: Move cards whose index between a and a+b-1 ( [a, a+b) ) to the top of the card stack. Order of the cards inside the moved part won't be changed.

Output

Print out the card stack from top (index 0) to buttom (largest index), each number occupies one line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

In NTHU, there are numerous Oloo stations interconnected by roads forming a tree structure. Each road has its passage time.

To ensure easy access for everyone to borrow Oloo, the operating company need to redistribute Oloo among stations during night so that each station has an equal number of Oloos.

You're given a tree consisting of $N$ nodes and $N-1$ edges, representing the map of NTHU campus. Each node is an Oloo station number from $0$ to $N - 1$, and the number of Oloo in Oloo station $i$ is denoted as $a_i$. The edges are represented by (u, v, w), where edge (u, v) connects node $u$ and node $v$, and the time required to traverse this edge is denoted by $w$.

The total cost of redistributing Oloo is calculated as the sum of distances each Oloo is moved, considering the passage time of each road. The objective is to minimize this cost. Write a program to help calculate the minimum cost.

Input

The first line contains an integer $T$, which is the number of testcases. For each testcase:

• The first line contains an integer $N$, which is the number of oloo station.
• The second line contains $N$ integers $a_1, a_2, \dots, a_N$, which are the number of Oloo in each station.
• The following $N-1$ lines of each testcase contain three integers $u_i, v_i, w_i$, which means there is a road connects $u_i$ and $v_i$, and the cost of road is $w_i$.

$N$
$a_1 \quad a_2 \quad \dots \quad a_N$
$u_1 \quad v_1 \quad w_1$
$u_2 \quad v_2 \quad w_2$
$\vdots$
$u_{N-1} \quad v_{N-1} \quad w_{N-1}$

Constraints

• $1 \le T \le 5$
• $0 \le u_i, v_i < N$
• $1 \le w_i \le 1000$
• For testcase 1~3:
  • $1 \le N \le 500$
  • $0 \le a_i \le 1000$
• For testcase 4~6:
  • $1 \le N \le 2 * 10^5$
  • $0 \le a_i \le 1000$
• For testcase 7~9:
  • $1 \le N \le 2 * 10^5$
  • $0 \le a_i \le 10^7$

Output

For each testcase, output its minimum cost. If it's impossible, print -1 as the answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Jameson loves to eat cakes from "Feed the Young Master (餵公子吃餅)" since the cakes give him wings. Nevertheless, the cakes bring side effects such as being prone to colds and insomnia.

The cakes come in 26 flavors (a-z). A package of cakes can have a random number of each flavor. Also, the arrangement of cakes in a package is random.

Today, Jameson wants to have some cakes before he sleeps. To avoid eating too much, he will only pick consecutive cakes with the same flavors. However, since he loves the cakes too much, he allowed himself to swap two cakes before picking consecutive same-flavor cakes.

Please help Jameson to find out the maximum number of cakes he can eat.

• This is a partial judge problem. You don't need to handle input and output. All you have to do is to implement the function int solve(std::string &text).
• This is a work of fiction. Any resemblance to actual persons, living or dead, or actual events is purely coincidental.

Input

Input contains one line with a string text, the arrangement of cakes.

Constraints

• 1 <= text.length <= 10⁵
• text consist of lowercase English characters only.

Output

Output contains one line with an integer, the maximum number of cakes Jameson can eat.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss