Squaring the circle is an age old problem. For millennia, people have sought to construct a square whose area is the same as a given circle. In 1882, Lindemann proved that $$$\pi$$$ is transcendental. As a corollary, it was then known that squaring the circle is impossible. Although there have been many claims to successfully squaring the circle, none has succeeded to this day...
Your mission, should you choose to accept it, is to square the circle.
The first and only line of input contains a single integer $$$r$$$ ($$$1 \le r \le 1000$$$), which is the radius of the circle.
The only line of output should contain a single real number, which is the side length of the square whose area is the same as the given circle. The output will be considered correct if the absolute or relative error is less than $$$10^{-4}$$$. Namely, if your answer is $$$a$$$ and the jury's answer is $$$b$$$, then your answer is accepted if $$$\frac{|a - b|}{\max(1,|b|)} \le 10^{-4}$$$.
1
1.7724538509
42
74.4430617380
Womais aime manger des croissants. He will eat one croissant every day for the next 80 years.
The first attempt was to stockpile 29220 croissants, which is enough to last 80 years. Unfortunately, after a week (7 days), the unconsumed croissants all went bad and became inedible. It seems that every croissant has this same shelf-life of 7 days. For example, if a croissant is bought on Monday, then it will be good through Sunday and become inedible on the next Monday.
For attempt two, Womais used his clairvoyance to see the croissant prices for the next $$$n$$$ days. Now he needs to determine the least cost of buying croissants to satisfy his croissant needs for the next $$$n$$$ days. It is safe to assume that the baker will never run out of croissants.
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 29220$$$), giving the number of days in question.
The second line of input contains $$$n$$$ space-separated integers $$$c_i$$$ ($$$1 \le c_i \le 4\cdot10^4$$$), where $$$c_i$$$ is the cost of one croissant on day $$$i$$$.
The only line of output should contain a single integer, which is the least cost for Womais to eat one croissant per day for the next $$$n$$$ days.
7 1 9 9 9 9 9 9
7
8 1 9 9 9 9 9 9 9
16
9 9 2 102 820 199 40000 1 37 42
22
Womais has constructed a sandwich on the plane. There are $$$n$$$ ingredients, where ingredient $$$i$$$ occupies the line segment from $$$(a_i,h_i)$$$ to $$$(b_i, h_i)$$$.
He now wants to share this sandwich with Dilgod by cutting it into two pieces. To do so, Womais chooses a non-horizontal line $$$\ell$$$ which cuts the plane into two pieces. Dilgod will receive the sandwich consisting of the parts on the left side of the line, and Womais the sandwich consisting of the parts on the right.
For each ingredient $$$i$$$, suppose that the line cuts it at the point $$$(c_i, h_i)$$$ (if the line does not intersect ingredient $$$i$$$, set $$$c_i$$$ to be one of $$$a_i$$$ or $$$b_i$$$, depending on which side of the line ingredient $$$i$$$ is on). Then, the goodness of the cut is defined as $$$\sum_{i=1}^{n} (b_i - c_i)(c_i - a_i)$$$.
Given the ingredient locations, help Womais find the maximum goodness of any line cutting them.
The first line of the input contains an integer $$$n$$$ ($$$1\le n \le 100$$$) – the number of ingredients.
The next $$$n$$$ lines describe the ingredients. The $$$i$$$-th line contains the tuple of integers $$$a_i, b_i, h_i$$$ ($$$1\le a_i \lt b_i \le 10^4$$$, $$$1\le h_i \le 10^4$$$) – the location of the $$$i$$$-th ingredient.
It is guaranteed that no two ingredients intersect: that is, there do not exist $$$i\neq j$$$ such that $$$h_i = h_j$$$ and $$$[a_i,b_i]\cap [a_j,b_j] \neq \varnothing$$$.
Output a single real number representing the maximum goodness of a line cutting the ingredients.
Your answer is considered correct if its absolute error or relative error does not exceed $$$10^{-6}$$$. Namely, if your answer is $$$a$$$ and the jury's answer is $$$b$$$, then your answer is accepted if $$$\frac{|a - b|}{\max(1,|b|)} \le 10^{-6}$$$.
21 5 12 6 2
8.000000000000
33 5 14 7 23 5 3
3.250000000000
Womais is taking a road trip through the fictional country of Muigleb. Unfortunately, he is late to his destination and would like to shave some time off his trip – but he is also scared of speeding and getting caught by the vigilant Muiglebian police. Highways in Muigleb have two lanes: the left lane and the right lane. Everybody in the right lane drives at the speed of 100 km/h, which is the Muiglebian speed limit. Cars in the left lane may drive at arbitrary speeds (even above the speed limit), subject to the following constraint: no car can drive faster than the car in front of it. Every car $$$c$$$ driving in the left lane will have an internal speed preference $$$s_c$$$. Then, if a car is driving in the left lane, its speed at any given moment will be equal to $$$\min(s_c, v)$$$, where $$$v$$$ is the speed of the car in front of it or $$$+\infty$$$ if there is no such car. To drive quickly and avoid getting pulled over, Womais will drive according to the following algorithm:
- If there is at least one car in the left lane, and the last car in the left lane is driving faster than 100 km/h, Womais will drive in the left lane behind the last car, with the speed equal to its speed.
- Otherwise, Womais will drive in the right lane at the speed of 100 km/h.
- A car currently in the left lane switches over to the right lane.
- A car currently in the right lane switches over to the left lane with some internal speed preference, ending up in front of all the cars currently in the left lane (note that this is different from what happens when Womais switches from the right lane to the left; he ends up behind all the cars in the left lane).
The first line of the input will contain two positive integers $$$d, n$$$ ($$$1 \leq d \leq {10}^9$$$, $$$0 \leq n \leq 2\cdot {10}^5$$$) – the length of the road trip in kilometers and the number of events to follow.
The $$$i$$$-th of the following $$$n$$$ lines will contain two positive integers $$$t_i, m_i$$$ ($$$1 \leq t_i, m_i \leq {10}^9$$$) and a character $$$c_i \in \{\texttt{L}, \texttt{R}\}$$$. If $$$c_i$$$ is $$$\texttt{L}$$$, the line will also contain a positive integer $$$s_i$$$ ($$$1 \leq s_i \leq {10}^9$$$). Here $$$t_i$$$ is the time in seconds of the $$$i$$$-th event (Womais's journey starts at time 0), $$$m_i$$$ is the unique identifier of the car involved in event $$$i$$$. The two cases for $$$c_i$$$ are as follows:
- If $$$c_i$$$ is $$$\texttt{R}$$$, car $$$m_i$$$ is switching from the left lane to the right lane. It is guaranteed that car $$$m_i$$$ was in the left lane just before this event.
- If $$$c_i$$$ is $$$\texttt{L}$$$, car $$$m_i$$$ is switching from the right lane to the left lane. This car's new internal speed preference is given as $$$s_i$$$, measured in km/h. It is guaranteed that car $$$m_i$$$ was in the right lane just before this event.
It is guaranteed that $$$t_i$$$ are strictly increasing.
The only line of output should contain a single integer, which is the number of seconds it will take Womais to drive $$$d$$$ km from the start of his journey, rounded up.
1000 310000 1 L 15015000 2 L 12520000 2 R
28167
In sample case 1, Womais is driving in the right lane with the speed of 100 km/h for the first 10000 seconds. At 10000s car 1 switches from right to left and Womais switches behind it, both of them driving at 150 km/h. At 15000s car 2 switches to the left in front of car 1, and both car 1 and Womais slow down to 125 km/h. At 20000s car 2 goes back to the right lane, and car 1 and Womais both speed back up to 150 km/h.
Womais is exploring the country of Muigleb on foot. For this purpose, Muigleb can be thought of as a collection of towns with bidirectional roads connecting some pairs of towns. Womais starts his walk in town $$$S$$$ and intends to reach the beautiful church in town $$$T$$$. Womais does not pay a lot of attention when he walks, so he may walk into the same town or walk along the same road multiple times on his journey (he may even walk through $$$S$$$ and/or $$$T$$$ multiple times before ending his journey at $$$T$$$). However, he is aware of an old Muiglebian superstition – if the total length of your journey is odd, you will be smitten by an ancient deity. Wanting to avoid such a fate at all costs, Womais would like your help to check that no matter what route he takes, he avoids the deity's wrath.
The first line of the input consists of two positive integers $$$n,m$$$ ($$$2 \leq n \leq 2\cdot10^5$$$, $$$1 \leq m \leq 2\cdot10^5$$$). The second line contains two positive integers $$$s,t$$$ ($$$1 \leq s,t \leq n$$$, $$$s \neq t$$$) describing the starting and ending towns of Womais's journey. The remaining $$$m$$$ lines each contain two positive integers $$$u,v$$$ ($$$1 \leq u,v \leq n$$$, $$$u \neq v$$$) describing a road. It is guaranteed that each pair of cities is connected by at most one road. It is also guaranteed that it is possible to get from $$$s$$$ to $$$t$$$ using the roads.
Output "Yes" (without quotes) if all walks from $$$s$$$ to $$$t$$$ have even length, and "No" (without quotes) otherwise. Here a walk of length $$$n$$$ from $$$s$$$ to $$$t$$$ is a sequence of towns $$$a_0, \ldots, a_n$$$ such that $$$a_0=s$$$, $$$a_n=t$$$, and $$$a_i$$$ is connected by a road to $$$a_{i+1}$$$ for all $$$0 \leq i \leq n-1$$$.
You can output "Yes" and "No" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).
6 52 41 22 33 41 45 6
Yes
6 61 51 66 22 33 44 26 5
No
Womais is hosting a Smash Tournament and is trying to pick two contestants to participate in a showmatch! In this showmatch, the two chosen contestants will play two separate sets against each other.
Each of the $$$n$$$ contestants has two playstyles that they want to show off – $$$a_i$$$ and $$$b_i$$$. If picked to play in the showmatch, they will use style $$$a_i$$$ in the first set and style $$$b_i$$$ in the second set.
In a given set, if the two contestants use styles $$$u$$$ and $$$v$$$ respectively, then the $$$\textit{character}$$$ of that set can be calculated as $$$\left|u - v\right|$$$.
Womais knows that if the two sets have the same $$$\textit{character}$$$, then the viewers will get bored and leave the event. On the other hand, if the two sets have different $$$\textit{character}$$$, then the match is guaranteed to be interesting. Find the number of pairs of contestants Womais can choose to produce an interesting match!
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 3\cdot 10^5$$$) – The number of potential contestants. The next $$$n$$$ lines contain two integers, $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq 10^9$$$) – The styles the $$$i$$$-th contestant will use in the first and second sets respectively.
Output a single integer – the number of pairs of contestants who will produce an interesting match.
512 1715 208 2323 815 20
6
Womais is playing a video game. Call a directed graph valid if it does not contain self-loops, and every vertex has at most one incoming and at most one outgoing edge. The game state consists of a valid directed graph with a weight attached to each vertex. Womais starts the game with some valid graph and a score of 0. His moves consist of adding edges to this graph. He can add any edge, provided that the resulting graph is still valid. When Womais adds an edge from a vertex with weight $$$a$$$ to a vertex with weight $$$b$$$, his score increases by $$$(a+b)^2$$$. What is the highest score Womais can achieve from a given game state? It is provable that the answer is always finite.
The first line of the input contains two positive integers $$$n$$$ ($$$1 \leq n \leq {10}^5$$$) and $$$m$$$ ($$$0 \leq m \leq {10}^5$$$). The following line contains $$$n$$$ integers $$$w_i$$$ ($$$1 \leq w_i \leq 10^5$$$), where $$$w_i$$$ is the weight in the $$$i$$$-th vertex. The remaining $$$m$$$ lines describe the edges of the initial game state, with the $$$i$$$-th line consisting of two integers $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$) representing a directed edge from $$$a_i$$$ to $$$b_i$$$. It is guaranteed that the graph described in the input is valid.
Output should be a single integer representing the maximum score Womais can achieve from the given game state.
3 13 3 102 3
205
Womais has a string $$$s$$$ consisting of lowercase letters and a pattern $$$p$$$ consisting of lowercase letters and stars. We say that the string $$$a$$$ fits the pattern $$$b$$$ if it is possible to get $$$a$$$ by replacing every star in $$$b$$$ with a (possibly empty) string. Different stars can be replaced by different strings. You are given a series of single-character modifications on the string $$$s$$$, and your task is to help Womais determine whether there exists a substring of $$$s$$$ which fits $$$p$$$ after each modification. Here a substring of a string $$$s = s_1s_2\ldots s_{\lvert s \rvert}$$$ is a string $$$s_ls_{l+1}\ldots s_r$$$ for some $$$1 \leq l \leq r \leq \lvert s \rvert$$$.
The first line of the input consists of a string $$$s$$$ ($$$1 \leq \lvert s \rvert \leq 2\cdot 10^5$$$) consisting of lowercase Latin letters. The second line contains a string $$$p$$$ ($$$1 \leq \lvert p \rvert \leq 200$$$) consisting of lowercase Latin letters and characters '*'. It is guaranteed that $$$p$$$ does not contain two consecutive stars. The third line contains a single integer $$$q$$$ ($$$0 \leq q \leq 2\cdot 10^4$$$), indicating the number of modifications to follow. The following $$$q$$$ lines each consist of an integer $$$i$$$ ($$$1 \leq i \leq \lvert s \rvert$$$) and a character $$$\texttt{c} \in \texttt{[a-z]}$$$, indicating that the $$$i$$$-th character of $$$s$$$ is changed to $$$\texttt{c}$$$.
The output should contain $$$q+1$$$ lines. The first line should contain "Yes" (without quotes) if there exists a substring of $$$s$$$ which fits the pattern $$$p$$$, and "No" (without quotes) otherwise. The $$$i$$$-th of the following $$$q$$$ lines should contain the answer to the same question after $$$s$$$ has undergone the first $$$i$$$ modifications.
The output is not case-sensitive, meaning that "Yes", "yes" or "yEs" will all count as an affirmative answer.
abacabada*a*a*a23 c4 a
Yes No Yes
stanford*sta*r63 s5 a4 t1 u8 r7 n
Yes No No Yes Yes Yes Yes
Womais is training to become a world-class spy to protect his magical village. His final assignment is to observe a tall building through very thick fog. This building has $$$n$$$ floors, each floor has $$$m$$$ windows in a row such that all the windows of this building form an $$$n\times m$$$ grid. Each window is either dark or lit by a light from inside the building. Womais needs to determine exactly which of the windows are lit to know the distribution of people inside the building. Enhancing his emerald eyes with an enigmatic magic, Womais is able to see through the fog well enough to make two observations:
- Floor $$$i$$$ has exactly $$$a_i$$$ lit windows.
- No two lit windows are horizontally or vertically adjacent.
The first line of input contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 30$$$, $$$1\le m\le 23$$$), representing the number of floors and the number of windows on each floor respectively (ie. the dimensions of the building).
The second line of input contains $$$n$$$ space-separated integers. The $$$i$$$-th integer is $$$a_i$$$ ($$$0\le a_i\le m$$$), representing the number of lit windows on the $$$i$$$-th floor.
The output should contain a single integer, the number of ways (modulo $$$10^9 + 7$$$) for the windows to be lit so that both of Womais's observations are satisfied.
4 31 2 0 2
1
2 32 2
0
As an attempt to convince you that Vancouver is a wonderful city, here are a few well-known facts:
- Winters are very rainy.
- The weather forecast is incredibly accurate and can accurately forecast the weather for an entire season (of course, it rains every second).
- The rain will get to you, no matter the umbrella.
Suppose we know the forecast for the next $$$n$$$ minutes. Say the amount of rain during the $$$i$$$-th minute is $$$w_i$$$. There will be $$$m$$$ students and each student will inevitably make a trip from one building to another. Attempting to stay dry, the $$$j$$$-th student carries an umbrella with an efficiency of $$$e_j$$$, meaning that the umbrella can block $$$e_j$$$ units of rain per minute. Thus, if student $$$j$$$ is outside during the $$$i$$$-th minute, the umbrella will block $$$\min(e_j, w_i)$$$ units of rain (because you can't block rain that doesn't exist). Finally, suppose student $$$j$$$ is outside from minute $$$l_j$$$ to minute $$$r_j$$$ inclusive. We want to know how wet each student gets (ie. how many units of rain will hit each student).
The first line of input contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 2\times10^5$$$), giving the number of minutes of the forecast and the number of students respectively.
The second line of input contains $$$n$$$ space-separated integers $$$w_i$$$ ($$$1 \le w_i \le 10^9$$$), giving the amount of rain during the $$$i$$$-th minute.
Each of the next $$$m$$$ lines of input contains three space-separated integers $$$l_j$$$, $$$r_j$$$, and $$$e_j$$$ ($$$1\le l_j\le r_j\le n,\ 0\le e_j\le 10^9$$$). This means the $$$j$$$-th student is outside from minute $$$l_j$$$ to minute $$$r_j$$$ inclusive, and has an umbrella of efficiency $$$e_j$$$.
The output should contain $$$m$$$ lines. The $$$j$$$-th line should contain a single integer, which is the number of units of rain that hit student $$$j$$$.
6 43 1 4 1 5 91 3 31 6 02 2 9992 5 2
1 23 0 5