You are given an string $$$s$$$, you go from left to right and append the unique characters in order of their appearance to an empty string $$$x_1$$$ and delete that character from it's position in $$$s$$$, if there are no more unique characters to be appended to $$$x_1$$$ you will create new string $$$x_2$$$ and start appending to it and so on... In the other words you will create $$$x_1,x_2,\dots x_k$$$ strings of unique characters as long as $$$s$$$ becomes empty.
Now your task is to print the last string that is created after end of this process, which is actually $$$x_k$$$.
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ — the number of test cases.
$$$$$$1 \le t \le 100$$$$$$
The first line of each test case contains an string $$$s$$$ consisting of lowercase letters.
$$$$$$1 \le |s| \le 2 \cdot 10^5$$$$$$
It is guaranteed that sum of lengths overall testcases won't exceed $$$2 \cdot 10^5$$$.
For each test case, print the last shortest string after this process.
3 aaabbc hgghi xyz
a gh xyz
In the first test case, $$$s = $$$"aaabbc" $$$x_1 = $$$"abc" $$$x_2 = $$$"ab" $$$x_3 = $$$"a"
For second test case, $$$s = $$$"hgghi" $$$x_1 = $$$"hgi" $$$x_2 = $$$"gh"
Gaz is an infinite city. The streets of this city are as follows :
Gaz Map The streets of this city can be introduced on the two-dimensional coordinate system as follows :
- A horizontal street coinciding with the $$$x-$$$axis.
- A vertical street coinciding with the $$$y-$$$axis.
- For every natural number $$$n$$$, there is a circular street with radius $$$n$$$ with the center of $$$(0, 0)$$$ coordinate.
We know that Alice is currently at a junction with coordinate $$$(x_1, y_1)$$$ and Bob is currently at a junction with coordinate $$$(x_2, y_2)$$$. A junction is a point at intersection of two streets. For example, $$$(0,1)$$$ and $$$(0,-1)$$$ are junctions formed from intersection of horizontal street and circular streets with radius $$$1$$$.
Alice wants to know the shortest distance that she has to walk in the streets of Gaz to reach Bob.
In the first line of input you'll be given a number $$$t$$$ $$$-$$$ the number of the testcases.
$$$$$$1 \le t \le 100$$$$$$
In each of the next $$$t$$$ lines, you'll receive $$$4$$$ integers $$$x_1, y_1, x_2, y_2$$$ which show the coordinates of the junctions where Alice and Bob are located.
$$$$$$-10^9 \le x_1, y_1, x_2, y_2 \le 10^9$$$$$$
It is guaranteed that at least one of $$$x_1, y_1$$$ and at least one of $$$x_2, y_2$$$ will be $$$0$$$.
For each test, print only one line containing a single floating-point number $$$-$$$ the minimum answer. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
42 0 -4 00 3 5 00 -7 0 00 -5 0 -5
6.000000 6.712389 7.000000 0.000000
Explanation of testcase $$$1$$$ :
The shortest path between these two junctions is a path in the form of a straight line.
$$$$$$\sqrt {(2 - (-4))^2 + (0 - 0)^2} = 6$$$$$$
Explanation of testcase $$$2$$$ :
The shortest path is like this :
$$$$$$\frac{1}{4} \times (2\pi \times 3) + \sqrt{(5 - 3)^2 + (0 - 0)^2} = \frac{3\pi}{2} + 2 \simeq 6.712389$$$$$$
You're given $$$n$$$ binary strings each of length $$$m$$$. In each operation, You can choose a prefix of an string and flip it (change each $$$0$$$ to $$$1$$$ and vice versa).
Now the goal is to make all these $$$n$$$ strings equal to each other. You should print the minimum number of operations needed to achieve the goal.
In the first line of input you'll be given a number $$$t$$$ which shows the number of testcases : $$$$$$1 \le t \le 10^3$$$$$$.
In the second line of input you'll receive two integers $$$n$$$ and $$$m$$$ which shows the number of strings and their length.
$$$$$$1 \le n, m \le 10^5$$$$$$.
In the next $$$n$$$ lines you'll receive strings of length $$$m$$$ which consist only of $$$0$$$ and $$$1$$$.
It is guaranteed that sum of $$$n \cdot m$$$ overall testcases does not exceed $$$10^5$$$.
In each line print the minimum number of operations needed to make the strings of each test equal to each other.
31 102 201104 501010001011100000110
0 1 5
Explanation for testcase $$$2$$$ :
- You only should choose prefix of length $$$2$$$ for the first string and then it will become $$$01 \rightarrow 10$$$
After the bomb explodes, Mr. Farhadi, even though he moves away from the bomb, is seriously injured and falls into a coma...
Tok has taken command instead of him, and in one of the attacks, while explaining the attack plan to the soldiers, one of the soldiers says that he also has a plan to attack.
A plan for an attack is to arrange the soldiers in an $$$n \cdot n$$$ map so that there is exactly one soldier in each row and in each column. The weakness of a map is the biggest $$$k$$$ that there is a $$$k \cdot k$$$ square in the map such that there are no soldiers in it.
Tok's map is such that its weakness is the least weakness among all the maps possible (note that we don't have Tok's map). If the map that Tok's soldier suggests to him is weaker than Tok's map, Tok will throw him into the black hole!
In the input you are given the soldier's map. First, print the weakness of his map, then determine whether the soldier falls into the black hole or not. (Is there a plan whose weakness is less than the plan proposed by the soldier?)
In the first line of input you'll be given $$$n$$$.
$$$$$$1 \le n \le 5 \cdot 10^4$$$$$$
In the next line you'll receive a permutation $$$p$$$ of length $$$n$$$ which $$$p_i$$$ shows that the solider of the $$$i_{th}$$$ column is located in the $$$p_{i}{th}$$$ row.
$$$$$$1 \le p_i \le n$$$$$$
In the first line of output print the weakness of the soldier's map.
In the second line, print "YES" if the soldier falls into the black hole and "NO" otherwise.
4 1 2 3 4
2 YES
2 1 2
1 NO
Explanation of test $$$1$$$ :
You can see that the answer of soldier's plan is $$$2$$$ but the optimal answer is $$$1$$$
You're given an array of integers $$$a = a_1a_2...a_n$$$, now you like to see number $$$69$$$ as many as possible in the array, for this goal there are two operations that can be used in a move :
- choose a prefix of the array and subtract $$$1$$$ from all of the elements of the chosen prefix.
- choose a suffix of the array and subtract $$$1$$$ from all of the elements of the chosen suffix.
Note that you can choose exactly one of the operations above at each moment and you can do each operation many times (possibly $$$0$$$), also numbers can become negative during the operations.
Now your task is to find the maximum number of $$$69$$$ you can obtain in the array.
In the first line of input you'll be given a number $$$n$$$ which shows the length of the array.
$$$$$$1 \le n \le 2000$$$$$$
In the second line you'll receive the array.
$$$$$$1 \le a_i \le 10^9$$$$$$
Print the maximum number of $$$69$$$ you can obtain with the given operations in the array.
7 64 69 72 72 72 69 64
4
7 72 77 71 5 73 71 72
5
Operations of testcase $$$2$$$ :
- choose the prefix of length $$$5$$$
- choose the prefix of length $$$5$$$
- choose the prefix of length $$$2$$$
- choose the suffix of length $$$3$$$
- choose the suffix of length $$$3$$$
- choose the suffix of length $$$1$$$
The array after the operations : $$$a = $$${$$$69, 74, 69, 3, 69, 69, 69$$$}.