Cayo is a very good student, but he is very tired with the semester at IME (Institute of Mirthful Excellence), so he started to miss some classes on purpose. Although last year things went very well this way, this year Colonel Dolphin started to straighten things out. He is very careful with class absences, so he will notice if someone does not show up.
The attendance system at IME works in a very weird way. Everyday, the students have many classes, and it is a looooong and exhausting day. Every class has a number of points $$$a_i$$$, called attendance points, and for every class a student attends, he earns $$$a_i$$$ points. At the end of the day, the sum of the earned points will compose your attendance points.
The students arrive at the first class, and they can leave earlier, before all classes end. Although they can not miss all the classes in one day (they have to go to IME everyday), there is a threshold of absent classes established by IME (because bad things happen, right?). Everyday Colonel Dolphin will look for missing students, checking if their attendance points are less than the threshold, $$$t_i$$$.
Cayo has to go to IME but does not want to spend her/his precious time with useless classes, so he decided to watch only the necessary to reach the threshold each day. Help him to count the attendance points he needs to have everyday and how many classes he has to watch to accomplish that.
The first line contains one integer, $$$n$$$ ($$$1 \le n \le 10 ^ 5$$$) — the number of classes during a day.
The next line will contain $$$n$$$ space-separated integers, $$$a_i$$$ ($$$1 \le a_i \le 10 ^ 9$$$) — the number of attendance points from a class.
The next line contains one integer $$$m$$$ ($$$1 \le m \le 10 ^ 5$$$) — the number of days Cayo has to go to IME.
The next line will contain $$$m$$$ space-separated integers, $$$t_i$$$ ($$$1 \le t_i \le \sum_{i = 1}^n a_i$$$) — the number of the threshold for attendance points for that respective day.
Output two numbers for each $$$m$$$ days — the minimum number of attendance points and the minimum number of classes needed each day.
5 3 4 5 8 10 5 1 3 8 21 30
3 1 3 1 12 3 30 5 30 5
4 100000 8 9 3 4 100000 1000 100007 100009
100000 1 100000 1 100008 2 100017 3
At his university, Sakai has been tasked with shooting cannons and discovering how far they will go. However, since he's shooting the cannons from a beach, they land in the water and he's unable to say where it exactly landed. Because of this, he asks two friends for help, Evelyn and Gandolfi, to find out what the distance is. Each of his friends is equipped with a device that is able to precisely find out the coordinates of the cannon ball once in its trajectory. These coordinates indicate the height the projectile is at a certain distance from the cannon.
Given the projectile's trajectory is a perfect parabola, and considering the cannon to be positioned at the origin of the coordinate plane, can you help Sakai find out what the distance from the cannon the shot landed?
The first line contains a single integer, $$$T$$$, $$$(1 \leq T \leq 10^5)$$$ — the number of test cases.
Each test case is one line and contains four integers, $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$, $$$(1 \leq x_1, y_1, x_2, y_2 \leq 10^4, x_1 \neq x_2)$$$ — indicating the position where Evelyn and Gandolfi, respectively, spotted the projectile.
For each test case, output a real number — the total distance traveled by the projectile. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$, that being if your answer is $$$a$$$ and the jury's is $$$b$$$, then the judge will check if $$$\frac{|a - b|}{max(1, b)} \leq 10^{-6}$$$.
24 5 8 54 5 7 6
12.000000000000000 13.545454545454545
Students aren't allowed to leave the Institute of Magic and Embarrassment (IME), so they get very hungry for candy. Camelo realized this opportunity and decided to open a candy store inside IME (no one knows how he got permission to do such an absurd thing).
There are $$$n$$$ students in IME, and every day student $$$i$$$ orders $$$c_i$$$ candies. Camelo does not care about money, he only wants to be liked by the maximum number of people at IME. A student likes Camelo if at the moment he receives his order, he has more candies than everyone else together.
Can you help Camelo find the maximum number of people he can make like him, and the minimum number of candies to do so? He can attend the orders in any order he wants (he may also choose to ignore some orders).
The first line contains a single integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$ — the number of test cases.
Each test case is two lines and the first line contains an integer $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ indicating the number of students at IME.
The second line contains $$$N$$$ integers $$$x_i$$$ $$$(1 \leq x_i \leq 10^9)$$$, indicating how many candies student $$$i$$$ orders.
It is guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$3 \times 10^5$$$.
For each test case, output two integers — the maximum number of people Camelo can make like him and the minimum number of candies to do so.
433 4 251 8 4 2 1011052 2 2 2 2
2 5 4 15 1 10 1 2
In the first case, we can at most make two people happy, and the way of doing so that minimizes the number of candy is attending the third person and then the first, requiring $$$2 + 3 = 5$$$ candies.
For João Braga, Calculus III is the easiest subject that he's ever studied, despite Mr. LV's greatest efforts. Because of this, he tends to drift off during class (as he doesn't need to study) and tries to distract himself with games he comes up with in his mind. One day he came up with a really exciting game: João Braga would randomly select two words from the blackboard and mess around with them. After selecting these two words, he would concatenate them and swap any two characters as he pleases. The game is considered successful if he's able to find the lexicographically smallest combination. Given these two strings $$$s$$$ and $$$t$$$, can you help João Braga find it?
A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:
- $$$a$$$ is a prefix of $$$b$$$, but $$$a \neq b$$$.
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter of $$$b$$$
The first line contains a single integer $$$T$$$ $$$(1 \leq T \leq 10^3)$$$ — the number of test cases.
Each test case is one line and contains two strings, $$$(1 \leq |s|, |t| \leq 10^3)$$$ — the words that João Braga chose, all of which only contain lowercase Latin letters.
For each test case, output a single string — the lexicographically smallest combination.
2ime brasilcalvao decria
abeiilmrs aaaccdeilorv
At the Institute of Meaningful Elevators (commonly known as IME), a student named Paim has been tasked with fixing its elevators (how ironic, I'd say). When he showed up to fix them, he found out something weird: the circuits are from out of this world! The circuit is composed of nodes that have connections, with each having a unique numerical identifier. He discovered, by reading the elevator's ancient manual, that in order for the circuit to be working, all identifiers from $$$1$$$ to $$$k$$$ can be reached by starting at node $$$1$$$ and following the connections; no identifier out of this range is reachable as well. This can be thought of as a permutation of size $$$k$$$, as, if you get all the nodes reachable from $$$1$$$, all identifiers from $$$1$$$ to $$$k$$$ will be present once.
The circuit that Paim is working with already has some connections; however, they don't necessarily respect the instructions in the manual. Given that he only has a pair of pliers to fix this issue, he's only able to remove existing connections from the circuit. Since having more nodes connected means a better functioning elevator, Paim wants to find out what's the maximum number of nodes that'll still be in use after efficiently fixing the circuit. More formally, he wants to find out what's the size of the largest subgraph, whose identifiers form a permutation. Can you help him figure this out?
This is a legitimate image from the Institute of Meaningful Elevators The first line contains two integers, $$$n$$$, $$$m$$$, $$$(1 \leq n \leq 2 \times 10^5)$$$, $$$(0 \leq m \leq \min(\frac{n \times (n - 1)}{2}, 4 \times 10^5)$$$ — the amount of nodes and the amount of connections.
The second line contains $$$n$$$ integers $$$a_i$$$, $$$(1 \leq a_i \leq 10^7)$$$ — the identifier of node $$$i$$$. It is guaranteed that each identifier is distinct and that there exists a node with the identifier $$$1$$$.
The next $$$m$$$ lines contain two integers, $$$u$$$, $$$v$$$, $$$(1 \leq u, v \leq n, u \neq v)$$$ — representing a connection. It is guaranteed that two nodes aren't connected together more than once.
Print one integer, the maximum number of nodes that'll still be in use after fixing the circuit.
5 6 4 3 10 2 1 1 2 4 5 2 3 2 4 1 3 2 5
4
You can see that if you don't remove connections $$$(1, 2)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, the nodes $$$1$$$, $$$2$$$, $$$4$$$, $$$5$$$ will remain connected. Their identifiers are, respectively, $$$4$$$, $$$3$$$, $$$2$$$, $$$1$$$, which does indeed form a permutation of size $$$4$$$.
Competitive frisbee has, for some reason, become a thing now, and everyone's trying to be the best. For this reason, Johannes and Asfora have begun practicing this sport, and their practice routine goes something like this: both of them start at the same point, and Johannes throws the frisbee in some direction while Asfora begins running after the frisbee. They're intelligent, so when the frisbee is thrown, Asfora is able to precisely pinpoint where it's going to land and begins running towards that direction.
Since they've been training a lot, Asfora has gotten lazy and will now only run if he's certain that he'll reach the frisbee. He doesn't have time to do this calculation, so he asks you for help in knowing whether he'll run or not. When Johannes throws a frisbee, Asfora is able to tell you the coordinates in which it'll land in relation to the starting point, how fast he's able to run at that moment, and how long it takes for the frisbee to reach the ground. Will you be able to help him?
The first line contains a single integer $$$T$$$, $$$(1 \leq T \leq 10^5)$$$ — the number of test cases.
Each test case is one line and contains four integers, $$$x$$$, $$$y$$$, $$$v$$$, $$$t$$$, $$$(1 \leq x, y \leq 10^4)$$$, $$$(1 \leq v, t \leq 10^2)$$$ — the $$$x$$$ and $$$y$$$ position where the frisbee lands in relation to the starting point, the speed in which Asfora runs, and the amount of time it took for the frisbee to reach the ground.
For each test case, output YES if he can get to the frisbee in the elapsed time, or NO otherwise.
24 2 3 106 8 1 9
YES NO
Recently, Calheiros has been really excited about Mr. Megamind's class on graphs, so much so that it's been the only thing on his mind. This has gotten so out of hand that it started seeping into his dreams, and one day into a nightmare of his. Trapped in this nightmare, the professor appeared in it and gave him a problem to solve in order to escape. However, due to him being in panic, he's unable to think straight in order to solve it.
The professor wants to connect $$$n$$$ cities together, by using some combination of $$$m$$$ roads that he's able to build. Each road will link two cities together, and it has a unique cost associated with it; the cost of each road is pairwise distinct. As such, the professor wants to know two things: what's the lowest amount that has to be spent to link all the cities and what's the largest direct distance between two cities after building the roads. Luckily, out of nowhere, you appear in this dream and are able to assist. Will you be able to save Calheiros from this nightmare?
The first line contains two integers, $$$n$$$ and $$$m$$$, $$$(2 \leq n \leq 10^5)$$$, $$$(n - 1 \leq m \leq min(3 \times 10^5, \frac{n \times (n - 1)}{2})$$$ — the number of cities and roads, respectively.
Each of the next $$$m$$$ lines will contain the description of a road. Each line contains three integers $$$u_i$$$, $$$v_i$$$, $$$c_i$$$, $$$(1 \leq u_i, v_i \leq n, u_i \neq v_i)$$$, $$$(1 \leq c_i \leq 10^9)$$$ — a road that can be built to connect cities $$$u_i$$$ and $$$v_i$$$ with cost $$$c_i$$$.
It is guaranteed that each $$$c_i$$$ is pairwise distinct and that you can form a connected graph with the roads given.
Print two lines of output. On the first line, print the total cost of building the roads. On the second line, print the largest distance between two cities.
4 5 1 2 4 2 3 6 1 3 8 3 4 10 4 2 7
17 2
You can easily see that if you choose the edges that connect the cities $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(4, 2)$$$, all of the cities will be connected and the lowest cost has been used to connect them. Besides that, you can notice that the largest distance between two cities in this graph is two.
Recently, Braga and Hamilton created their own language consisting only of lowercase Latin letters so they can speak about people without them knowing. However, Braga noticed that Hamilton was having trouble spelling some words of this very exotic language. Since Braga is a very proactive student, he decided to help Hamilton by creating an algorithm to autocomplete after he types some initial letters.
The logic behind his algorithm is very simple: given the string $$$s$$$ that Hamilton typed, the algorithm returns the smallest word in SupersecretLanguage that has $$$s$$$ as a prefix.
Hamilton was not convinced this would really speed up his writing...
Can you please return the number of characters that Braga's algorithm will type in?
The first line contains two integers, $$$n$$$ $$$(1 \leq n \leq 10^4)$$$, $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ - the number of words in SupersecretLanguage and the number of queries that will be made.
The next $$$n$$$ lines each contain one string $$$s_i$$$ $$$(1 \leq |s_i| \leq 10^5)$$$, a word in the dictionary. These words are not necessarily ordered.
The next $$$q$$$ lines each contain one string $$$r_i$$$ $$$(1 \leq |r_i| \leq 10^5)$$$, the words Hamilton typed into the autocompleter.
It is guaranteed that $$$\displaystyle\sum_{i = 0}^n |s_i| \leq 4\cdot10^5$$$ and $$$\displaystyle\sum_{i = 0}^q |r_i| \leq 10^6$$$.
For each string $$$r_i$$$ output the number of characters that will be autocompleted by Braga's algorithm. If $$$r_i$$$ is not a prefix to any string in the dictionary, print $$$-1$$$.
3 4 cosenza cosenzazinho brasil cos cosenzazin brasil ime
4 2 0 -1
3 6 flamengo fluminense jovemaocompletardezoitoanosvocepode fla fl flu mengo fluminense jovem
5 6 7 -1 0 30
Vieira is such a good math student that some of his superiors took notice of this skill. Captain Shoba was really impressed by the calculations that he was able to do, and so whenever he could, he'd try to test Vieira's skills. Usually, the captain would give Vieira an array and an integer $$$x$$$; Vieira would promptly say the indices of two numbers whose multiplication would result in $$$x$$$.
Since he was responding to the captain's queries in less than one femtosecond, the captain thought of another way to test him. Now, instead of saying two indices, Vieira would have to discover how many pairs of indices exist so that the multiplication of the numbers results in $$$x$$$. He's tired of the captain's shenanigans and asks you to make a program to respond for him.
The first line contains two integers, $$$n$$$, $$$x$$$, $$$(1 \leq n \leq 10^6)$$$, $$$(1 \leq x \leq 10^8)$$$ — the length of the array and the number that should be multiplied to.
The second line contains $$$n$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq 10^4)$$$ — the array $$$a$$$.
Print a single integer — the number of pairs $$$i$$$, $$$j$$$, $$$(1 \leq i \lt j \leq n)$$$, such that $$$a_i \times a_j = x$$$.
4 10 5 2 3 5
2
Henrique Holanda (not to be confused with the ICPC world finalist Davi Holanda) loves running and has been training a lot for a physical evaluation, known as the Training Assessment on Fatiguing (something like that, I can't seem to remember), commonly called TAF. The TAF is divided into two parts; first, he needs to run from one point in the city to another and then do as many pushups as possible. For some reason, the organizers of this event have forgotten how to use a stopwatch and so the time it takes to complete the first part doesn't really matter.
Because of this, Henrique Holanda scouts how the first part is going to happen and finds out that there are $$$n$$$ possible crossroads he can go through in order to get to the finish line; he begins running at crossroad $$$1$$$ and finishes at crossroad $$$n$$$. Besides this, there are $$$m$$$ roads that arbitrarily connect two different crossroads, and since he wants to finish the running section as least fatigued as possible, instead of assigning a distance to it, he assigns a tiredness factor to it.
He measures his tiredness factor the following way: when he begins running, his current tiredness factor is $$$1$$$. When he goes through a road to go from one crossroad to another, he multiplies his own tiredness factor by the value associated with that road. Can you help him find out what's the minimum tiredness factor he's able to end the running section with? Since the answer can get really big, he wants the logarithm base seven of the answer.
The first line contains two integers, $$$n$$$, $$$m$$$, $$$(1 \leq n \leq 10^5)$$$, $$$(n - 1 \leq m \leq \min(3 \times 10^5, \frac{n \times (n - 1)}{2}))$$$ — the number of crossroads and the number of roads.
Each of the next $$$m$$$ lines will contain the description of a road. Each line contains three integers, $$$u_i$$$, $$$v_i$$$, $$$c_i$$$, $$$(1 \leq u_i, v_i, \leq n, u_i \neq v_i)$$$, $$$(1 \leq c_i \leq 10^9)$$$ — a road connecting crossroads $$$u_i$$$ and $$$v_i$$$ that multiplies his tiredness factor by $$$c_i$$$.
For each test case, output a real number — the logarithm base seven of the tiredness factor. That being, if Henrique Holanda's tiredness factor is $$$k$$$, you should print $$$log_7(k)$$$. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$, that being if your answer is $$$a$$$ and the jury's is $$$b$$$, then the judge will check if $$$\frac{|a - b|}{max(1, b)} \leq 10^{-6}$$$.
5 7 1 2 4 2 3 6 1 3 5 4 5 8 4 2 3 3 5 7 2 5 16
1.827087475346916