Magikarp wants to buy a bond. He knows the bond's coupon rate, the annual interest rate, its face value, and the number of years until it matures. The bond pays one coupon at the end of each year and returns its face value at maturity. Help Magikarp find its current price.
Let $$$c$$$ be the coupon rate as a percentage, $$$r$$$ be the annual interest rate as a percentage, $$$F$$$ be the face value, and $$$n$$$ be the number of years until maturity. The coupon paid each year is $$$F \cdot \frac{c}{100}$$$. The bond's current price is
$$$$$$ P = \frac{F}{\left(1+\frac{r}{100}\right)^n} + \sum_{k=1}^{n} \frac{F \cdot \frac{c}{100}}{\left(1+\frac{r}{100}\right)^k}. $$$$$$
The second term is the present value of all coupon payments. The first term is the present value of the face value returned at maturity.
The first line contains two real numbers $$$c$$$ and $$$r$$$ ($$$0 \le c \le 100$$$, $$$0.01 \le r \le 100$$$) — the coupon rate and the annual interest rate, respectively, given as percentages.
The second line contains two integers $$$F$$$ and $$$n$$$ ($$$1 \le F \le 10^6$$$, $$$1 \le n \le 1000$$$) — the face value of the bond and the number of years until it matures, respectively.
Output the bond's current price. Your answer is accepted if its absolute error is at most $$$10^{-4}$$$.
5.0 5.01000 3
1000.000000000000000
6 41000 3
1055.501820664542720
In the first sample, the annual coupon and interest rates are equal, so the bond's current price equals its face value.
In the second sample, the annual coupon is $$$60$$$. Discounting the three coupons and the $$$1000$$$ face value at $$$4\%$$$ gives $$$1055.5018206645$$$.
Hint: in order to satisfy the above error bound, be sure to print many digits of your answer (at least 8).
For example, if your answer is stored in ans:
- Java: System.out.printf("%.10f%n", ans);
- C++: cout << fixed << setprecision(10) << ans << '\n'; (include <iomanip>)
- Python: print(f"{ans:.10f}")
You are in charge of buying a pumpkin to carve into a jack-o'-lantern for your suite's Halloween decorations! After performing extensive research at the nearby supermarket, you've realized that the supermarket generally charges more for larger pumpkins, but the relationship is complicated: you've fit a cubic curve relating price $$$p$$$ of the pumpkin to its volume:
$$$$$$V(p) = a_0 p^3 + a_1 p^2 + a_2 p + a_3$$$$$$
for some positive constants $$$a_i$$$ you've calculated from the data.
A good-looking jack-o'-lantern must be carved from a pumpkin of volume at least $$$V_T$$$. Given $$$V_T$$$, what's the cheapest price you'll have to pay to acquire a sufficiently-large pumpkin?
The only line of input contains five space-separated real numbers $$$V_T$$$, $$$a_0$$$, $$$a_1$$$, $$$a_2$$$, and $$$a_3$$$. These numbers might be expressed in scientific notation (see sample inputs) and are all in the range $$$\left[ 10^{-9}, 10^9\right]$$$.
Print the smallest value of $$$p$$$ for which $$$V(p) \geq V_T$$$. Your answer will be judged correct if it differs from the judge's solution by absolute or relative error at most $$$10^{-6}$$$.
100.0 1.0 2.0 3.0 4.0
3.8137429654598236083984375
1e9 1e-9 1e-9 1e-9 1e-9
999999.666666418313980102539062
1.21419e-07 1571.28 12923.4 6.86914e+07 2.14303e+06
2.98023223876953125e-08
Hint: in order to satisfy the above error bound, be sure to print many digits of $$$p$$$ (at least 8).
For example, if your answer is stored in ans:
- Java: System.out.printf("%.10f%n", ans);
- C++: cout << fixed << setprecision(10) << ans << '\n'; (include <iomanip>)
- Python: print(f"{ans:.10f}")
Alice and Beth want to meet up for brunch. They both live in different parts of the city; Alice drives and Beth rides a bike. Given a map of the city and the amount of time it takes Alice and Beth to travel along each road, what's the soonest they can meet up, if both leave their apartments immediately?
More specifically, if $$$P$$$ is an intersection in the city, then the time it takes Alice and Beth to meet up at $$$P$$$ is the maximum of Alice and Beth's travel time to $$$P$$$. Find the $$$P$$$ that minimizes this maximum travel time and print that travel time.
There are brunch places all over the city, but only near the intersections: not in the middle of random roads. So Alice and Beth are only interested in meeting up at a city intersection.
The first line of input contains two space-separated integers $$$N$$$ and $$$M$$$ ($$$2 \leq N \leq 1\,000$$$; $$$1 \leq M \leq 50\,000$$$), the number of intersections and roads in the city, respectively.
The next $$$M$$$ lines describe the roads. Each line contains four space-separated integers $$$u$$$, $$$v$$$, $$$a$$$, and $$$b$$$ ($$$1 \leq u \lt v \leq N$$$; $$$0 \leq a, b \leq 100$$$) indicating that there is a road connecting intersections $$$u$$$ and $$$v$$$, and that it takes Alice and Beth $$$a$$$ and $$$b$$$ minutes to travel along that road, respectively.
Roads can be traveled in either direction. There is at most one road between any pair of intersections.
Alice lives at intersection $$$1$$$ and Beth lives at intersection $$$N$$$.
Print the shortest amount of time it takes for Alice and Beth to meet up at a common intersection, if both leave their apartments at the same time and travel as quickly as possible towards the intersection that minimizes this time.
If it's impossible for Alice and Beth to meet up anywhere in the city, print $$$-1$$$ instead.
6 71 2 10 352 3 1 42 4 5 152 5 2 33 6 11 204 6 5 25 6 0 1
10
Magikarp is shopping at M-Mart. He has $$$n$$$ coupons in his pocket, numbered from $$$1$$$ to $$$n$$$. Each coupon gives either a percentage discount or a dollar discount.
There are $$$q$$$ items Magikarp might buy. For each item, he chooses a contiguous subarray of his coupons and may use those coupons in any order. He wants to pay as little as possible. A price cannot go below $$$0$$$; if a discount would make it negative, the price becomes $$$0$$$.
Magikarp has already chosen which coupons to apply to each item, but not the order in which to apply those coupons. Help Magikarp find the minimum possible price of each item.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 200\,000$$$) — the number of coupons and the number of items, respectively.
Each of the next $$$n$$$ lines describes one coupon. The $$$i$$$th line contains a character $$$t_i$$$ and an integer $$$x_i$$$. If $$$t_i=\texttt{P}$$$, the coupon discounts the current price by $$$x_i$$$ percent ($$$0 \le x_i \le 99$$$). If $$$t_i=\texttt{D}$$$, the coupon discounts the current price by $$$x_i$$$ dollars ($$$0 \le x_i \le 10^9$$$).
Each of the next $$$q$$$ lines contains three integers $$$p$$$, $$$l$$$, and $$$r$$$ ($$$1 \le p \le 10^6$$$, $$$1 \le l \le r \le n$$$) — the item's original price and the endpoints of the chosen coupon subarray, respectively.
It is possible that the same coupon is used on multiple items.
It is guaranteed that applying all percentage coupons among the $$$n$$$ coupons to a price of $$$1$$$ (ignoring dollar coupons) leaves a price of at least $$$10^{-250}$$$. The smallest positive value of a 64-bit double is around $$$10^{-308}$$$.
For each item, output its minimum possible price if Magikarp applies his chosen coupons in the optimal order. Your answer is accepted if its absolute error is at most $$$10^{-4}$$$.
3 3D 10P 50D 5100 1 310 1 3100 2 2
35.000000000000000 0.000000000000000 50.000000000000000
4 2P 90D 1P 10D 50100 1 41000 2 4
0.000000000000000 849.000000000000000
In the first sample, Magikarp can use the $$$50\%$$$ coupon first, reducing the price from $$$100$$$ to $$$50$$$, then use both dollar coupons to reduce it to $$$35$$$. For the second item, the same discounts reduce the price to $$$0$$$. The second query uses only the $$$50\%$$$ coupon.
In the second sample, the $$$90\%$$$ and $$$10\%$$$ coupons reduce the first item's price from $$$100$$$ to $$$9$$$, and the two dollar coupons reduce it to $$$0$$$. For the second item, the $$$10\%$$$ coupon reduces $$$1000$$$ to $$$900$$$, and the two dollar coupons then reduce it by $$$51$$$.
Hint: in order to satisfy the above error bound, be sure to print many digits of your answer (at least 8).
For example, if your answer is stored in ans:
- Java: System.out.printf("%.10f%n", ans);
- C++: cout << fixed << setprecision(10) << ans << '\n'; (include <iomanip>)
- Python: print(f"{ans:.10f}")
While bored on a trip, you've invented a single-player card game to pass the time. You start by laying out $$$N$$$ cards chosen at random from a deck: to keep the game simple, you've removed the face cards from the card deck, so that every card has a rank from $$$1$$$ to $$$10$$$, and a suit (clubs, diamonds, hearts, or spades).
You then try to group as many cards as possible into pairs. Two cards can be paired if they have the same suit or the same rank. (Once two cards have been paired, they cannot be used again to form any additional pairs.)
What's the maximum number of pairs you can form using the given cards, if you play the game optimally?
The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 40$$$), the number of cards you've drawn from the deck.
Each of the next $$$N$$$ lines describes one of the cards and consists of a rank (an integer between 1 and 10 inclusive) followed by a single upper-case letter C, D, H, or S, indicating a suit of clubs, diamonds, hearts, or spades, respectively.
No two cards will have the same rank and suit.
Print the maximum number of pairs that can be formed from the given cards.
52C7C10H7S5C
2
42C3D4H5S
0