A sequence $$$a$$$ of length $$$n$$$ is called palindromic if $$$a_i=a_{n-i+1}$$$ for all $$$1 \leq i \leq n$$$.
You are given the sequence $$$b$$$ of $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$. Determine whether it is possible to increase exactly one element of $$$b$$$ by $$$1$$$ in such a way that the resulting sequence will not be palindromic.
The first line of the input contains one integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the length of the input sequence. The $$$i$$$-th of the following $$$n$$$ lines contains one integer $$$b_i$$$ ($$$1 \leq b_i \leq 1000$$$) — the $$$i$$$-th element of sequence $$$b$$$.
If it is possible to increase exactly one $$$b_i$$$ by $$$1$$$ and get the sequence that is not palindromic, print 1 in the only line of the output. Otherwise, print 0.
1 1
0
2 20 21
1
Знатно покутив в баре на Некрасова, Глеб возвращается в отель Индиго вдоль Литейного проспекта.
Будем считать, что Глеб находится в точке 0 вдоль проспекта, а отель — в точке $$$L$$$. Также имеются $$$N$$$ переходов со светофорами, $$$i$$$-й переход находится в точке $$$X_i$$$ ($$$0 \lt X_1 \lt X_2 \lt \ldots \lt X_n \lt L$$$). Чтобы попасть домой, Глебу нужно пройти весь проспект и в какой-то момент времени его перейти.
Все светофоры имеют одинаковый такт, то есть горят $$$G$$$ секунд зелёным и $$$R$$$ секунд красным. Синхронизации нет, у всех светофоров случайный равновероятно выбранный сдвиг такта. Глеб знает числа $$$G$$$ и $$$R$$$, но не знает сдвиги.
На каждом светофоре есть часы, которые показывают состояние такта. Глеб видит часы, как только оказывается в точке около светофора. Глеб обладает памятью, так что увиденное состояние уже не забывает.
Глеб двигается прогулочным шагом со скоростью один метр в секунду. Все числа в задаче целые (и сдвиги тактов светофоров — тоже).
Также известно, что переходы расположены не слишком часто — на любом отрезке проспекта длиной не более $$$G+R$$$ метров находится не более двух переходов.
Чему равно математическое ожидание времени в пути до Индиго, если Глеб действует оптимально. Глеб может в любой момент времени перемещаться в любых направлениях, ходить вперёд и назад, переходить улицу произвольное число раз. Переход улицы занимает $$$B$$$ секунд. Переходить улицу можно только по переходам и только на зелёный свет при условии, что он горит в течение всего времени перехода.
В первой строке записаны числа $$$N$$$ ($$$1 \le N \le 10^5$$$), $$$L$$$ ($$$1 \le L \le 10^9$$$), $$$G$$$ ($$$1 \le G \le 10^9$$$), $$$R$$$ ($$$1 \le R \le 10^9$$$), $$$B$$$ ($$$1 \le B \le G$$$). Далее следуют $$$N$$$ строк с координатами переходов в порядке возрастания. В $$$i$$$-й из них записано число $$$X_i$$$ ($$$0 \lt X_i \lt L$$$).
Выведите одно число — математическое ожидание времени в пути до Индиго при условии оптимальных действий Глеба. Абсолютная или относительная погрешность ответа не должна превышать $$$10^{-9}$$$.
1 10 2 4 1 2
12.6666666666667
2 820 30 50 23 400 810
866.0250000000000
3 100 20 50 1 10 15 85
107.6141690962099
Gleb has socks of $$$n$$$ distinct colors. In particular, he owns $$$a_i$$$ pairs of socks of color $$$i$$$. He wears these pairs one after the other till there are no more clean pairs of socks left, then it is time for The Great Wash.
Gleb puts all of his socks into a washing machine with a drying option and waits for an two-three hours. Now, the worst part begins. Gleb needs to assemble socks in pairs again. To simplify the process we assume that all socks of the same color are indistinguishable. In other words, any two socks of the same color can form a pair. Obviously, Gleb never forms a pair of socks from two of distinct color.
Gleb performs the following process. We denote the set of all socks inside the washing machine as $$$A$$$ and the set of all socks that haven't been matched yet and lie near Gleb as $$$B$$$.
While waiting for wash-and-dry cycle to finish Gleb wonders, what is the expected time the process described above will take? The last time he took part in a programming competition was several years ago, so he needs your help to find out the answer.
The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — the number of distinct colors of socks Gleb possesses.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 5$$$), the $$$i$$$-th of them denoting the number of pairs of socks of color $$$i$$$ in Gleb's wardrobe.
Print one real value — the expected number of seconds it will take Gleb to complete the whole process if he follows the steps given. Your answer will be accepted if its absolute or relative error does not exceed $$$10^{-6}$$$.
1 1
3.000000000
1 3
9.000000000
2 1 1
7.000000000
3 3 2 2
29.571428571
There are $$$n$$$ children numbered $$$1, 2, \dots, n$$$. They stand in a circle. Each child has a bag with non-empty set of distinct positive integers.
As a part of Christmas celebration, children want to play a game of the following rules:
Help children win the game or find out that this is impossible.
The first line of the input contains a single integer $$$n$$$ ($$$2 \leq n \leq 500\,000$$$), the number of children.
The $$$i$$$-th of the following $$$n$$$ lines contains the description of the $$$i$$$-th child' bag. The first integer of each description is $$$k_i$$$ ($$$1 \leq k_i$$$) — the number of integers in the bag. Then follow $$$k_i$$$ integers $$$a_{ij}$$$ ($$$1 \leq a_{ij} \leq 10^{9}$$$), which describe the content of the bag.
The total size of all bags is constrained as $$$\sum k_i \leq 500\,000$$$.
It is guaranteed that all integers in each particular bag are distinct.
If there is no way for children to win the game, print -1 in the only line of the output. Otherwise, print $$$n$$$ integers, $$$x_1, x_2, \dots, x_n$$$, where $$$x_i$$$ is the integer that the $$$i$$$-th child must pull out of her bag and pass to the next child in order to succeed in the game.
3 2 1 4 2 4 3 2 3 1
1 4 1
For any positive integer $$$y$$$ we define $$$A(y)$$$ as the set of all positive integers that are anagrams of $$$y$$$. Formally, we consider the sequence of all digits of $$$y$$$ in decimal representation without leading zeroes, then we apply all possible permutations to this sequence. For any permutation we throw away leading zeroes and assemble digits back to an integer. All integers that can be obtained that way belong to $$$A(y)$$$. For example, for $$$2021$$$ set $$$A(2021)$$$ consists of integers $$$122$$$, $$$212$$$, $$$221$$$, $$$1220$$$, $$$2120$$$, $$$2210$$$, $$$1202$$$, $$$2102$$$, $$$2201$$$, $$$1022$$$, $$$2012$$$ and $$$2021$$$. Note, that set $$$A(y)$$$ always contains $$$y$$$, thus it is never empty.
For any positive integer $$$x$$$ we define $$$S(x)$$$ as the set of all positive integers $$$z$$$ such that greatest common divisor of all integers in $$$A(z)$$$ equals $$$x$$$.
You are given the integer $$$n$$$, find the minimum integer $$$z$$$ in $$$S(x)$$$, or determine that $$$S(x)$$$ is empty.
The first line of the input contains one integer $$$t$$$ ($$$1 \leq t \leq 50$$$) — the number of the test cases.
Each test case data consists of one integer $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$).
For each test case, print one integer on a separate line. If the corresponding set $$$S(n)$$$ is empty, print -1. Otherwise, print minimum element of $$$S(n)$$$.
2 12 2021
48 -1
In graph theory, a cactus is a connected undirected graph in which any two simple cycles have at most one vertex in common.
Given an integer $$$n$$$, build a connected graph with $$$n$$$ vertices that is not a cactus. Note that your graph can't have self-loops or multiple edges. The number of edges in your graph should be minimum possible.
The input consists of a single integer $$$n$$$ ($$$2 \le n \le 1000$$$).
If there is no connected graph of $$$n$$$ vertices without self-loops and multiple edges that is not a cactus, print -1 in the only line of the output. Otherwise, first print positive integer $$$m$$$ — the number of edges in your graph. Then print $$$m$$$ lines, each containing two integers — edges of the resulting graph. Use consecutive integers $$$1, 2, \ldots, n$$$ to enumerate the vertices of the graph.
If there are more than solutions with minimum number of edges, print any of them.
3
-1
One of the greatest e-sport events, The Invitational TOAD-3 Championship, will feature $$$16$$$ best teams in the world. In order to prolong the fascinating event and acquire more money from advertising a double-elimination tournament scheme will be used.
First, all teams are ordered by their rating and the $$$i$$$-th team in the sorted list plays versus the team at position $$$(17-i)$$$. The winner of each of these matches goes to the winners' bracket, the loser goes to the losers' bracket.
Participants of the winners' bracket continue to play a single-elimination tournament, except that the losers of each round "drop down" into the losers' bracket.
Each round of the loser's bracket is conducted in two stages; a minor stage followed by a major stage. Both contain the same number of matches which is the same again as the number of matches in the corresponding round of the winners' bracket. If the minor stage of a looser's bracket round contains $$$2^k$$$ matches, there will be $$$2^k$$$ winners. Meanwhile, the $$$2^k$$$ matches in the corresponding round of the winners' bracket will produce $$$2^k$$$ losers. These $$$2^{k+1}$$$ teams will then form pairs for $$$2^k$$$ matches of the corresponding major stage of the looser's bracket. At this stage of the round, looser of the winners' bracket round can play only against winners of the minor stage of the looser's bracket.
In both brackets, before each round opponents are chosen at random to form pairs. Same apply to the process of forming pairs of type "loser from winners' bracket versus winner of the minor stage from the losers' bracket" at the major stages of the losers' bracket rounds.
All players who are eliminated from the same stage are considered to share the same position in the resulting ranking.
Below is the scheme of how the double-elimination tournament for 16 teams is held.
You are given the list of teams with the results of all matches played by this team during the tournament in chronological order. Determine the final place for each team.
The input contains $$$16$$$ lines.
Each line consists of two strings — the team name $$$t$$$ made up of lowercase English letters ($$$1 \le |t| \le 50$$$) and the string $$$G$$$ with the outcomes of all games this team has played. String $$$G$$$ consists of digits 1 and 0 only. If the $$$i$$$-th character of this string equals 1 it means that this team won its $$$i$$$-th match on the tournament. If the $$$i$$$-th character of this string equals to 0, it means that this team lost its $$$i$$$-th match on the tournament.
You may assume that all team names are distinct and that the distribution of wins and losses correspond to some correctly held double-elimination tournament for those teams.
Print 16 lines. Each line should contain the notation for place: one integer if the place is not shared, and two integers separated by single '-' — the highest and the lowest if the place is shared, followed by the team name.
Teams shall be listed by their places in increasing order. If several teams share a place, sort those teams by the name lexicographically. See sample output for further clarification.
escmraeett 11100 neigulsievse 010 noet 1010 nduymianegt 00 psimraiett 10111111 ustprriov 1100 yccnrieuwq 010 go 1010 agmiicnigv 10110 ctosaasetb 00 sugtacmiivnngi 11010 hpaenlte 00 lggsdp 11110 taincf 010 ainlclea 010 asmtaeert 00
1 psimraiett 2 lggsdp 3 escmraeett 4 sugtacmiivnngi 5-6 agmiicnigv 5-6 ustprriov 7-8 go 7-8 noet 9-12 ainlclea 9-12 neigulsievse 9-12 taincf 9-12 yccnrieuwq 13-16 asmtaeert 13-16 ctosaasetb 13-16 hpaenlte 13-16 nduymianegt
Given the string $$$S$$$, consisting of letters 'I', 'V', 'X', 'L', 'C', 'D' and 'M'. Your task is to split the string to the minimum number of strings that are:
The following table from Wikipedia displays how the Roman Numerals are written:
| Individual decimal places | Thousands | Hundreds | Tens | Units |
| 1 | M | C | X | I |
| 2 | MM | CC | XX | II |
| 3 | MMM | CCC | XXX | III |
| 4 | CD | XL | IV | |
| 5 | D | L | V | |
| 6 | DC | LX | VI | |
| 7 | DCC | LXX | VII | |
| 8 | DCCC | LXXX | VIII | |
| 9 | CM | XC | IX |
The first line of the input consists of one integer $$$n$$$ — length of the string ($$$1 \leq n \leq 100\,000$$$).
The second line contains the string of length $$$n$$$, consisting of letters 'I', 'V', 'X', 'L', 'C', 'D' and 'M'.
In first line of the output print one integer $$$k$$$ — the minimum number of correct roman palindromes that can form the given string being concatenated. Then print $$$k$$$ lines, each line containing one string — a correct Roman numeral that is a palindrome, such as the concatenation of all $$$k$$$ lines in the order of output is equal to the given string.
If there is more than one solution, print any of them.
5 MMXXI
3 MM XX I
Given $$$n$$$ points $$$p_1, p_2, \ldots p_n$$$ in the two-dimensional Euclidean plane, calculate the total pairwise Euclidean distance between them. Simple as that.
Recall that Euclidean distance between two points $$$a = (x_1, y_1)$$$ and $$$b = (x_2, y_2)$$$ is defined as follows:
$$$$$$ \operatorname{dist}(a, b) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} $$$$$$
The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 500\,000$$$), the number of points.
The $$$i$$$-th of the following $$$n$$$ lines contains a pair of integers $$$x_i$$$, $$$y_i$$$ ($$$-10^6 \leq x_i, y_i \leq 10^6$$$), the coordinates of $$$p_i$$$.
Output the value of $$$\sum\limits_{i \lt j} \operatorname{dist}(p_i, p_j)$$$. Your answer will be considered correct if its relative or absolute error does not exceed $$$10^{-2}$$$.
3 -1 2 2 2 -1 -2
12.0000000000
4 0 0 2 0 0 2 2 2
13.6568542490
In the first sample test the pairwise distances are $$$3$$$, $$$4$$$ and $$$5$$$.
In the second sample test the pairwise distances are $$$2, 2, 2, 2, 2\sqrt{2}, 2\sqrt{2}$$$.
Полное решение будет оценено в 3 балла.
В игре «Подземелья и радуги» используются кубики разной формы и с разным количеством граней. Игровой процесс заключается в перемещении по нескольким подземельям и выполнении различных действий. Суммарно в игре $$$n$$$ состояний: различные положения, имеющиеся предметы и т. д. Для каждого из состояний правила игры определяют, какой игровой кубик нужно бросить, чтобы узнать, в какое состояние перейдет игра (или останется в том же состоянии). Игровой кубик может иметь более $$$n$$$ граней, поэтому дополнительно правила определяют, сколько граней этого кубика соответствует переходам в каждое состояние.
Например, в игре с тремя состояниями в одном из них может быть доступен кубик с пятью гранями. Для перехода в состояние 1 будут использоваться две его грани, в состояние 2 — одна грань, а в состояние 3 — две грани.
Игроки начинают в состоянии 1 и игра длится $$$k$$$ раундов. Для того, чтобы игра закончилась изумительным финалом, игроки должны в последнем раунде попасть в состояние $$$s$$$. Попадания в это состояние в промежуточных раундах не имеют значения.
Опытный ведущий знает вероятности выпадения каждой грани каждого кубика. В каждом раунде он может выбирать, какие грани кубика будут соответствовать каким исходам, то есть ведущий назначает для каждой грани кубика переход в состояние на следующий раунд. Если игроки попали в одно и то же состояние несколько раз, он может сделать разный выбор в каждом случае.
Ведущий хочет, чтобы игра закончилась изумительным финалом с максимальной вероятностью. Вычислите эту вероятность при оптимальных действиях ведущего.
В первой строке дано число состояний $$$n$$$ ($$$2 \le n \le 1000$$$), число раундов игры $$$k$$$ ($$$1 \le k \le 100$$$) и номер состояния с изумительным финалом $$$s$$$ ($$$1 \le s \le n$$$).
В следующих $$$n$$$ строках даны описания кубиков и правила переходов из каждого состояния. Первые $$$n$$$ чисел строки $$$i$$$ задают количество граней кубика $$$F_{ij}$$$ ($$$0 \le F_{ij} \le 1000$$$), которые соответствуют переходам из состояния $$$i$$$ в каждое из $$$n$$$ состояний. Далее в этой же строке дан знаменатель $$$Q_i$$$ ($$$\sum_j F_{ij} \le Q_i\le 10^6$$$) вероятностей выпадений граней кубика. А за ним $$$\sum_j F_{ij}$$$ числителей $$$P_{ij}$$$ ($$$1 \le P_{ij} \le Q_i$$$) вероятностей выпадения каждой грани кубика.
Общее число граней каждого кубика удовлетворяет ограничениям $$$2 \le \sum_j F_{ij}\le 1000$$$, а сумма вероятностей выпадения всех граней равна $$$1$$$.
Выведите максимальную вероятность получения изумительного финала при оптимальных действиях ведущего с абсолютной погрешностью, не превосходящей $$$10^{-9}$$$.
2 1 2 1 1 3 1 2 1 1 3 2 1
0.666666666667
3 3 3 1 1 0 3 2 1 0 1 1 3 2 1 1 0 1 3 2 1
0.592592592593
2 2 2 2 1 4 1 2 1 2 1 4 1 1 2
0.5
The Kingdom of Berland is great and glorious, but it is currently ruled by a powerful and peevish king Vlad who got old and now sees treasons and plots all around him. He now suspects his two sons in planning a coup, so he decided to establish his control over all their communications.
The Kingdom of Berland is formed by $$$n$$$ cities connected by $$$m$$$ bidirectional roads in a way that makes it possible to get from any city to any other city using these roads only. The elder son of King Vlad lives in city $$$1$$$, while the younger son lives in city $$$n$$$.
In order to control all messengers who run between city $$$1$$$ and city $$$n$$$ Vlad wants to pick some cities and establish a secret police department in each of them. It turns out that no matter how powerful you are, you are not able to keep all the things secret. If city $$$v$$$ has a police department established in it, the mayor of this city somehow becomes aware of this. Moreover, the mayor of any city that is connected to $$$v$$$ by a direct road becomes aware of this police departments as well.
Of course, the King wants to keep his sons unaware of his new secret police. Therefore he has three limitations.
You don't want to help King Vlad in his malicious games, but the problem itself looks nice so you want to find the optimal answer just for fun.
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.
Then follow $$$t$$$ test cases' descriptions. Each test case description starts with two integers $$$n$$$ and $$$m$$$ ($$$3 \leq n \leq 300$$$, $$$2 \leq m \leq \frac{n \cdot (n - 1)}{2} - 1$$$) — the number of cities and the number of roads in the kingdom of Berland. Each of the following $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$), providing the indices of the cities connected by the $$$i$$$-th bidirectional road.
It is guaranteed that the sum of values of $$$n$$$ in all $$$t$$$ test cases doesn't exceed $$$300$$$.
For each test it is guaranteed that each road connects two distinct cities, no two roads connect the same pair of cities and no road connects city $$$1$$$ with city $$$n$$$.
For each of $$$t$$$ tests print two lines. The first line of the output should contain two integers $$$a$$$ and $$$k$$$, where $$$a$$$ is the answer, i.e. the minimum possible number of city mayors to be aware about at least one secret police department, and $$$k$$$ is the number of secret police departments to be establish in order to achieve answer $$$a$$$. The next line should contain $$$k$$$ distinct indices $$$x_1, x_2, \ldots, x_k$$$ ($$$1 \lt x_i \lt n$$$), providing where exactly to place these secret police departments in the optimal answer. If there are several optimal answers, print any of them.
3 3 2 1 2 2 3 4 4 1 2 2 4 1 3 3 4 13 18 1 2 1 3 1 4 2 5 3 5 3 6 4 6 5 7 6 7 7 8 7 9 8 12 8 11 9 11 9 10 12 13 11 13 10 13
3 1 2 4 2 2 3 5 1 7
With the speed of light are food technologies conquering cities and towns of Berland, and, especially, its gorgeous capital City N.
FoodBerry is the largest food delivery that operates in City N. Consider the city as a two-dimensional square with sides parallel to coordinate axis. The bottom left corner of this square has coordinates $$$(-10^{4}, -10^{4})$$$ and the top right corner has coordinates $$$(10^{4}, 10^{4})$$$. All coordinates are given in meters.
FoodBerry has one Super Large Warehouse located at $$$(0, 0)$$$ and $$$n$$$ dark stores (smaller warehouses), the $$$i$$$-th of them is located at point $$$(x_i, y_i)$$$. Each dark store has two types of delivery: by foot and by car. Delivery by foot can be used for all points that are located no more than $$$a$$$ meters from this dark store, while delivery by car can be used for up to $$$b$$$ meters distances ($$$a \leq b$$$, obviously). During one day each dark store is able to execute no more than $$$c$$$ deliveries. Moreover, due to the limitation of vehicles, no more than $$$d$$$ of these deliveries can be done by car ($$$d \leq c$$$).
Super Large Warehouse is located at $$$(0, 0)$$$ and is capable of performing any number of deliveries to any locations in the city. However, using this option is expensive and FoodBerry tries to avoid it to for as long as possible.
In this problem we are going to analyze one day of FoodBerry in City N. There were $$$m$$$ orders during that day, they are given in the order they were made and processed. The $$$i$$$-th order asks for the delivery to point $$$(x'_i, y'_i)$$$. For the purpose of this problem we introduce some bold assumptions.
Of course, each distribution is done with respect to limitations on distance and quantity of orders per dark store given by parameters $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$. If there is a distribution of orders that satisfies all the requirements and executes all the deliveries without using Super Large Warehouse, the scheduling program goes for it.
Assuming all distributions are made optimal, what is the minimum order index $$$i$$$ such that there will be no way to make a valid distribution without using Super Large Warehouse?
The first line of the input contains six integers $$$n$$$, $$$m$$$, $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$ ($$$1 \leq n, m \leq 500$$$, $$$1 \leq a \leq b \leq 30\,000$$$, $$$1 \leq d \leq c \leq 1000$$$). Here $$$n$$$ is the number of dark stores in City N, $$$m$$$ is the number of orders to process, $$$a$$$ is the maximum possible distance for delivery from dark store by foot, $$$b$$$ is the maximum possible distance for delivery from dark store by car, $$$c$$$ is the maximum possible total number of deliveries a dark store can execute a day, and $$$d$$$ is the maximum possible number of deliveries by car a dark store can execute a day.
Then follow $$$n$$$ lines containing two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10\,000 \leq x_i, y_i \leq 10\,000$$$) each — coordinates of dark stores.
Finally go $$$m$$$ lines with coordinates of orders. Each of them contains two integers $$$x'_i$$$ and $$$y'_i$$$ ($$$-10\,000 \leq x'_i, y'_i \leq 10\,000$$$).
Any points of the input can coincide, i.e. there can be two or more dark stores in the same point, two or more orders in the same point, a dark store and an order in the same point, a dark store or an order at point $$$(0, 0)$$$ and so on.
It is possible that some order is located out of reach of any dark store. Note that it is still possible to execute all the orders as FoodSberry has Super Large Warehous that is capable of doing any number of deliveries to any location in City N.
If it is possible to obey all the requirements and satisfy all $$$m$$$ orders without using Super Large Warehous, print -1 in the only line of the output.
Otherwise, print minimum possible index $$$i$$$ such that Super Large Warehouse is required to satisfy first $$$i$$$ orders.
1 3 1 3 2 1 1 1 2 1 2 2 1 2
3
3 6 1 1 2 2 0 1 -2 1 2 1 -1 1 1 1 0 2 0 0 -2 1 2 1
-1
There are $$$n$$$ crossings in Bytetown, connected with $$$m$$$ bidirectional roads. The $$$i$$$-th road connects crossings $$$u_i$$$ and $$$v_i$$$, has length of $$$l_i$$$ meters and a cost factor of $$$c_i$$$.
In order to ease the road traffic, a special fine system is used in Bytetown. You can drive with any speed and change the speed whenever you want. However, if the maximum speed during your travel along the road $$$i$$$ is $$$v$$$ meters per second, you should pay $$$v \cdot c_i$$$ dollars fine.
You live near the crossing $$$1$$$ and want to get to the crossing $$$n$$$ in no more than $$$T$$$ seconds. What is the smallest possible fine you will have to pay if you choose the route and the speed for each road optimally?
In the first line of the input there are three numbers $$$n$$$, $$$m$$$ and $$$T$$$ ($$$1 \leq n \leq 2000$$$, $$$1 \leq m \leq 100\,000$$$, $$$1 \leq T \leq 10^9$$$).
The $$$i$$$-th of the next $$$m$$$ lines contains four numbers $$$u_i$$$, $$$v_i$$$, $$$l_i$$$, $$$c_i$$$, describing the $$$i$$$-th edge according to the statement ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$, $$$1 \leq l_i, c_i \leq 10^9$$$).
It is guaranteed that it is possible to reach the crossing $$$n$$$ starting at the crossing $$$1$$$.
Print single real number — the smallest possible fine. Your answer will be considered correct if its relative or absolute error doesn't exceed $$$10^{-6}$$$.
3 3 100 1 3 100 100 1 2 100 24 2 3 100 24
96.0000000000
3 2 10 1 2 9 1 2 3 1 1000
119.8736659610
4 5 9 1 2 6 7 1 3 6 2 2 3 8 7 2 4 3 4 3 4 1 7
4.1478114200
You are given six positive integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$, $$$e$$$ and $$$f$$$. You need to find out whether there exists a triangle $$$ABC$$$ with the following properties.
If such triangle exists, find the minimum possible value of its perimeter.
The input consists of six lines, each containg one integer $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$, $$$e$$$ and $$$f$$$ ($$$1 \leq a, b, c, d, e, f \leq 1000$$$) respectively.
If there is no triangle satisfying all the properties, print -1. Otherwise, print one integer — the minimum possible perimeter of such triangle.
1 1 2 2 3 3
1
1 2 3 4 5 6
-1
1 2 2 3 3 1
-1
Заданы два дерева, на каждом стоит своя фишка. За один ход можно переместить обе фишки по своим деревьям на одно и то же расстояние (считается по числу рёбер в простом пути между стартовой и конечной вершинами). Требуется переместить пару фишек из заданной стартовой пары положений в конечную за минимальное число ходов.
В первой строке записаны числа $$$n_1$$$ ($$$1 \leq n_1 \leq 200\,000$$$), $$$n_2$$$ ($$$1 \leq n_2 \leq 200\,000$$$), $$$m$$$ ($$$1 \leq m \leq 200\,000$$$) — количество вершин в первом дереве, количество вершин во втором дереве и количество запросов. В следующих $$$n_1 - 1$$$ строках записаны пары чисел $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n_1$$$, $$$x_i \neq y_i$$$) — рёбра первого дерева. В следующих $$$n_2 - 1$$$ строках записаны пары чисел $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n_2$$$, $$$x_i \neq y_i$$$) — рёбра второго дерева. В следующих $$$m$$$ строках записаны запросы. Каждый запрос — это четвёрка чисел $$$s_1$$$ ($$$1 \leq s_1 \leq n_1$$$), $$$s_2$$$ ($$$1 \leq s_2 \leq n_2$$$), $$$t_1$$$ ($$$1 \leq t_1 \leq n_1$$$), $$$t_2$$$ ($$$1 \leq t_2 \leq n_2$$$) — стартовая позиция первой фишки на первом дереве, стартовая позиция второй фишки на втором дереве, финишная позиция первой фишки на первом дереве, финишная позиция второй фишки на втором дереве соответственно.
На каждый из $$$m$$$ запросов выведите по одному числу — минимальное количество ходов, необходимое, чтобы добраться из стартовой пары позиций в конечную. Если добраться невозможно, выведите в соответствующей строчке -1.
4 5 7 1 2 2 3 2 4 1 2 2 3 3 4 4 5 1 1 2 5 1 5 4 1 1 5 4 2 2 5 2 3 2 1 2 5 3 2 3 2 4 4 1 2
-1 2 -1 2 3 0 1