After buying a monitor and a suitcase, then breaking the monitor by putting it in the suitcase on a flight, Leo resolved to make better personal finance decisions. However, he was challenged in this resolve when Black Friday came to pass. He ended up adding too many things to his shopping cart, to the dismay of his bank account. When all seemed lost, Leo remembered something. He had a coupon book lying around that he could use. These coupons were special and worked by first lowering his current shopping cart balance by $$$a_i$$$, and then giving a $$$d_i\%$$$ discount (removing $$$d_i\%$$$ of the adjusted balance). Due to a software error, Leo found that he could apply multiple coupons to the same shopping cart, and that applying all of the coupons in different orders could result in different final balances. Help Leo determine an optimal way to order the coupons that minimizes the final balance.
The first line of input will consist of a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of coupons Leo has.
The following $$$n$$$ lines will consist of two real numbers $$$a_i$$$ and $$$d_i$$$ $$$(0.0 \le a_i \le 10^9, 0.0 \le d_i \lt 100.0)$$$ — the amount to reduce the price by and the discount percentage of the $$$i$$$-th coupon.
Both values $$$a_i,d_i$$$ will be printed to two decimal places. Also assume that Leo's shopping cart balance is large enough that it will never go negative after applying all of the coupons in any order.
Output a line containing a permutation $$$c$$$ of the numbers from $$$1$$$ to $$$n$$$ — the order that the coupons should be applied in. $$$c_1$$$ should correspond to the first coupon used, $$$c_2$$$ should correspond to the second coupon used, and so on. $$$c$$$ should have $$$n$$$ elements and be separated by spaces. There may be multiple optimal orderings, and any optimal ordering will be accepted.
216.65 0.000.00 16.65
2 1
3200.00 10.0010.00 20.0050.00 5.00
2 3 1
Madeline is stuck in a grid, where she can only move up, down, left and right by one cell. She is currently in the first cell of the last row of the grid and wants to collect a strawberry in the last cell of the first row. Initially, Madeline is extremely fast so it takes her zero seconds to travel to a new cell, however, part of her (often referred to as Badeline) wants to slow her down. For every pair of adjacent cells, Badeline can increase the time it takes Madeline to traverse between two cells by a positive real number, $$$x$$$, for a cost of $$$x \cdot c$$$. Note that $$$c$$$ can differ between different pairs of cells. Assuming Madeline will take the shortest path to the strawberry after Badeline adds in the delays, determine the maximum shortest path Badeline can create for Madeline such that Badeline's total cost is at most $$$k$$$.
The first line of input will consist of three integers, $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \leq n, m \leq 1000$$$, $$$1 \leq k \leq 10^9$$$) — the number of rows and columns in the grid and the max total cost.
For the following $$$n$$$ lines, the $$$i$$$-th line will consist of $$$m-1$$$ integers, $$$c_{r,i,j}$$$ indicating the cost rate of increasing the time it takes to traverse between cells $$$(i, j)$$$ and $$$(i, j+1)$$$, where $$$(i, j)$$$ denotes the $$$j$$$-th cell of the $$$i$$$-th row.
For the following $$$n-1$$$ lines, the $$$i$$$-th line will consist of $$$m$$$ integers, $$$c_{c,i,j}$$$ indicating the cost rate of increasing the time it takes to traverse between cells $$$(i, j)$$$ and $$$(i+1, j)$$$, where $$$(i, j)$$$ denotes the $$$j$$$-th cell of the $$$i$$$-th row.
All cost rates are between $$$1$$$ and $$$10^9$$$.
Output a single real number — the longest shortest path Badeline can create for Madeline. Your answer will be accepted if it has an absolute or relative error of $$$10^{-6}$$$ with the judge's solution.
2 2 3111 1
1.5000000000
3 3 43 62 51 41 3 52 4 6
1.3333333333
Tax day is coming! Quinn is very worried about his taxes but does not want to go to a tax lawyer to file them. He's decided to navigate the world of taxes on his own to find the very best way to file his taxes. The country Quinn lives in has two tax systems in which you can report income to be taxed. You cannot report a total income higher than $$$m$$$ dollars.
A tax system is defined as follows:
- A tax system consists of $$$n$$$ tax brackets.
- The tax system is defined by two strictly increasing sequences $$$b$$$ and $$$t$$$ of sizes $$$n+1$$$ and $$$n$$$, respectively.
- $$$b$$$ represents the tax bracket boundaries while $$$t$$$ represents the tax rates of the brackets. Specifically, the $$$i$$$-th tax bracket is defined by three numbers $$$b_i, b_{i+1}, t_i$$$, defining an interval $$$[b_i,b_{i+1}]$$$ that is taxed at a rate of $$$t_i\%$$$.
- All of the tax brackets are disjoint and union to the full interval $$$[0,m]$$$. Therefore, $$$b_n=m$$$.
To actually report a total income of $$$x$$$, Quinn must first split it into $$$y$$$ and $$$z$$$ — the income he will report to tax system 1 and 2, respectively. Then the starting point for tax system 1 is $$$0$$$ and the starting point for tax system 2 is $$$y$$$. Help Quinn determine the minimum amount of taxes he must pay if he splits $$$x$$$ optimally. $$$y$$$ and $$$z$$$ must be non-negative, real values that sum to $$$x$$$.
However, Quinn does not yet know how much income he will earn this year, so he wants you to help him figure this out for multiple total incomes.
The first line of input will consist of two integers $$$n$$$ and $$$m$$$ $$$(2 \le n \le 10^5, 1 \le m \le 10^9)$$$ — the number of tax brackets both tax systems have and the maximum total income that can be reported, respectively.
Following that are the descriptions of tax system 1 and 2, respectively. The input formats for both are identical and as follows:
The first line consists of a strictly increasing array $$$b$$$ of $$$n+1$$$ real numbers $$$(0.0 \le b_i \le m,b_0=0.0,b_n=m)$$$, representing the tax boundaries. Each value will have exactly two decimal places. The second line consists of a strictly increasing array $$$t$$$ of $$$n$$$ real numbers $$$(0.0 \le t_i \le 100.0)$$$, representing the tax rates. Each value will have exactly five decimal places.
The next line of input will consist of a single integer $$$q$$$ $$$(1 \le q \le 10^5)$$$ — the number of queries. The last $$$q$$$ lines of input will each consist of a single real number $$$(0.0 \le x_i \le m)$$$, representing a query for a total income. Each value will have exactly two decimal places.
Output $$$q$$$ lines, each containing a single real number — the minimum tax paid for the respective query. Your answer will be accepted if it has an absolute or relative error of $$$10^{-6}$$$ with the judge's solution.
3 100.00 2.00 3.00 10.0020.00000 30.00000 100.000000.00 1.00 4.00 10.000.00000 50.00000 60.00000121.664.001.001.600.0010.009.001.672.002.103.001.90
0.33000000 1.20000000 0.00000000 0.30000000 0.00000000 4.80000000 4.20000000 0.33400000 0.40000000 0.43000000 0.70000000 0.38000000
Tax System 1 is analogous to the ordinary income tax system in the US and Tax System 2 is analogous to the capital gains tax system in the US. This is, of course, a simplification of the US tax system. For example, you usually cannot choose how much of your income to distribute to each system. Do not use this material as financial, tax, or legal advice. For guidance on actual tax matters, consult a qualified tax professional or refer to official government resources. Also, do not forget to file your taxes.
This is a run-twice interactive problem.
There is a hurricane brewing in the middle of the Atlantic Ocean and you have some sensors to deploy to track data about the storm, such as wind speeds and trajectory. Over the span of a one-kilometer square, you have placed $$$n$$$ sensors so far, such that each side of the square has at least one sensor on it. The resulting area you can then scan with the sensors is the convex hull of the sensors.
You have one last sensor to place, then you must report the area that you can scan. However, the hurricane is quickly approaching, and with the strength of the hurricane, you know as soon as you get the last sensor in place, you will lose a significant amount of connection to the sensors.
Due to poor planning, you did not write down any of the coordinates of the sensors, and now only have access to one satellite that can communicate with the sensors. The satellite can ping a location within or on a five-kilometer square, however you do not know exactly where the original square is located, only that it is fully within or on the boundaries of the new square. The result of a ping will tell you whether that location is within or on the convex hull of the sensors. Using at most $$$10000$$$ pings, you must determine the area of sensors' convex hull.
This problem will be modeled as a run-twice interactive problem.
First Run
The first line of input consists of the word ADD.
The second line of input consists of a single integer, $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of initial sensors placed.
The following $$$n$$$ lines consist of two integers, $$$x_i$$$ and $$$y_i$$$ ($$$0 \leq x_i, y_i \leq 1000$$$) — the point corresponding to the location of the $$$i$$$-th sensor. It is guaranteed that no two given points will be equal, and that each side of the bounding square will contain at least one point.
You must print two integers $$$x_a$$$ and $$$y_a$$$ ($$$0 \leq x_a, y_a \leq 1000$$$) — the point corresponding to the location of the added sensor.
Second Run
The first line of input consists of the word AREA.
You can make at most $$$10^4$$$ queries by printing QUERY x y ($$$0 \leq x, y \leq 5000$$$), where $$$x$$$ and $$$y$$$ are integers. The interactor will reply with INSIDE if the point is inside (or on) the convex hull of all $$$n+1$$$ sensors, and OUTSIDE otherwise. It is guaranteed that the coordinates of the sensors are integers in the range $$$0$$$ to $$$5000$$$, inclusive, and that their relative positions to each other were not altered. That is, for all $$$i$$$ and $$$j$$$, the vector spanning point $$$i$$$ to point $$$j$$$ is equivalent in both coordinate systems.
Once you have determined the area of the sensors' convex hull, output a single line consisting of AREA A, where $$$A$$$ is an integer corresponding to the twice the area of the convex hull. It can be proven that doubling the area will always result in an integer value.
If at any point in the second run:
- your program outputs an incorrect value of $$$A$$$;
- your program outputs a line that doesn't match a format outlined above;
- your program uses more than $$$10000$$$ queries;
- your program outputs a coordinate outside of the $$$5000$$$ by $$$5000$$$ bounding box;
The interactor is NOT adaptive. That is, the location of the initial bounding box will be determined before the second pass, and at no point will its location change regardless of what your program does.
ADD 4 0 500 1000 500 500 0 500 1000
500 500
AREA OUTSIDE INSIDE
QUERY 0 0 QUERY 2500 2500 AREA 1000000
Sachin was investigating IPv6 addresses and the way they were compressed, and this gave him an idea for a new compression scheme. First, you have an address of $$$n$$$ hexadecimal characters. Hexadecimal characters are the digits $$$0-9$$$ and the letters $$$a-f$$$. They are separated into blocks of $$$k$$$ hexadecimal characters with colons in between blocks. To compress the string, perform the following process:
- Pick a hexadecimal character $$$c$$$ and remove all occurrences of c in the string.
- Remove as few colons as possible so that there are no more than 2 colons in a row.
Sachin wants to know for a given string the smallest compression length. He also wants to see how changing the string affects the compression length, so he will give you multiple queries. In the $$$i$$$-th query, he will change all characters in the range $$$[l_i, r_i]$$$ in the string to the character $$$c_i$$$. After each query, report the smallest compression length.
The first line of input consists of two integers $$$n$$$ and $$$k$$$ $$$(1 \le k \le n \le 10^5)$$$ — the length of the string and the block size, respectively. It is guaranteed that $$$n$$$ is a multiple of $$$k$$$.
The second line of input consists of a string of $$$n$$$ characters, where each character is a hexadecimal character ($$$0-9,a-f$$$).
The third line of input consists of a single integer $$$q$$$ $$$(1 \le q \le 10^5)$$$ — the number of queries.
The next $$$q$$$ lines of input each consist of two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$, as well as a hexadecimal character $$$c_i$$$.
Output $$$q$$$ lines, where the $$$i$$$-th line consists of a single integer representing the smallest compression length of the string after processing the first $$$i$$$ queries.
8 20a80f2c352 3 04 6 e8 8 c2 5 52 7 9
7 8 8 7 4
After the first query in the example, the uncompressed string is 00:00:f2:c3. The optimal character to remove is '0', which results in ::f2:c3. Since there are no more than 2 colons in a row, no colons can be removed and the answer is 7.
After the fifth query in the example, the uncompressed string is 09:99:99:9c. The optimal character to remove is '9', which results in 0:::c. One colon needs to be removed, resulting in 0::c with a length of 4.
Let $$$k \geq 2$$$. Define a $$$k$$$-star as a tree with $$$k+1$$$ nodes, such that there is one central node connected to exactly $$$k$$$ leaves. A $$$k$$$-star set is a non-empty graph where each connected component of that graph is a $$$k$$$-star. For a given tree, count the number of subsets of edges, such that the graph composed of just those edges and nodes that are endpoints of those edges forms a $$$k$$$-star set.
The first line of input consists of two integers $$$n$$$ and $$$k$$$ ($$$2 \leq k \lt n \leq 2 \cdot 10^5$$$) — the number of nodes in the given tree and the size of each target star.
The following $$$n-1$$$ lines each consist of two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$), denoting that there is an edge between nodes $$$u$$$ and $$$v$$$.
Output a single integer denoting the number of $$$k$$$-star sets of the given tree. Since this number can be large, output the answer under modulo $$$998244353$$$.
5 31 52 53 54 5
4
7 21 21 32 43 53 63 7
11
Determine how many non-empty subsets of the numbers from $$$1$$$ to $$$n$$$ there are such that the least common multiple (LCM) of the numbers in the subset is a multiple of $$$k$$$.
The first line of input will consist of a single integer $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of test cases.
Each of the next $$$t$$$ lines will consist of two integers $$$n$$$ and $$$k$$$ $$$(1 \le n,k \le 10^{18})$$$.
It is also guaranteed that all $$$n$$$ and $$$k$$$ can be factorized with primes smaller than $$$10^6$$$.
Since the output can be large, print it modulo $$$998244353$$$.
44 46 617 106 7
8441143040
One day, Sachin's password $$$p$$$ was found in a leaked passwords database. Since Sachin refuses to remember more than 1 password, this means he now has to change his password on every single account he has. Instead of coming up with a new password, he decides to make his new password derivable from his old one with the following transformation:
- Add every substring of $$$p$$$ to a list. If string $$$s$$$ is a substring of $$$p$$$ multiple times, then it will appear in the list multiple times.
- Sort the list lexicographically.
- Concatenate the list into a new string $$$p'$$$.
- Use the $$$L$$$-th to $$$R$$$-th characters of $$$p'$$$ as the new password.
Determine what Sachin's new password should be.
The first line of input consists of a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$ — the length of Sachin's password $$$p$$$.
The second line of input consists of two integers $$$L$$$ and $$$R$$$ $$$(1 \le L \le R \le {n+2 \choose 3})$$$ — the substring of $$$p'$$$ to use as the new password.
The third line of input consists of a single string of $$$n$$$ lowercase English letters — Sachin's old password $$$p$$$.
It is guaranteed that $$$R-L+1\le 10^6$$$.
Output a single string of $$$R-L+1$$$ characters — Sachin's new password.
31 10aba
aaabababba
32 6aba
aabab
75 17bbbcaaa
aaaaaabbbbbbb
It's a ****ing boat, and it's full of pirates
Captain Oliver is plotting a new expedition for his pirate crew. His navigation skills aren't the strongest, so he decided to randomly choose a point on the shore and a direction. He is now curious about his probability of reaching the opposite shore across the sea. He has now asked for your help to determine this probability by modeling it as a geometry problem!
He has modeled each shore as a polyline in the Cartesian plane, each starting at $$$x = 0$$$ and ending at the same value of $$$x$$$. Since the shores are separated by a sea, it is guaranteed that the maximum y value of the starting shore is strictly less than the minimum y of the ending shore. In addition, there are no bays; therefore, it is guaranteed that for each polyline, the x values of the points are strictly increasing.
Captain Oliver will then pick a point $$$p$$$ uniformly randomly on the starting polyline. Let $$$\vec{n}$$$ be the normal vector to the segment that $$$p$$$ is on, pointing towards the sea (i.e., it has a positive y component). Relative to $$$\vec{n}$$$, he will then pick an angle, $$$\theta$$$ ($$$-\frac{\pi}{2} \leq \theta \leq \frac{\pi}{2}$$$), with a probability density function of $$$\frac{\cos(\theta)}{2}$$$. The boat's trajectory is then the ray starting at $$$p$$$ and traveling at angle $$$\theta$$$, in respect to $$$\vec{n}$$$. A trajectory reaches the opposite shore if it intersects the ending polyline and only intersects the starting polyline at $$$p$$$.
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$2 \leq n, m \leq 10^6$$$) — the number of points on the starting shore's polyline, and the number of points on the ending shore's polyline.
The following $$$n$$$ lines will each contain two integers, $$$x_{s, i}$$$ and $$$y_{s, i}$$$ ($$$0 \leq x_{s, i}, y_{s, i} \leq 10^9$$$) — the $$$i$$$-th point on the starting shore's polyline. It is guaranteed that $$$x_{s, i} \lt x_{s, i+1}$$$ for all $$$i \in [1, n-1]$$$.
The following $$$m$$$ lines will each contain two integers, $$$x_{e, i}$$$ and $$$y_{e, i}$$$ ($$$0 \leq x_{e, i}, y_{e, i} \leq 10^9$$$) — the $$$i$$$-th point on the ending shore's polyline. It is guaranteed that $$$x_{e, i} \lt x_{e, i+1}$$$ for all $$$i \in [1, m-1]$$$.
It is guaranteed that the maximum value of $$$y_{s, i}$$$ is strictly less than the minimum value of $$$y_{e, i}$$$ and that $$$x_{s,1} = x_{e,1} = 0$$$ and $$$x_{s,n} = x_{e,m}$$$.
Output a single real number — the probability that the trajectory successfully reaches the ending shore. Your answer will be accepted if it has an absolute or relative error of $$$10^{-6}$$$ with the judge's solution.
3 30 01 32 00 41 52 4
0.0911512657
5 70 02 23 14 26 00 61 32 43 74 45 36 6
0.3715825446
Puzzle Boy is back for more! Ben's favorite hobby is puzzles (which is why he's referred to as Puzzle Boy). After he easily solved Nic's previous puzzle, Nic wants to give him a different kind of challenge. Nic has devised a word game played with a starting dictionary. In this game, Ben and Nic take turns writing new words in the dictionary, with Ben starting first. The person who can't think of a word to add to the dictionary on their turn loses the game.
The original set of rules for words in the dictionary is as follows:
- All of the words in the dictionary must be $$$m$$$ letters long.
- Each word will only use the first $$$c$$$ letters of the English alphabet.
- The words in the dictionary may not be distinct.
A newly added word $$$w$$$ also has to follow these additional rules:
- The new word should be related to some word already in the dictionary. Therefore, there must exist some index $$$i$$$ and word $$$d$$$ that is already in the dictionary such that $$$w_i=d_i$$$.
- The new word must be novel and unique. Therefore, there must exist some index $$$i$$$ where the letter $$$w_i$$$ is not used at index $$$i$$$ for any other word already in the dictionary.
Ben and Nic played a few rounds of the game with different starting dictionaries. At first, Ben would lose most of the time. But after saying "I understand it now," Ben started winning the majority of the games. To test whether Puzzle Boy truly solved the puzzle, Nic has challenged him to determine the number of different words he can add in the first turn of the game and win the game. Assume both Ben and Nic play optimally.
The first line of input will consist of three integers $$$n$$$, $$$m$$$ $$$(2 \le n,m \le 10^3)$$$, and $$$c$$$ $$$(2 \le c \le 26)$$$ — the number of words in the dictionary, the length of each word, and the number of letters in the English alphabet that can be used.
The following $$$n$$$ lines will each consist of a single string of $$$m$$$ lowercase letters using only the first $$$c$$$ letters of the English alphabet.
It is guaranteed that Ben can add a word to the dictionary at the beginning of the game.
Output a single integer: the number of starting words that Ben can add to the dictionary on his first turn and win the game. Since this number can be large, output it modulo $$$998244353$$$.
2 3 2aaaaba
2
2 2 2aaaa
0
However, Samarth is rusty when it comes to reading. He's never been particularly good at it and always had an ICPC teammate read problems for him. So when Samarth read the one sentence problem statement in Trapping Rain Water, he did not realize that the 2D structure is an elevation map. Instead, Samarth has the following assumptions about the 2D structure:
- The 2D structure is given as a grid of cells denoted by 'x' and '.', where '.' represents an empty cell and 'x' represents a block in a cell.
- The bottom row of the 2D structure is a fully occupied row of blocks.
Samarth also has the following assumptions about how water works:
- Water can only flow through empty cells (specifically, it can't flow through the space between adjacent blocks or between diagonally adjacent blocks).
- Water doesn't stick to blocks; if water runs down the side of a block, it won't stick to the bottom of the block.
- Water doesn't spread while falling. It falls straight downward due to gravity.
- Water that exits the grid will never enter the grid again.
- Air bubbles will not form when water flows into a trapped space.
- It rains for an arbitrarily long amount of time, and then the water will drain for an arbitrarily long amount of time.
- The siphon effect does not apply.
Help Samarth determine which cells will trap rain water. After all, how hard can a LeetCode problem be?
The first line of input consists of two integers $$$n$$$ and $$$m$$$ $$$(3 \le n,m \le 10^6, n\cdot m \le 10^6)$$$ — the dimensions of the grid.
The following $$$n$$$ lines of input each contain a row of the grid, represented as a string of $$$m$$$ characters which are either '.' or 'x'.
It is guaranteed that the last row of the grid only has 'x'.
Output the grid after it has rained. Specifically, output $$$n$$$ lines of $$$m$$$ characters each. Each character in the grid should be 'x' (block), '.' (empty cell), or '$$$\texttt{\textasciitilde}$$$' (filled with water).
5 12...................x.......x...xx.x..x.xx.xxxxxxxxxxxxxxxxxx
............ .......x.... ...x~~~xx~x. .x~xx~xxxxxx xxxxxxxxxxxx
7 5.....x...xx...xxx.xxx.x.xx...xxxxxx
..... x~~~x x~~~x xx~xx x.x.x x...x xxxxx
8 7xxx.xxx........xx.x.....xx.........xx.x...x..x..xxxxxxxx
xxx.xxx ....... .xx~x.. ...xx.. ....... xx~x... x~~x~~x xxxxxxx
7 7xxx.xxx..............x.xxx..x.x.x.xx.....xxxxxxxx
xxx.xxx ....... ....... x.xxx.. x~x~x~x x~~~~~x xxxxxxx
5 7xxxxx.x....x..x.x.x.xx.x...xxxxxxxx
xxxxx.x ....x.. x~x~x~x x~x~~~x xxxxxxx
Sahur has taken up gardening, and it's time for his annual checkup on one of the hedges he is maintaining. The hedge is represented as a series of segments of greenery of varying heights, represented by an array of $$$n$$$ integers. To clean up the hedge, he needs to trim it so that every part of the hedge is the same height (he is fine with any height; he just wants it to be uniform).
To do this, he can use some of the strange-looking razors that he bought at a yard sale. Each razor is much longer than the hedge and has cutting blades that are one segment wide and evenly spaced apart on the razor. For every positive integer $$$k$$$, he has a razor with $$$k$$$ segments of free space between each blade on the razor. In one application of a razor, he can line up the blades with some segments of the hedge, lift the razor to a certain height, and cut the hedge. A cut is applied simultaneously to all hedge segments that line up with the razor blades. If the hedge segment is taller than the blade, it will get cut down to the blade's height. Otherwise, the segment will not be cut. Since Sahur is lazy, he wants to minimize the number of times he has to use a razor to cut the hedge to his specifications.
The first line of input consists of one integer $$$n$$$ $$$(1 \le n \le 10^6)$$$, the size of the array.
The second line of input consists of $$$n$$$ integers $$$h_1,h_2,...,h_n$$$ $$$(1 \le h_i \le 10^6)$$$ — the heights of the segments of the hedge.
Output a single integer — the minimum number of times Sahur needs to use a razor to cut the hedge.
51 1 1 1 1
0
35 6 7
2