As every March 29th, Juan leaves his house and heads towards the home of Jacobo, his best buddy, to celebrate the date in style, as one would expect. However, a malicious step stands in his way. In an unexpected turn of events, the step causes Juan to fall, a spectacle both dramatic and embarrassing, while it lets out a stony laugh that fits its role as the protagonist's arch-nemesis. As a result of the fall, Juan breaks his femur in two different places, resulting in three fragments of lengths $$$a$$$, $$$b$$$, and $$$c$$$.
While waiting for medical services, Juan wonders if he could form a non-degenerate triangle with these bone fragments.
The input consists of several cases. Each case consists of three natural numbers $$$a, b, c$$$ separated by spaces. Each case ends with a newline.
Print one line per case with the word "si" if Juan can form a non-degenerate triangle with the bone fragments and the word "no" otherwise.
$$$0 \leq a, b, c \lt 10^8$$$
3 4 5 9 2 4
si no
Bureaucracy is synonymous with boredom, but you will have no choice but to face it if you want to collect your scholarship before the year ends. To this end, you head to the ministerial offices to try your luck with the procedures, to see if you can obtain the necessary supporting document.
There are $$$n$$$ secretarial windows in a row, one behind the other. At each window, you can carry out a procedure, which consists of presenting document A to obtain another document B. The procedure can only be performed if you have document A, and this document is retained after the procedure. However, once you pass a window (whether or not a procedure is performed at it), you cannot go back due to legal subtleties that are not relevant here. Once you pass the last window, it will no longer be possible to return to the first, as the offices will have closed.
Initially, you have only one document. Given the initial document and the desired one, what is the minimum number of procedures possible?
The input starts with an integer $$$T$$$, the number of test cases. Each case begins with $$$n$$$ and $$$m$$$, the number of windows and the total number of documents that exist. The documents are numbered from $$$0$$$ to $$$m-1$$$, with $$$0$$$ being the initial document and $$$m-1$$$ being the desired document. Following are $$$n$$$ lines with two integers $$$a_i$$$ $$$b_i$$$, indicating that at the $$$i$$$-th window, document $$$a_i$$$ can be presented to obtain document $$$b_i$$$.
For each case, print a line with the minimum number of procedures to be performed. If it is impossible to obtain the desired document, print "Imposible" instead (without quotes).
Case 1 (5 points): $$$1 \leq n \leq 10^3$$$, $$$m = 2$$$.
Case 2 (5 points): $$$n = 2$$$, $$$1 \leq m \leq 10^3$$$.
Case 3 (36 points): $$$1 \leq n,m \leq 10^3$$$.
Case 4 (54 points): $$$1 \leq n,m \leq 10^6$$$.
4 2 3 0 1 1 2 2 3 0 2 1 0 2 4 1 3 0 1 6 7 0 3 3 2 4 6 3 5 2 5 5 6
2 1 Imposible 3
After receiving advertisements from local restaurants, María decides to spend the afternoon doing her favorite hobby: removing unwanted advertisements from mailboxes. For this reason, she decides to go with a group of friends to Badajoz to eliminate the spam mail. The location of the mailboxes can be modeled as a one-dimensional line. The mailboxes are located at positions $$$l_i$$$, while María's friends are initially at positions $$$p_i$$$. Every second, María's friends can move one unit to the right or to the left. If their position coincides with that of a mailbox, they can instantly remove the advertisement from that mailbox. Your goal is to find the minimum time that María and her friends need to remove all the advertisements if they distribute the work optimally. At the same time, there can be two people in the same position, and there can also be more than one mailbox at the same position.
The input starts with an integer $$$t$$$, the number of cases. Following this are the cases, each starting with two integers $$$n$$$ and $$$m$$$: the number of mailboxes and the number of María's friends (including her). The next $$$n$$$ lines describe (with one integer each) the positions of the mailboxes (the first lines), and the following $$$m$$$ lines describe the positions of María's friends (the next lines).
Print $$$t$$$ lines, each containing an integer, the minimum time that María and her friends need to clean Badajoz of spam mail.
Case 1: $$$n = 1$$$, $$$1 \leq m \leq 10^5$$$, $$$0 \leq l_i, p_i \leq 10^{18}$$$ (7 points)
Case 2: $$$1 \leq n \leq 10^5$$$, $$$m = 1$$$, $$$0 \leq l_i, p_i \leq 10^{18}$$$ (12 points)
Case 3: $$$1 \leq n \leq 20$$$, $$$1 \leq m \leq 20$$$, $$$0 \leq l_i, p_i \leq 10^9$$$ (21 points)
Case 4: $$$1 \leq n \leq 500$$$, $$$1 \leq m \leq 500$$$, $$$0 \leq l_i, p_i \leq 10^9$$$ (26 points)
Case 5: $$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^5$$$, $$$0 \leq l_i, p_i \leq 10^{18}$$$ (34 points)
2 3 2 0 3 8 1 5 1 2 6 3 10
4 3
You want to organize a soccer match among $$$n$$$ players. You need to separate the players into two teams, and all players have agreed that they do not care about the number of players in each team. However, you know that there are people who cannot even stand to see each other, let alone play on the same team. In fact, you know that $$$m$$$ distinct pairs of players hate each other a certain amount $$$h$$$ (measured in phobios, the usual unit of hate). With this information, you must find the minimum number $$$k \geq 0$$$ such that two distinct teams can be formed where the hate between any two people in the same team is less than or equal to $$$k$$$.
The input consists of multiple cases. The first line will contain a natural number $$$t$$$, the number of cases.
For each case:
- The first line will contain two integers $$$n, m$$$, the number of players, and the number of pairs that hate each other.
- The following $$$m$$$ lines will contain three integers $$$u_k, v_k, h_k$$$, the two players and how much they hate each other. No two pairs $$$u_k$$$ and $$$v_k$$$ will be repeated.
The output should be a natural number for each case, the minimum number $$$k \geq 0$$$ such that two distinct teams can be formed where the hate between any two people in the same team is less than or equal to $$$k$$$.
$$$1 \leq t$$$
$$$1 \leq u_k, v_k \leq n, \, u_k \neq v_k$$$
32 points: $$$2 \leq n \leq 2000$$$, $$$0 \leq m \leq 2000$$$, $$$1 \leq h_k \leq 2000$$$
17 points: $$$2 \leq n \leq 2000$$$, $$$0 \leq m \leq 2000$$$, $$$1 \leq h_k \leq 10^9$$$
51 points: $$$2 \leq n \leq 200000$$$, $$$0 \leq m \leq 200000$$$, $$$1 \leq h_k \leq 10^9$$$
2 3 3 1 2 3 2 3 2 1 3 1 4 6 1 2 5 1 3 4 1 4 4 2 3 6 2 4 7 3 4 2
1 4