In Romania, a very popular location for a nice relaxing holiday is Vama Veche. This is a problem about a group of friends and their vacation here.
Because the friends were very relaxed, they were not able to make the calculations needed for splitting the bills. Thus, most of the time they decided to have someone pay and worry about it later. Now they owe money to each other and need to make some bank transfers in order to satisfy everyone. The only problem is that they are lazy and want to make the minimum amount of transactions in order to achieve this.
Formally, you have $$$N$$$ friends and $$$M$$$ conditions of $$$friend_x$$$ owes $$$friend_y$$$ an amount of money equal to $$$val$$$. You need to find the minimum amount of transactions needed so that each friend has no debt and no further money to receive.
The first line of the input contains the integers $$$N$$$ ($$$1 \leq N \leq 20$$$) and $$$M$$$ ($$$0 \leq M \leq N*(N-1)$$$), denoting the number of friends and the number of conditions.
Each of the following $$$M$$$ lines contains $$$3$$$ positive integers: $$$friend_x$$$, $$$friend_y$$$ and $$$val$$$ ($$$1 \leq friend_x, friend_y \leq N$$$, $$$friend_x \neq friend_y$$$, $$$1 \leq val \leq 10^5$$$), denoting that $$$friend_x$$$ owes $$$friend_y$$$ an amount of money equal to $$$val$$$. Each ordered pair of $$$(friend_x, friend_y)$$$ will appear at most once in the input.
On a single line, print the minimum number of transactions needed in order to satisfy all the friends.
3 4 1 2 10 2 1 5 2 3 10 1 3 10
2
4 3 1 2 15 1 3 15 1 4 15
3
3 3 1 2 10 2 3 10 3 1 10
0
In the first example, the minimum amount of transactions needed is $$$2$$$: $$$friend_1$$$ gives $$$friend_2$$$ $$$15$$$ dollars and $$$friend_2$$$ gives $$$friend_3$$$ $$$20$$$ dollars.
In the second example, the minimum amount of transactions needed is $$$3$$$: $$$friend_1$$$ gives $$$friend_2$$$ $$$15$$$ dollars, $$$friend_1$$$ gives $$$friend_3$$$ $$$15$$$ dollars and $$$friend_1$$$ gives $$$friend_3$$$ $$$15$$$ dollars.
In the third example, no transactions are needed.
Since the beginning of the AGM contest, the members of the committee have had a favourite game which we always play before the contest for good luck.
The game is played between $$$3$$$ players using $$$N$$$ cards. The game has perfect information, all the players know all the cards in the game. Each player has $$$N/3$$$ cards of the following types:
- $$$7$$$ - used to attack a turn
- $$$8$$$
- $$$9$$$
- $$$10$$$ - equals to a point
- $$$A$$$ - equals to a point
- $$$J$$$
- $$$Q$$$
- $$$K$$$
The game is played in turns. At the end of a turn, the starting player for the next turn is determined and the process repeats until all the players have no cards left. The rules for a turn are the following:
- Each of the players will put exactly one card down in clockwise order beginning from the starting player of the turn (so player $$$(currentPlayer + 1) \% 3$$$ is after player $$$currentPlayer$$$).
- A player can attack a turn by putting a $$$7$$$ or a card equal to the first card of the turn placed by the starting player.
- At the end of a turn (after all 3 players have put a card down), if the starting player was not attacked by either of the other two players, he will be the winner of the turn.
- If the starting player was attacked, he can decide to either give up and let the last player that attacked him be the winner, or decide to contest by putting a $$$7$$$ or a card equal to the first card of the turn. If the player contests, the turn will continue and the other 2 players will have to each put a card down again and the process repeats until a winner is determined.
- The winner of a turn takes all the points of the turn (equal to the number of $$$10$$$ and $$$A$$$ cards from the table) and will be the starting player of the next turn.
- At the end of a turn, all the cards from the table are burned.
At the end of the game (when all the players have no cards left), the winner of the game is the player that has more points than each of the other two players (in the case there are more players with the maximum number of points, there are no winners).
In this game, you are the player $$$0$$$ (note: player $$$0$$$ is not always the starting player of the first turn). Your objective is to win the game. The other two players have no interest in winning, but they will do the optimal strategy in order to not let you win (classic sportsmanship).
If everyone plays the optimal strategy, we want you to determine if you can win the game or not.
The first line of the input contains the integers $$$N$$$ ($$$3 \leq N \leq 15$$$, N multiple of 3) and $$$P$$$ ($$$0 \leq P \leq 2$$$), denoting the total number of cards and the player who starts the game. The next $$$3$$$ lines have $$$N/3$$$ cards separated by spaces (a card can be $$$7$$$, $$$8$$$, $$$9$$$, $$$10$$$, $$$A$$$, $$$J$$$, $$$Q$$$ or $$$K$$$), denoting the cards of player $$$0$$$, $$$1$$$, and $$$2$$$, respectively.
Print $$$YEE!$$$ if there is an optimal strategy in order to win or $$$OOH...$$$ otherwise.
3 1 7 A A
YEE!
6 2 8 A 7 7 9 Q
OOH...
15 0 Q A 10 10 7 10 J A A 9 8 9 J 8 Q
YEE!
In the first example, player $$$1$$$ starts the game with $$$A$$$, player $$$2$$$ puts another $$$A$$$ and player $$$0$$$ puts a $$$7$$$. Because player $$$1$$$ cannot contest now (has no cards left), player $$$0$$$ is the one that attacked last (even if player $$$2$$$ attacked before him by putting a $$$A$$$), thus winning the $$$2$$$ points in the turn and winning the game.
In the second example, any strategy player $$$0$$$ chooses, player $$$1$$$ and player $$$2$$$ will always succeed in making him lose.
After even more Covid-19 related restrictions have been lifted, Lucia can go back to one of her favourite hobbies - bar hopping. The city where she wants to do that has all interesting locations placed in a way such that the roads between them form a tree. Moreover, each road $$$i$$$ has a wealth index $$$w_i$$$. Now, pub owners are quite the elitists, so in order to be able to go from a bar $$$a$$$ to a bar $$$b$$$ through road $$$i$$$, it must hold that she has a wealth index greater or equal than $$$w_i$$$.
Lucia is no stranger to bar hopping. In fact, there are combinations of pubs that she has tried before the pandemic. Therefore, she wants to make things more interesting.
For a given path from $$$X$$$ to $$$Y$$$, Lucia is now wondering how much wealth she would need in order to visit $$$K$$$ other pubs that are not included in said path, starting from $$$X$$$. Since she is quite adventurous, she does not ask herself this only once - she does this $$$Q$$$ times.
The first line of input will contain two integers, $$$N$$$ $$$(1 \le N \le 10^5)$$$ and $$$Q$$$ $$$(1 \le Q \le 10^5)$$$. The following $$$N-1$$$ lines will contain three integers $$$x$$$, $$$y$$$ and $$$w$$$ $$$(1 \le w \le 10^9)$$$, signifying that there is a road from $$$x$$$ to $$$y$$$ with a wealth index of $$$w$$$. The next $$$Q$$$ lines of input shall also contain three integers $$$x$$$, $$$y$$$, $$$k\ (k \ge 1)$$$, representing a query: given a path from $$$x$$$ to $$$y$$$ (not necessarily distinct), what is the minimum wealth index that Lucia requires in order to go to $$$k$$$ other pubs which do not belong to this path? It is guaranteed that there are at least $$$k$$$ nodes outside the path.
The output shall have a line containing $$$Q$$$ different integers $$$wealth_i$$$. Integer $$$wealth_i$$$ represents the answer to query $$$i$$$.
8 3 2 1 7 3 1 4 4 3 8 5 1 10 6 4 2 7 4 5 8 2 6 4 5 4 3 7 4 2 3 3
8 8 8
You are given an undirected graph with $$$N$$$ nodes and a list of edges of size $$$M$$$. You are asked to partition the given list of edges into minimum number of contiguous and disjoint subsequences such that every subsequence describes a bipartite graph. Please note, the graphs formed by different subsequences are completely independent.
The first line of the input contains the integers $$$N$$$ ($$$2 \leq N \leq 200000$$$) and $$$M$$$ ($$$1 \leq M \leq 200000$$$), denoting the number of nodes and the size of the edge list.
Each of the following $$$M$$$ lines contains $$$2$$$ positive integers, denoting an edge between nodes $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq N, x \neq y$$$).
On a single line, print the minimum number of subsequences to partition the given list of edges such that every graph inside a subsequence is bipartite.
3 3 1 3 1 2 2 3
2
It is time for yet another coins problem. Ionel found a 50 $$$bani$$$ coin on the street. If this happened 10 years ago, he would have been able to just consider himself lucky and buy some bread or some candy.
Unfortunately, this mysterious phenomenon called inflation has been happening, so he cannot really buy much with that coin these days. Therefore, he decided to at least play with it. Namely, if he flips the coin, Ionel will either get head or tails. He's so fascinated by this that he is thinking of flipping the coin $$$N$$$ ($$$1 \leq N \leq 10^6$$$) times. By doing so, he realizes that the expected number of distinct substrings of $$$K$$$($$$1 \leq K \leq N$$$) tails is $$$X$$$.
Now you might be confused: Ionel is giving all of this talk about an expected value, but there is no probability in sight. That is indeed the case - Ionel knows that there is a chance of $$$p$$$ of rolling tail and a chance of $$$1-p$$$ of rolling head. Weirdly enough, he does not actually know the value of this $$$p$$$. However, with the information that you're given, you might be able to find out and get one more accepted submission for the contest.
Formally, you are given a coin which can be flipped to head or to tail. This coin will be flipped $$$N$$$ times. Moreover, you also know $$$X(0 \leq X \leq N-K+1)$$$, which is the expected value for the number of times you can get a substring of length $$$K$$$ which is made only of tails.
What is the probability $$$p$$$ of rolling tail, given this information? We guarantee that $$$p$$$ will have a precision of $$$10^{-7}$$$.
On the first line, you are given an integer $$$T$$$ denoting $$$T$$$ different test cases, where $$$1 \leq T \leq 10^3$$$. The next $$$T$$$ lines will contain three values: an integer $$$N (1 \leq N \leq 10^6)$$$, referring to how many times a coin will be flipped, an integer $$$K (1 \leq K \leq N)$$$, referring to the length $$$K$$$ of each individual streak of tails, and a decimal positive value $$$X(0 \leq X \leq N-K+1)$$$, referring to the expected number of tail streaks of length $$$K$$$.
On $$$T$$$ lines, print $$$p_u$$$, the probability of rolling tail for the given coin.
3 10 3 3.432 10 3 0 10 3 8
0.754198673 0.000000000 1.000000000
Although Gogu is considered to be the best search engine, we believe you can do something better. Let's do it!
There are 4 types of queries you can make to your custom search engine:
- Type a new character in the search bar of the engine. Each time the search engine will suggest the most searched $$$K$$$ words where the current typed word is a prefix. If there are more words with the same frequency, the engine will pick those searched first. If there are less than $$$K$$$ words with this prefix, the search engine will display all of them.
- Clear the current search bar of the engine
- Delete the last character typed
- Press enter and search the current typed word. This word can now be used for future suggestions by the search engine.
The first line of the input contains the integers $$$Q$$$ ($$$1 \leq Q \leq 500.000$$$) and $$$K$$$ ($$$1 \leq K \leq 10$$$), denoting the number of queries and the numbers of words the search engine will try to suggest. The next $$$Q$$$ lines have the following structure:
- $$$1$$$ $$$C$$$ - to type a letter
- $$$2$$$ - to clear the current typed word
- $$$3$$$ - to delete the last typed character
- $$$4$$$ - to search the current typed word
For each operation of the $$$1^{st}$$$ type print on one line the IDs of the most searched $$$K$$$ words (or less than $$$K$$$ if there are not that many) with the current typed prefix in descending order of their frequency. In case of equality in terms of frequency, the word with the smallest ID goes first. If there is no word with the given prefix print $$$-1$$$. The ID of a word is the index of the first query of type $$$4$$$ which searched it. Please note that the queries are 0-indexed.
19 3 1 a 1 a 4 3 1 a 4 3 1 a 4 3 1 b 4 3 1 c 4 2 1 a 2 1 b
-1 -1 2 2 -1 -1 2 11 14 -1
One day, Johnny finds out he has a rare genetic condition. Naturally, he looks around the internet for a bit, and discovers that it's a condition that only affects men and it's mainly carried on the Y chromosome. After doing more research, he finds the following: A male is identified by one X chromosome and one Y chromosome (i.e. XY), while a female is identified by two X chromosomes (i.e. XX). During reproduction, when the zygote is formed, it gets a random chromosome from the mother and a random one from the father (these chromosomes being chosen with equal probability). If a chromosome carrying the disease is passed down from the parent to the child, then the child will carry the disease on that chromosome. Both males and females can carry the genetic condition on either of the chromosomes (or even on both), but it only manifests in males. In order for the disease to manifest the male must carry the disease on both of his chromosomes (i.e. both X and Y must have the gene), otherwise he is only a carrier.
Curious about the prevalence of this disease in his family, he starts wondering what is the probability of a given family member to have this disease.
Given a family tree that only has the paternal side (all nodes represent men in the family), the node that Johnny represents in his family tree, and a list of family members that Johnny is checking, your task is to calculate for each of these men their probability to have the genetic disease. Additionally, all children of a father have the same mother.
We consider that all possible chromosome combinations have a uniform distribution. The probability of a node having the disease should be calculated GIVEN the fact that you know Johnny has the disease.
Since the input and output are quite large, we recommend using fast methods of reading and writing, such as desynchronization in C++.
The first line of the input consists of the integer $$$N$$$ (the number of men in the family tree, $$$1 \leq N \leq 10^{6}$$$) and an integer $$$G$$$ ($$$1 \leq G \leq N$$$), representing Johnny.
Then, there are $$$N$$$ lines describing the children of every node. The first number, $$$n_k$$$ represents the node, and the second number, $$$c_k$$$ the number of children ($$$1 \leq c_k \leq N$$$). Then, there are $$$c_k$$$ integers, the indexes of $$$n_k$$$'s children.
On the next line is a single integer, $$$Q$$$ ($$$1 \leq Q \leq 10^{6}$$$), the number of queries.
On the final line, there's $$$Q$$$ integers, the nodes for which you need to output the probability of having the disease.
In your output, there should be $$$Q$$$ lines, the answer to every query with a precision of at least $$$10^{-7}$$$.
5 4 1 2 2 3 2 1 4 3 1 5 4 0 5 0 2 2 4
0.5000000000 1.0000000000
After working for over a year in a corporation, Peter realised that this is not the way to get rich. Instead, he quit his job and decided to participate in a lottery.
The lottery consists of a bag of $$$N$$$ prizes. The value of the $$$i^{\text{th}}$$$ prize is $$$value[i]$$$ and its weight is $$$weight[i]$$$. A prize is chosen randomly from the bag according to its weight. That is, the probability of the $$$i^{\text{th}}$$$ prize to be chosen is $$$\frac{weight[i]}{\sum_{k=1}^N weight[k]}$$$. Now, Peter has a choice to make. He can accept the prize and go home with it, or he can refuse the prize. If Peter refuses, the prize is placed back in the bag and Peter plays another round. However, Peter can refuse at most $$$K$$$ times. If he refuses $$$K$$$ times, then he is forced to take home the prize from the $$$K+1^{\text{th}}$$$ round.
Help Peter get rich and compute for him the maximum expected value he can get if he plays optimally.
The first line of the input contains the integers $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$K$$$ ($$$0 \leq K \leq 10^7$$$), denoting the number of prizes in the bag and the maximum number of times Peter can refuse the prize.
Each of the following $$$N$$$ lines contains $$$2$$$ integers $$$value[i]$$$ and $$$weight[i]$$$ ($$$1 \leq value[i], weight[i] \leq 10^5$$$), denoting the value and the weight of the $$$i^{\text{th}}$$$ prize.
On a single line, print the maximum expected value Peter can get if he plays optimally. Your answer will be considered correct if the absolute or relative difference between your answer and judge's answer is less than $$$10^{-8}$$$.
3 2 1 4 2 3 3 1
2.093750000000
Andrei is very keen on Physics, but he really hates maths. He always says: "Arghh, maths is just a tool, I don't need to understand it. It just helps me to do Physics!". Also, Andrei likes Computer Science and got stuck with the following problem:
You are given a matrix of size $$$N * M$$$ full of numbers modulo $$$3$$$. You can change any number in the matrix with another value modulo $$$3$$$. This operation has a cost equal to the absolute difference between the new value and the old one. The cost to change more elements is the sum of the costs to change each element individually. A submatrix of the initial matrix is called "special" if the number of rows is divisible by $$$2$$$ and the number of columns is divisible by $$$3$$$. Can you change the given matrix so that the sum inside each "special" submatrix is $$$1$$$ modulo $$$3$$$? If yes, what would be the minimum cost?
Please help Andrei to solve this problem even if you don't agree with his strong opinions!
The first line of the input contains the integers $$$N$$$ ($$$1 \leq N \leq 1000$$$) and $$$M$$$ ($$$1 \leq M \leq 1000$$$), denoting the number of rows and columns of the given matrix $$$A$$$.
Each of the following $$$N$$$ lines contains $$$M$$$ positive integers, denoting the values of the matrix $$$A$$$ ($$$0 \leq A_{i,j} \leq 2$$$).
On a single line, print the minimum cost to transform the matrix $$$A$$$ or $$$-1$$$ if it is not possible.
2 3 0 0 0 0 0 2
1
You just got inside a metro, and you want to take a seat somewhere. Obviously, you don't want to sit next to anyone. As a matter of fact, you want to sit as far away as you can from anyone. Thinking about that while standing up, you think of the following social experiment.
Suppose you have a metro that has a row of $$$N + 2$$$ seats, numbered from $$$0$$$ to $$$N + 1$$$. Seats $$$0$$$ and $$$N + 1$$$ are already occupied. A normal person chooses a vacant seat such that it is as far away from other occupied seats. That is, for each unoccupied seat, the person calculates two values $$$d_l$$$ and $$$d_r$$$, which are the distances to the nearest seat from the left and right, respectively. Out of each seat, the person will choose the seat with the value $$$min(d_l, d_r)$$$ as high as possible. If there are multiple such seats, the person will choose the seat with the value $$$max(d_l, d_r)$$$ as high as possible. If the person still can't decide on a seat, he will choose the leftmost seat (that is, the seat with the smallest index).
Now, let's start the social experiment. There are $$$Q$$$ events that happen sequentially, numbered from $$$1$$$ to $$$Q$$$. Each event is described by two numbers: $$$t_i$$$ and $$$k_i$$$.
- If $$$t_i$$$ is $$$1$$$, then a random person occupies seat $$$k_i$$$ if that place is vacant. Otherwise, the person sitting there will stand up and leave the metro, freeing that seat.
- If $$$t_i$$$ is $$$2$$$, then you wonder: if $$$k_i$$$ normal people would get inside the metro, where would the last person to enter sit?
Note: for the events with $$$t_i$$$ = 2, the configuration of the seats will not be changed by the $$$k_i$$$ people, as this is just a hypothetical question.
The first line of input contains the integers $$$N$$$ ($$$1 \leq N \leq 1.000.000.000$$$) and $$$Q$$$ ($$$1 \leq Q \leq 100.000$$$). The following $$$Q$$$ lines contain the description of each event, the $$$i$$$-th line containing two numbers $$$t_i$$$ ($$$1 \leq t_i \leq 2$$$) and $$$k_i$$$ ($$$1 \leq k_i \leq N$$$).
It is guaranteed that there are at most $$$11.000$$$ events with $$$t_i = 1$$$.
For each event of type $$$2$$$, type on one line the index of the seat chosen by the last person. If the last person cannot find a seat, print $$$-1$$$ instead.
10 5 2 5 1 4 2 5 2 1 2 10
6 1 7 -1
You are given a rooted tree with $$$N$$$ vertices indexed from $$$1$$$ to $$$N$$$ (a connected graph with $$$N$$$ vertices and $$$N - 1$$$ edges), rooted in the vertex $$$1$$$. Each vertex of the tree is assigned a letter from the first $$$10$$$ letters of the English alphabet ($$$"abcdefghij"$$$). Your little sister played with the tree and she deleted the letters from some vertices. Thus, some vertices are empty. As you love palindromes, some vertices from the tree are restricted. If the node $$$i$$$ is restricted, we have the following restriction: there exists a permutation of all the letters contained in the subtree rooted in $$$i$$$, including vertex $$$i$$$, such that the resulting string is a palindrome. Note that a string is palindrome, if it reads the same backward as forward.
As you want to keep all the restrictions true, you need to calculate the number of ways to assign letters to the empty vertices, such that all the restrictions are true. You can assign a letter from the first $$$10$$$ letters of the English alphabet. Because this number can be very large, you need to compute it modulo $$$998244353$$$.
The first line of the input contains the integers $$$N$$$ ($$$1 \leq N \leq 300.000$$$) and $$$Q$$$ ($$$1 \leq Q \leq 5.000$$$).
The following line contains $$$N - 1$$$ numbers, where the $$$i$$$-th number $$$P_i$$$ represents that there is an edge in the tree between vertices $$$P_i$$$ and $$$i + 1$$$, for each $$$1 \leq i \leq N - 1$$$.
The next line contains $$$Q$$$ different numbers between $$$1$$$ and $$$N$$$, representing the vertices that are restricted.
The last line contains a string of length $$$N$$$, consisting only of the first $$$10$$$ letters of the English alphabet and $$$?$$$, representing the value of each vertex. If a vertex has the value equal to $$$?$$$, it means that it is empty.
On a single line, print the number of ways you can assign letters from the first $$$10$$$ letters of the English alphabet to the empty vertices, such that all the restrictions are true. Because this number can be very large, you need to compute it modulo $$$998244353$$$.
5 2 1 1 2 2 1 2 a????
784
12 3 1 1 1 2 2 3 3 5 6 7 7 2 3 7 ??a??????a??
95334400
Transfagarasan is finally open to be driven through. To go down the mountain, travellers have to go through a serpentine road with $$$N(1 \leq N \leq 10^5)$$$ turns. The road has a starting height $$$y_s$$$ and a lower, end height $$$y_f$$$. Note that $$$0 \leq |y_s|, |y_f| \leq 10^9$$$, and that you go down the mountain, meaning that $$$y_s \gt y_f$$$.
The road is laid out such that, on one hand, turn number $$$i$$$ (where $$$i$$$ is an odd integer), requires drivers to turn to the left (from the driver's perspective). On the other hand, turn number $$$i$$$ (where $$$i$$$ is an even integer) requires drivers to turn to the right (from the driver's perspective).
Formally, you can imagine these $$$N$$$ turns as circles, where circle $$$i$$$ has radius $$$r_i$$$ ($$$1 \leq r_i \leq 10$$$) and a centre $$$(x_i, y_i)$$$, where it holds that $$$0 \leq |x_i|, |y_i| \leq 10^9$$$, and the road moves around these circles. It is guaranteed that circle $$$i$$$ is strictly above circle $$$i+1$$$ - in other words, $$$y_i-r_i \gt y_{i+1}+r_{i+1}$$$. Plus, it is also guaranteed that if $$$i$$$ is an odd number, then circle $$$i$$$ is to the left of circle $$$i+1$$$ (i.e. $$$x_i+r_i \lt x_{i+1}-y_{i+1}$$$), and if $$$i$$$ is an even number, then circle $$$i$$$ is to the right of circle $$$i+1$$$ (i.e. $$$x_i-r_i \gt x_{i+1}+y_{i+1}$$$).
Last but not least, note that the first circle is going to be below the starting height: in other words, $$$y_s \ge r_1+y_1$$$. Similarly, the last circle is going to be above the finishing height, meaning that $$$y_f \le y_n-r_n$$$.
What is the minimum distance $$$D$$$ of the road given that it starts anywhere at the starting height $$$y_s$$$, it ends anywhere at the ending height $$$y_f$$$, and it moves around the given circles as described above?
A picture containing of how such a road would look like can be seen on the second page of the problem statement, after the example section. Please note that the picture does NOT match the numerical example and it is meant as a visual representation of the restrictions in the problem.
Note that $$$D$$$ must have a precision of at least $$$10^{-7}$$$ in order to be considered correct.
The first line of input will contain three integers: $$$N$$$ ($$$1 \leq N \leq 10^5$$$), $$$y_s$$$ ($$$0 \leq |y_s| \leq 10^9$$$), $$$y_f$$$ ($$$0 \leq |y_f| \leq 10^9$$$). $$$N$$$ represents the number of circles, $$$y_s$$$, the starting height, and $$$y_f$$$, the end height.
The next $$$N$$$ lines of input will contain three integers $$$x_i$$$ $$$(0 \leq |x_i| \leq 10^9)$$$, $$$y_i$$$ $$$(0 \leq |y_i| \leq 10^9)$$$ and $$$r_i$$$ ($$$1 \leq r_i \leq 10$$$).
Print the distance $$$D$$$ - the minimum distance that a driver must travel to get from $$$y_s$$$ to $$$y_f$$$. Note that $$$D$$$ must be printed with a precision of at least $$$10^{-7}$$$.
3 8 0 1 7 1 4 4 1 1 1 1
14.5884381
