Magikarp is on an anti-diet and wants to maximize the amount of calories that he eats today. He currently has a selection of $$$n$$$ restaurants. The $$$i$$$th restaurant serves only 2 dishes: an appetizer with $$$a_i$$$ calories and an entree with $$$b_i$$$ calories. Magikarp will choose exactly 1 restaurant for an appetizer and exactly 1 for an entree, while maximizing the total number of calories he consumes. However, he does not want to order his 2 dishes from the same restaurant. What is the maximum sum of calories Magikarp can order?
The first line of input contains $$$n$$$ $$$(2\le n\le 2\cdot 10^5)$$$ — the total number of restaurants.
The $$$i$$$th of the next $$$n$$$ lines contains 2 integers $$$a_i$$$ and $$$b_i$$$ $$$(0\le a_i, b_i\le 10^6)$$$ — the number of calories in the appetizer and entree, respectively, at restaurant $$$i$$$.
Output a single number, the maximum sum of calories Magikarp can order.
56 12 710 43 31 4
17
2100 1001 2
102
For the first sample, Magikarp can order an appetizer from restaurant $$$3$$$ and an entree from restaurant $$$2$$$ for a calorie total of $$$10 + 7 = 17$$$. It can be shown that no other combination produces a larger total.
For the second sample, Magikarp would want to order both the appetizer and entree from restaurant $$$1$$$, but this is not allowed. The best that he can do is order the appetizer from restaurant $$$1$$$ and the entree from restaurant $$$2$$$ for a calorie total of $$$100+2=102$$$.
You are building a new roof for your shed. You've decided to design the roof so that its cross-section is shaped like the curve $$$\cos x$$$ for $$$x \in [-\pi/2, \pi/2]$$$ (recall that cosine increases monotonically from $$$0$$$ at $$$x = -\pi/2$$$ to $$$1$$$ at $$$x=0$$$, and then decreases monotonically back to $$$0$$$ at $$$x=\pi/2$$$).
To buttress the roof, you will install some wooden beams. Each beam can be represented as a line segment of slope $$$m$$$ that extends from $$$(0,0)$$$ to a point $$$(x, mx)$$$ touching the roof. You've computed the value of the slope $$$m$$$ needed in order for the roof to be structurally sound. Before heading to the hardware store to buy lumber, you need to know the value of $$$x$$$ for which $$$\cos x = mx$$$. Compute this value.
The only line of input contains a single real number $$$m$$$ $$$(0 \leq m \leq 10^9)$$$: the slope of the beams you plan to install under your roof.
Print a real number: the value of $$$x \in [0, \pi/2]$$$ for which $$$\cos x = mx$$$. It is guaranteed that this value exists and is unique. Your program will be judged correct if it differs from the judge's solution with relative or absolute error at most $$$10^{-9}$$$.
42.0
0.0238027792365755885839462280273
0
1.57079632682143710553646087646
428668410.596547564
2.35741026699542999267578125e-09
Hint: make sure you use double precision and print $$$x$$$ with many digits after the decimal point (at least nine) to meet the above precision requirement.
To get the value of $$$\pi$$$ in your program, you can use the following.
In C++:
const double PI = acos(-1.0);
In Java:
double PI = Math.PI;
In Python:
import math
PI = math.pi
You are replacing the sprinkler system in your front yard and need to connect a set of sprinkler heads with pipes.
Water enters the sprinkler system from a faucet at a fixed location in space. A pipe needs to carry this water to one sprinkler head, and from there to a second sprinkler head, and so on. The pipe cannot branch: it must visit every sprinkler head exactly once, but can connect the sprinkler heads in any order.
Given the cost of laying pipe between the faucet and every sprinkler head, and between every head and every other head, compute the cheapest cost you must pay to connect water to every sprinkler head using a single non-branching pipe.
The first line of input contains an integer $$$N$$$ $$$(1 \leq N \leq 15)$$$, the number of sprinkler heads in your front yard.
The next line of input contains $$$N$$$ space-separated integers $$$f_i$$$ $$$(0 \leq f_i \leq 10^6)$$$, the cost of connecting the faucet to sprinkler head $$$i$$$.
Each of the next $$$N$$$ lines of input contain $$$N$$$ space-separated integers each. The $$$j$$$th integer on the $$$i$$$th row, $$$c_{ij}$$$ $$$(0 \leq c_{ij} \leq 10^6)$$$, is the cost of connecting sprinkler head $$$i$$$ to sprinkler head $$$j$$$ with pipe. It is guaranteed that $$$c_{ij} = c_{ji}$$$ and that $$$c_{ii} = 0$$$ for every $$$i, j$$$ (though it is invalid to connect a sprinkler head to itself in any case.)
Print the cheapest total cost of connecting the faucet to all sprinkler heads using a single, non-branching pipe.
47 8 1 20 3 1 43 0 8 81 8 0 54 8 5 0
11
110000000
1000000
51000 1000 1 1000 10000 1 1000 1000 10001 0 1000 1000 11000 1000 0 1 10001000 1000 1 0 11000 1 1000 1 0
5
In the first sample, there are $$$4$$$ sprinkler heads. The costs of connecting the faucet to each sprinkler head are $$$$$$f = \begin{bmatrix}7 & 8 & 1 & 2\end{bmatrix}.$$$$$$
One optimal way to connect the sprinkler heads is to use the order $$$$$$\text{faucet} \rightarrow 4 \rightarrow 3 \rightarrow 1 \rightarrow 2.$$$$$$
The total cost of this order is $$$$$$f_4 + c_{4,3} + c_{3,1} + c_{1,2}.$$$$$$
Substituting the values from the input, this is $$$$$$2 + 5 + 1 + 3 = 11.$$$$$$
Therefore, the cheapest total cost is $$$11$$$.
You are the Lead Engineer for the province of Spongeland, which consists of $$$n$$$ cities. Your mission is to establish a highway network such that every city is reachable from every other city through a series of connected roads.
There are $$$m$$$ potential highway proposals available for construction. Each proposal $$$i$$$ (where $$$1 \le i \le m$$$) is defined by:
However, the provincial government has already signed a non-negotiable contract for proposal $$$j$$$. This specific highway must be included in your final network, regardless of its cost or how it affects the overall efficiency.
Calculate the minimum total cost to connect all $$$n$$$ cities, ensuring that proposal $$$j$$$ is part of the infrastructure.
The first line contains two integers: $$$n$$$ (number of cities) and $$$m$$$ (number of proposals). The second line contains an integer $$$j$$$, representing the index of the mandatory proposal. The following $$$m$$$ lines each contain three integers $$$u_i, v_i$$$, and $$$c_i$$$, representing the $$$i$$$-th proposal.
A single integer representing the minimum cost to connect all $$$n$$$ cities including proposal $$$j$$$. Note: Use a 64-bit integer type to avoid overflow.
4 531 2 102 3 53 4 501 4 202 4 15
65
The mandatory proposal is proposal $$$3$$$, which connects cities $$$3$$$ and $$$4$$$ with cost $$$50$$$.
After including this proposal, one optimal way to finish connecting all cities is to also include: $$$$$$ (2, 3) \text{ with cost } 5 $$$$$$ and $$$$$$ (1, 2) \text{ with cost } 10. $$$$$$
These three highways connect all $$$4$$$ cities: $$$$$$ 1 \leftrightarrow 2 \leftrightarrow 3 \leftrightarrow 4. $$$$$$
The total cost is $$$$$$ 50 + 5 + 10 = 65. $$$$$$
Therefore, the minimum total cost including proposal $$$3$$$ is $$$65$$$.
Given an array $$$A$$$ of size $$$N$$$ and an integer $$$1 \leq k \leq N$$$, we can cut $$$A$$$ from left to right into consecutive contiguous subarrays. Each subarray has size $$$k$$$, except possibly the last subarray, which may have size between $$$1$$$ and $$$k$$$ inclusive. Equivalently, we cut after positions $$$k, 2k, 3k, \ldots$$$ until the end of the array. These subarrays, including the last subarray, are the $$$k$$$-partitions of $$$A$$$.
For example, for the array $$$$$$A = \begin{bmatrix} 1 & 2 & 3 & 1 & 1 & 2 & 5 \end{bmatrix}$$$$$$ the $$$3$$$-partitions of $$$A$$$ are $$$\begin{bmatrix}1 & 2 & 3\end{bmatrix}$$$, $$$\begin{bmatrix}1 & 1 & 2\end{bmatrix}$$$, and $$$\begin{bmatrix} 5 \end{bmatrix}$$$.
The array $$$A$$$ has sorted $$$k$$$-partitions if each of its $$$k$$$-partitions (including the last partition) has non-decreasing elements. Note that every array has sorted $$$1$$$-partitions, and that an array of size $$$N$$$ has sorted $$$N$$$-partitions if and only if $$$A$$$ itself is sorted. The example array $$$A$$$ above has sorted $$$k$$$-partitions for $$$k=1$$$ and $$$3$$$.
Given an array $$$A$$$ of size $$$N$$$, compute the largest integer $$$k \leq N$$$ for which $$$A$$$ has sorted $$$k$$$-partitions.
The first line of input contains a single integer $$$N$$$ $$$(1 \leq N \leq 2\cdot 10^5)$$$, the size of the input array. The next line contains $$$N$$$ space-separated integers $$$a_i$$$ $$$(0 \leq a_i \leq 10^6)$$$, the contents of the array.
Print the largest integer $$$k \leq N$$$ for which $$$A$$$ has sorted $$$k$$$-partitions. Such an integer is always guaranteed to exist.
71 2 3 1 1 2 5
3
742 42 42 42 42 42 42
7
54 3 2 1 0
1
Hint: think about the time complexity of your approach before implementing a solution!