| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10972 | Remove unnecessary parentheses |
|
| 13837 | Bubbling! |
|
Description
Given an infix Boolean expression with parentheses, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. Please remove unnecessary parentheses and print the infix expression. Existence of unnecessary parentheses doesn’t affect the result of expression. For example,
(A&B)|(C&D) → A&B|(C&D)
(((A|B))) → A|B
Hint: You can combine two homework. Build a syntax tree and print the infix expression with necessary parentheses.
For OJ submission:
Step 1. Submit your main.c into the submission block.(Please choose C compiler)
Step 2. Check the results and debug your program if necessary.
Input
The input is an infix expression, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, two operators ‘&’ and ‘|’, and parentheses. The length of the infix expression is less than 256.
Output
The output is an infix expression without unnecessary parentheses.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
We learnt bubble sort in class, which could be implemented so easily:
void bubble_sort(int *begin, int *end)
{
for (; begin < end; end--)
for (int *ptr = begin + 1; ptr < end; ptr++)
if (*(ptr - 1) > *ptr)
iter_swap(ptr - 1, ptr);
}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.