People are ready for vacation. One thing people like to do during vacation is going to amusement parks.
Kantipa is an operator of an amusement park ride. There are $$$N$$$ people queueing to ride the ride. These people are numbered from $$$1$$$ to $$$N$$$ in order from front to back. Each person has a value $$$A_i$$$.
Kantipa can ignore the popular convention of a queue and make these people ride the ride in any order that she allows. The ordering can be any of the $$$N!$$$ possible orderings. For an ordering of who rides the ride first which Kantipa decides on, the anger level of person $$$i$$$ is calculated as follows:
- Let $$$p$$$ signify that person $$$i$$$ is the $$$p$$$-th person who rides the ride.
- Let $$$s$$$ be the sum of the values of $$$A_j$$$ for every person $$$j$$$ that is further back than person $$$i$$$ in the queue but rides the ride earlier than person $$$i$$$.
- The anger level of person $$$i$$$ is $$$p\times A_i + s$$$.
For an ordering of who rides the ride first, the total anger level is the sum of anger levels of the entire $$$N$$$ people.
There are $$$N!$$$ possible orderings. Kantipa wants to construct an array of size $$$N!$$$ consisting of all of the total anger levels for every single ordering. Kantipa has an integer $$$K$$$, she wants to sort that array in non-decreasing order and get the $$$K$$$-th element. However, doing so manually takes a very long time. Can you help her find the desired value?
The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N \leq 200\,000$$$; $$$1\leq K\leq\min(N!,200\,000)$$$) — the number of people in the queue and the index of the element asked in the sorted array.
The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \leq A_i \leq 200\,000$$$) — the value of each person.
A single integer representing the $$$K$$$-th element in the non-decreasing order of the array of the $$$N!$$$ total anger levels.
3 42 6 5
35
4 71 1 1 1
12
In the first example, consider the $$$6$$$ orderings of who rides the ride first:
- Person $$$1$$$, person $$$2$$$, person $$$3$$$. The total anger level is $$$2+12+15=29$$$.
- Person $$$1$$$, person $$$3$$$, person $$$2$$$. The total anger level is $$$2+23+10=35$$$.
- Person $$$2$$$, person $$$1$$$, person $$$3$$$. The total anger level is $$$10+6+15=31$$$.
- Person $$$2$$$, person $$$3$$$, person $$$1$$$. The total anger level is $$$17+6+10=33$$$.
- Person $$$3$$$, person $$$1$$$, person $$$2$$$. The total anger level is $$$9+23+5=37$$$.
- Person $$$3$$$, person $$$2$$$, person $$$1$$$. The total anger level is $$$17+17+5=39$$$.
The sorted array is $$$[29, 31, 33, 35, 37, 39]$$$.
Assume you are a highly intelligent person that has perfect logic. Hence, you will not gamble under any circumstances, but this time you are forced to and have no choice.
You are given $$$N$$$ dice, each dice has $$$M$$$ faces. Let the number on the $$$j$$$-th face of the $$$i$$$-th dice be $$$A_{i,j}$$$.
Initially, all dice are not locked. You have exactly $$$N$$$ turns to make all dice locked in the end. Each turn is the following steps:
- Roll all dice that are not locked. For each dice that's rolled, each of the $$$M$$$ faces has an equal probability to show up.
- Then, after seeing the faces, you choose exactly one dice to lock. This locked dice will remain locked until the end of the game and can't be relocked.
The final score is the sum of values on the shown faces of all dice in the end.
Being the perfect logician you are, in any situation, you'll always do moves that maximizes your expected final score. What is the expected value of your score?
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 12$$$; $$$1 \leq M \leq 1000$$$) — the number of dice and the number of faces for each dice.
The $$$i$$$-th of the next $$$N$$$ lines contains $$$M$$$ integers $$$A_{i,1}, A_{i,2}, \ldots, A_{i,M}$$$ ($$$1 \leq A_{i,j} \leq 10^9$$$) — the value in each face for the $$$i$$$-th dice.
A single real number representing the expected value of your score.
Your answer is considered correct if the relative or absolute error of your answer doesn't exceed $$$10^{-4}$$$. Formally, let your answer be $$$a$$$ and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a-b|}{\max(1,b)}\leq10^{-4}$$$.
2 21 32 2
4.5000000000
4 58 7 6 5 72 3 4 5 31 8 8 8 87 7 8 7 6
26.6129577984
In the first example, after the first roll, the two possible configurations of values shown on the two dice are $$$[1,2]$$$ and $$$[3,2]$$$, each having a probability of $$$\frac{1}{2}$$$ of happening.
- If $$$[1,2]$$$ shows up, it's better to lock dice $$$2$$$. After that, you roll dice $$$1$$$, which itself can result in a value of $$$1$$$ or $$$3$$$ with equal probability. This means, the final configurations $$$[1,2]$$$ and $$$[3,2]$$$ from this scenario each has an overall probability of $$$\frac{1}{4}$$$.
- If $$$[3,2]$$$ shows up, it's better to lock dice $$$1$$$. After that, you roll dice $$$2$$$, which itself always results in a value of $$$2$$$. This means, the final configuration $$$[3,2]$$$ from this scenario has an overall probability of $$$\frac{1}{2}$$$.
The expected value of the total score overall is $$$(1+2)\times\frac{1}{4}+(3+2)\times\frac{1}{4}+(3+2)\times\frac{1}{2}=4.5$$$.
A GE-string is a string where each of its characters is either $$$\texttt{G}$$$ or $$$\texttt{E}$$$. A GE-string is said to be alternating if and only if there is no pair of the same character that are adjacent.
We can partition a GE-string into one or more subsequences of characters such that each character is in exactly one subsequence. A partition is valid if and only if each subsequence is alternating. A valid partition of a GE-string is minimum if and only if it partitions the GE-string into the minimum number of subsequences out of all possible valid partitions for that GE-string.
The score of a GE-string is the number of different minimum valid partitions for that GE-string. Two partitions are different if and only if two characters are in the same subsequence in one partition, but they are in different subsequences in the other partition.
Kantipa has a string $$$S$$$ that is a GE-string of length $$$N$$$. Calculate the score of $$$S$$$. Print the answer modulo $$$998\,244\,353$$$.
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 200\,000$$$) — the length of $$$S$$$.
The second line contains a string $$$S$$$ of length $$$N$$$ consisting of characters $$$\texttt{G}$$$ or $$$\texttt{E}$$$.
An integer representing the score of $$$S$$$, modulo $$$998\,244\,353$$$.
7GEGGGEG
9
6EEEEEE
1
In the first example, the minimum number of subsequences out of all possible valid partitions is $$$3$$$. There are $$$9$$$ different ways to partition $$$\texttt{GEGGGEG}$$$ into $$$3$$$ subsequences. The following are possible sets of the sets of indices for the $$$3$$$ subsequences:
- $$$\{\{1, 2, 3\}, \{4\}, \{5, 6, 7\}\}$$$
- $$$\{\{1, 2, 3\}, \{4, 6, 7\}, \{5\}\}$$$
- $$$\{\{1, 2, 3, 6, 7\}, \{4\}, \{5\}\}$$$
- $$$\{\{1, 2, 4\}, \{3\}, \{5, 6, 7\}\}$$$
- $$$\{\{1, 2, 4\}, \{3, 6, 7\}, \{5\}\}$$$
- $$$\{\{1, 2, 4, 6, 7\}, \{3\}, \{5\}\}$$$
- $$$\{\{1, 2, 5\}, \{3\}, \{4, 6, 7\}\}$$$
- $$$\{\{1, 2, 5\}, \{3, 6, 7\}, \{4\}\}$$$
- $$$\{\{1, 2, 5, 6, 7\}, \{3\}, \{4\}\}$$$
In the second example, there's only one possible minimum valid partition, which is achieved by making every single character its own subsequence.
Natsuho, an Indonesian girl, wants to have a vacation in Japan. When browsing plane ticket prices, she sees that the prices are in yen (Japanese currency), but she's only familiar with rupiahs (Indonesian currency). It's known that in this universe, $$$1$$$ yen is equal to $$$100$$$ rupiahs.
Let's say we have a price that's a positive integer in yen. Let's say it's $$$N$$$ digits long. How many digits will it have if the price is converted into rupiahs?
The only line contains a single integer $$$N$$$ ($$$1 \leq N \leq 18$$$) — the number of digits in the price in yen.
A single integer representing the number of digits in the price if it's converted into rupiahs.
1
3
9
11
In the first example, any $$$1$$$-digit positive integer ($$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$8$$$, or $$$9$$$) in yen, when converted into rupiahs, with turn into $$$100$$$, $$$200$$$, $$$300$$$, $$$400$$$, $$$500$$$, $$$600$$$, $$$700$$$, $$$800$$$, or $$$900$$$. Every single one of those has $$$3$$$ digits.
Kantipa wants to make a board game that takes place on a grid. The grid is an $$$N\times N$$$ grid with $$$N$$$ rows and $$$N$$$ columns. The rows are numbered from $$$1$$$ to $$$N$$$ from top to bottom and the columns are numbered from $$$1$$$ to $$$N$$$ from left to right. The tile in row $$$x$$$ and column $$$y$$$ is denoted as $$$(x, y)$$$. There are $$$D$$$ special tiles with the $$$i$$$-th special tile being tile $$$(R_i, C_i)$$$. It's guaranteed that the special tiles are pairwise distinct.
In each level of the game, there's a start tile and a goal tile. The player has one game piece that's initially located in the start tile in the beginning of the level. A piece in tile $$$(x, y)$$$ can do one of the following five moves:
- Move to $$$(x-1, y)$$$. This takes $$$1$$$ second.
- Move to $$$(x, y-1)$$$. This takes $$$1$$$ second.
- Move to $$$(x+1, y)$$$. This takes $$$1$$$ second.
- Move to $$$(x, y+1)$$$. This takes $$$1$$$ second.
- Move to $$$(x', y')$$$ such that $$$(x', y') \neq (x, y)$$$ and one of the following is satisfied:
- $$$x'+y' = x+y$$$
- $$$x'-y' = x-y$$$
Note that in a move, the piece cannot go outside the grid. A level ends once the player's piece lands on the goal tile. Since the bishop move is very overpowered, each level limits the maximum number of times the player can do the bishop move in that level.
To make an entire board game, Kantipa must make a sequence of exactly $$$K$$$ levels. The sequence of levels can be represented as three arrays $$$S$$$, $$$G$$$, and $$$L$$$, each with length $$$K$$$, such that $$$1\leq S_j,G_j\leq D$$$ and $$$0\leq L_j\leq B$$$ (the constant $$$B$$$ is given). These three arrays signify a sequence of levels where in the $$$j$$$-th level, the start tile is the $$$S_j$$$-th special tile, the goal tile is the $$$G_j$$$-th special tile, and the maximum number of times the player can do the bishop move is $$$L_j$$$.
The sequence of levels must follow the following restrictions:
- For each level, the start tile must be different from the goal tile ($$$S_j\neq G_j$$$ must hold).
- The minimum amount of time to complete each of the $$$K$$$ levels in the sequence must be strictly increasing.
Note that a special tile can be used as a start tile or a goal tile multiple times, if used in different levels.
Find the number of different valid sequences of levels. Since the number can be very large, print it modulo $$$998\,244\,353$$$.
Two sequences of levels are said to be different if and only if at least one of $$$S$$$, $$$G$$$, or $$$L$$$ in both sequences are different.
The first line contains four integers $$$N$$$, $$$D$$$, $$$K$$$, and $$$B$$$ ($$$1 \leq N \leq 100\,000$$$; $$$1 \leq D \leq \min(100\,000,N^2)$$$; $$$1 \leq K,B \leq 100\,000$$$) — the size of the board, the number of special tiles, the number of levels in a valid sequence, and the maximum limit for the value of $$$L_j$$$.
The $$$i$$$-th of the next $$$D$$$ lines contains two integers $$$R_i$$$ and $$$C_i$$$ ($$$1\leq R_i,C_i\leq N$$$) — the location of each special tile. The special tiles are pairwise distinct.
An integer representing the number of different valid sequences of levels modulo $$$998\,244\,353$$$.
5 4 5 23 41 14 13 3
15168
2 2 2 21 12 2
8
In the first example, an example of a valid sequence of levels is $$$S = [2, 3, 3, 3, 2]$$$, $$$G = [4, 2, 1, 2, 1]$$$, $$$L = [1, 2, 1, 1, 0]$$$. Each level of this game is described as follows:
- In the $$$1$$$-st level, the start tile is $$$(1, 1)$$$, the goal tile is $$$(3, 3)$$$, the bishop move limit is $$$1$$$. A way to get the minimum time is from $$$(1, 1)$$$, bishop move to $$$(3, 3)$$$. This takes $$$0$$$ seconds.
- In the $$$2$$$-nd level, the start tile is $$$(4, 1)$$$, the goal tile is $$$(1, 1)$$$, the bishop move limit is $$$2$$$. A way to get the minimum time is from $$$(4, 1)$$$, bishop move to $$$(2, 3)$$$, move to $$$(2, 2)$$$, bishop move to $$$(1, 1)$$$. This takes $$$1$$$ second.
- In the $$$3$$$-rd level, the start tile is $$$(4, 1)$$$, the goal tile is $$$(3, 4)$$$, the bishop move limit is $$$1$$$. A way to get the minimum time is from $$$(4, 1)$$$, move to $$$(5, 1)$$$, bishop move to $$$(2, 4)$$$, move to $$$(3, 4)$$$. This takes $$$2$$$ seconds.
- In the $$$4$$$-th level, the start tile is $$$(4, 1)$$$, the goal tile is $$$(1, 1)$$$, the bishop move limit is $$$1$$$. A way to get the minimum time is from $$$(4, 1)$$$, move to $$$(3, 1)$$$, move to $$$(2, 1)$$$, move to $$$(1, 1)$$$. This takes $$$3$$$ seconds.
- In the $$$5$$$-th level, the start tile is $$$(1, 1)$$$, the goal tile is $$$(3, 4)$$$, the bishop move limit is $$$0$$$. A way to get the minimum time is from $$$(1, 1)$$$, move to $$$(1, 2)$$$, move to $$$(2, 2)$$$, move to $$$(3, 2)$$$, move to $$$(3, 3)$$$, move to $$$(3, 4)$$$. This takes $$$5$$$ seconds.
Notice that the minimum amount of time to complete each level is strictly increasing. Since this meets all requirements, this is a valid sequence of levels.
In the second example, the following is every possible sequence of levels that's valid:
- $$$S=[1,1]$$$, $$$G=[2,2]$$$, $$$L=[1,0]$$$
- $$$S=[1,1]$$$, $$$G=[2,2]$$$, $$$L=[2,0]$$$
- $$$S=[1,2]$$$, $$$G=[2,1]$$$, $$$L=[1,0]$$$
- $$$S=[1,2]$$$, $$$G=[2,1]$$$, $$$L=[2,0]$$$
- $$$S=[2,1]$$$, $$$G=[1,2]$$$, $$$L=[1,0]$$$
- $$$S=[2,1]$$$, $$$G=[1,2]$$$, $$$L=[2,0]$$$
- $$$S=[2,2]$$$, $$$G=[1,1]$$$, $$$L=[1,0]$$$
- $$$S=[2,2]$$$, $$$G=[1,1]$$$, $$$L=[2,0]$$$
Kantipa wants to coordinate a dance performance where the dancers sit while dancing. The dance consists of $$$N$$$ dancers sitting in a single row. The stage consists of $$$10^{100}$$$ pre-made slots for the dancers to sit, numbered from $$$1$$$ to $$$10^{100}$$$ from left to right. These slots are equally spaced.
A configuration of the $$$N$$$ dancers is valid if and only if all of the following are satisfied:
- The dancers sit on different slots.
- There exists an integer $$$k$$$ such that for any pair of two dancers with no other dancers between them, the distance between the two is $$$k$$$. Such valid configuration is said to be $$$k$$$-separated.
There are $$$N$$$ dancers numbered from $$$1$$$ to $$$N$$$. Initially, all $$$N$$$ dancers are sitting on different slots among slots $$$1$$$ through $$$N$$$. In other words, there exists an array $$$P$$$ that's a permutation of $$$[1,2,\ldots,N]$$$ such that dancer $$$i$$$ is initially sitting on slot $$$P_i$$$.
For a permutation $$$P$$$, Kantipa defines the value of $$$f(x)$$$ ($$$0\leq x\leq N-2$$$) as the number of different values of $$$\mathbf{k}$$$ such that Kantipa can rearrange the positions of dancers $$$1$$$ through $$$x$$$ to any slots to make the configuration $$$k$$$-separated, while not changing the positions of dancers $$$x+1$$$ through $$$N$$$.
Find any permutation $$$P$$$ such that the value of $$$f(0)+f(1)+f(2)+\ldots+f(N-2)$$$ is as big as possible! If there are multiple solutions, output any of them.
The only line contains a single integer $$$N$$$ ($$$2 \leq N \leq 300\,000$$$) — the number of dancers.
Print $$$N$$$ integers in one line. The $$$i$$$-th integer is the value of $$$P_i$$$ (the initial position of dancer $$$i$$$). If there are multiple solutions, output any of them.
5
4 2 3 5 1
For $$$f(0)$$$, we can only do nothing, which would make it $$$1$$$-separated, so $$$f(0)=1$$$.
For $$$f(1)$$$, by being able to rearrange the position of dancer $$$1$$$, we can still only make it $$$1$$$-separated, so $$$f(1)=1$$$.
For $$$f(2)$$$, by being able to rearrange the positions of dancers $$$1$$$ and $$$2$$$, not only can we make it $$$1$$$-separated, we can also make it $$$2$$$-separated by moving dancer $$$1$$$ to slot $$$9$$$ and moving dancer $$$2$$$ to slot $$$7$$$, so $$$f(2)=2$$$.
For $$$f(3)$$$, by being able to rearrange the positions of dancers $$$1$$$, $$$2$$$, and $$$3$$$, not only can we make it $$$1$$$-separated and $$$2$$$-separated, we can also make it $$$4$$$-separated by moving dancer $$$1$$$ to slot $$$9$$$, moving dancer $$$2$$$ to slot $$$17$$$, and moving dancer $$$3$$$ to slot $$$13$$$, so $$$f(2)=3$$$.
Therefore, $$$f(0)+f(1)+f(2)+f(3)=7$$$, which is the biggest possible value of this sum for $$$5$$$ dancers.
There's a cartoon show you made called Comet Universe that you're working on by yourself. After releasing the pilot episode (episode $$$0$$$) which got a perfect rating of $$$10$$$, you plan to release $$$N$$$ episodes, numbered from $$$1$$$ to $$$N$$$. To release the episodes, you want to do what's called a comet bomb.
You have $$$N\times M$$$ days to work on your cartoon, numbered from $$$1$$$ to $$$N\times M$$$. For each episode $$$i$$$ ($$$1\leq i\leq N$$$), you have to finish it by the end of day $$$i\times M$$$ so the episode can air by that time. For each day, you can only choose to work on one episode. An episode is said to be ready if you've worked on it for a total of at least $$$A$$$ days. An episode is said to be excellent if you've worked on it for a total of at least $$$B$$$ days ($$$B\geq A$$$).
When an episode airs, there are three cases:
- If it's excellent, then it'll get a perfect rating of $$$10$$$.
- If it's only ready, but not excellent, then it'll get a rating of $$$\max(r-1,0)$$$ with $$$r$$$ being the rating of the previous episode. (Note that episode $$$0$$$ got a rating of $$$10$$$).
- If it's not ready, then your entire cartoon show will become a disappointment and will be canceled immediately, with the audience completely forgetting about the entire thing. Because of that, you won't let that happen.
What's the maximum possible sum of ratings of episodes $$$1$$$ through $$$N$$$ if every episode must be ready when it airs? Or report if it's impossible!
The only line contains four integers $$$N$$$, $$$M$$$, $$$A$$$, and $$$B$$$ ($$$1\leq N,M\leq100\,000$$$; $$$1\leq A\leq B\leq100\,000$$$) — the number of episodes, the number of days between episodes, the number of days for an episode to be ready, and the number of days for an episode to be excellent.
A single integer representing the maximum possible sum of ratings of episodes $$$1$$$ through $$$N$$$ if every episode must be ready when it airs, or report -1 it's impossible.
4 3 2 5
36
1 10 100 1000
-1
In the first example, you can do the following for each day:
- Work on episode $$$1$$$.
- Work on episode $$$3$$$.
- Work on episode $$$1$$$.
- Episode $$$1$$$ airs with a rating of $$$9$$$.
- Work on episode $$$3$$$.
- Work on episode $$$2$$$.
- Work on episode $$$2$$$.
- Episode $$$2$$$ airs with a rating of $$$8$$$.
- Work on episode $$$3$$$.
- Work on episode $$$3$$$.
- Work on episode $$$3$$$.
- Episode $$$3$$$ airs with a rating of $$$10$$$.
- Work on episode $$$4$$$.
- Work on episode $$$4$$$.
- Work on episode $$$4$$$.
- Episode $$$4$$$ airs with a rating of $$$9$$$.
The sum of ratings of episodes $$$1$$$ through $$$4$$$ is $$$9+8+10+9=36$$$.
In the famous company of Limas Agung (Indonesian for Great Pyramid), there are multiple career paths that one can take when dedicating their work into this company. There are $$$N$$$ job titles, each with its own integer salary, and $$$N-1$$$ promotions. Each of the job titles except job title $$$1$$$ has only one possible promotion path, that is job title $$$i$$$ can be promoted to job title $$$P_i$$$ in exactly one year ($$$1 \leq P_i \lt i$$$). A job title is considered entry-level if no other job title promotes to it.
The company hasn't decided on the salary of each job title yet, but there are some restrictions. The company has a minimum wage of $$$L$$$ and a maximum wage of $$$H$$$. Every single entry-level job title has minimum wage salary. Any promotion will never decrease the salary. The company also implements a policy, "Wherever you are in the company ladder, the raise you will get from this year to the next year is never less than the raise you get from last year to this year."
In more formal words, you're tasked to construct an array $$$S$$$ (with $$$S_i$$$ being the salary of job title $$$i$$$) such that:
- $$$L \leq S_i \leq H$$$
- $$$S_i = L$$$ for every entry-level job title.
- $$$S_i \leq S_{P_i}$$$
- $$$S_{P_i}-S_i \leq S_{P_{P_i}}-S_{P_i}$$$
When considering every possible configuration, the company wonders, how much is the biggest possible value of the total salaries that satisfies these conditions (the biggest possible value of $$$S_1+S_2+\ldots+S_N$$$)?
The first line contains three integers $$$N$$$, $$$L$$$, and $$$H$$$ ($$$2 \leq N \leq 200\,000$$$; $$$1 \leq L \leq H \leq 10^{12}$$$) — the number of job titles, the minimum wage, and the maximum wage.
The second line contains $$$N-1$$$ integers $$$P_2, P_3, \ldots, P_N$$$ ($$$1 \leq P_i \lt i$$$) — the job title that each job title promotes to.
One number that represents the maximum sum of all salaries.
5 7 111 2 2 3
42
3 23 231 2
69
2 265 47611
5026
In the first example, a configuration of salaries for positions $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, and $$$5$$$ that produces the maximum sum is $$$11$$$, $$$9$$$, $$$8$$$, $$$7$$$, and $$$7$$$
Have you ever wondered about the most effective row and column widths for your data in an Excel sheet? You are given $$$N$$$ rows of data, with each row $$$i$$$ containing three integers $$$X_i$$$, $$$Y_i$$$, and $$$Z_i$$$, located in columns $$$1$$$, $$$2$$$, and $$$3$$$ respectively.
For each of the $$$N$$$ rows, and each of the $$$3$$$ columns, you can set its width. This width would affect the display of every cell within that row or column. This means, a cell in a row with width $$$w_r$$$ and a column with width $$$w_c$$$ has an area of $$$w_r\times w_c$$$. Note that these row and column widths don't have to be integers.
You want to set the widths of the rows and columns such that each cell's area is no less than its corresponding integer given at the start. Find the minimum total area of the entire table that can be made possible!
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 300\,000$$$) — the number of rows.
The $$$i$$$-th of the next $$$N$$$ lines contains three integers $$$X_i$$$, $$$Y_i$$$, and $$$Z_i$$$ ($$$1\leq X_i,Y_i,Z_i\leq 10^9$$$) — the integers in columns $$$1$$$, $$$2$$$, and $$$3$$$ for row $$$i$$$.
Print a single line containing single real number representing the minimum total area of the table that can be made possible.
An answer is considered correct if the relative or absolute error of your answer doesn't exceed $$$10^{-4}$$$. Formally, let your answer be $$$a$$$ and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a-b|}{\max(1,b)}\leq10^{-4}$$$.
4 7 6 5 6 5 4 5 4 3 4 3 6
67.66508
One possible optimal solution is to have the widths of the rows be $$$[2.93939\ldots,2.44949\ldots,2.04124\ldots,3.15076\ldots]$$$ and the widths of the columns be $$$[2.44949\ldots,2.04124\ldots,1.90430\ldots]$$$.
During Kantipa's vacation, from the room she is staying in, Kantipa can see $$$N$$$ mountains that are arranged in a single row. She numbers the mountains from $$$1$$$ to $$$N$$$ from left to right. Then, she constructs a permutation $$$A$$$ that's a permutation of $$$[1, 2, \ldots, N]$$$ which means mountain $$$i$$$ has the $$$A_i$$$-th lowest height out of the $$$N$$$ mountains.
Kantipa wants to take several panoramic photos of these mountains. To take a panoramic photo, she chooses two integers $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq N$$$) and then takes a photo of all mountains from index $$$L$$$ to $$$R$$$. In the photo, Kantipa renumerates the mountains from $$$1$$$ to $$$R-L+1$$$ from left to right.
Kantipa thinks that the most important aspect of a panoramic photo is the position of the highest mountain in the photo. Therefore, she asks you, for each integer $$$k$$$ from $$$1$$$ to $$$N$$$, find the number of different ways to choose $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq N$$$) such that the tallest mountain in the photo is in the $$$k$$$-th position from the left (according to the new numbering in the photo).
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 200\,000$$$) — the number of mountains.
The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ — the height of each mountain. $$$A$$$ is a permutation of $$$[1, 2, \ldots, N]$$$.
A single line containing $$$N$$$ integers, with the $$$k$$$-th integer representing the number of different ways to choose $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq N$$$) such that the tallest mountain in the photo is in the $$$k$$$-th position from the left (according to the new numbering in the photo).
41 2 4 3
5 3 2 0
Consider the following pairs of $$$(L, R)$$$:
- The pairs $$$(1, 1)$$$, $$$(2, 2)$$$, $$$(3, 3)$$$, $$$(3, 4)$$$, $$$(4, 4)$$$ each has the tallest mountain at the $$$1$$$-st position.
- The pairs $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$ each has the tallest mountain at the $$$2$$$-nd position.
- The pairs $$$(1, 3)$$$, $$$(1, 4)$$$ each has the tallest mountain at the $$$3$$$-rd position.
There's a timber wood company that spans several countries. Associated with the company, there are $$$N_0$$$ countries, numbered from $$$0$$$ to $$$N_0-1$$$. In total, there are $$$N_0N_1$$$ cities, numbered from $$$0$$$ to $$$N_0N_1-1$$$ such that city $$$x$$$ belongs in country $$$\lfloor\frac{x}{N_1}\rfloor$$$. In total, there are $$$N_0N_1N_2$$$ locations that the company operates in. These locations are numbered from $$$0$$$ to $$$N_0N_1N_2-1$$$ such that location $$$x$$$ belongs in city $$$\lfloor\frac{x}{N_2}\rfloor$$$.
There is a truck driver who has to drive her truck carrying wood logs around all $$$N_0N_1N_2$$$ locations. The truck must start in any one of these locations, then go to every single one of the other locations any order, then end the journey in any location. She can visit a location more than once.
Since the truck driver likes to pee carelessly wherever she goes, there is an additional restriction to the entire journey. For each city, once the truck leaves the city, it can't go back into that city. The same thing applies to each country. Once the truck leaves a country, it can't go back into that country.
There are three different fees, denoted by three functions $$$f$$$, $$$g$$$, and $$$h$$$, each with two parameters.
- The values of $$$f(x,y)$$$ are defined for all $$$0\leq x \lt y\leq N_0-1$$$.
- The values of $$$g(x,y)$$$ are defined for all $$$0\leq x \lt y\leq N_0N_1-1$$$.
- The values of $$$h(x,y)$$$ are defined for all $$$0\leq x \lt y\leq N_0N_1N_2-1$$$.
For any pair $$$(x,y)$$$ ($$$x \lt y$$$), when the driver wants to drive her truck directly from location $$$x$$$ to location $$$y$$$ or vice versa, she must do all of the following three things:
- If $$$x$$$ and $$$y$$$ are in different countries, she must pay $$$f(\lfloor\frac{x}{N_1N_2}\rfloor,\lfloor\frac{y}{N_1N_2}\rfloor)$$$ gold coins.
- If $$$x$$$ and $$$y$$$ are in different cities, she must pay $$$g(\lfloor\frac{x}{N_2}\rfloor,\lfloor\frac{y}{N_2}\rfloor)$$$ silver coins.
- She must pay $$$h(x,y)$$$ bronze coins.
There are some special properties for the values of functions $$$f$$$ and $$$g$$$.
- For any pair of pairs $$$(x,y)$$$ and $$$(x',y')$$$ ($$$x \lt y$$$; $$$x' \lt y'$$$; $$$(x,y)\neq(x',y')$$$), if $$$f(x,y)\leq f(x',y')$$$ holds, then $$$2f(x,y)\leq f(x',y')$$$ also holds.
- For any pair of pairs $$$(x,y)$$$ and $$$(x',y')$$$ ($$$x \lt y$$$; $$$x' \lt y'$$$; $$$(x,y)\neq(x',y')$$$), if $$$\lfloor\frac{x}{N_1}\rfloor=\lfloor\frac{y}{N_1}\rfloor=\lfloor\frac{x'}{N_1}\rfloor=\lfloor\frac{y'}{N_1}\rfloor$$$ holds and $$$g(x,y)\leq g(x',y')$$$ holds, then $$$2g(x,y)\leq g(x',y')$$$ also holds.
- For any pair of pairs $$$(x,y)$$$ and $$$(x',y')$$$ ($$$x \lt y$$$; $$$x' \lt y'$$$; $$$(x,y)\neq(x',y')$$$), if $$$\lfloor\frac{x}{N_2}\rfloor=\lfloor\frac{y}{N_2}\rfloor=\lfloor\frac{x'}{N_2}\rfloor=\lfloor\frac{y'}{N_2}\rfloor$$$ holds and $$$h(x,y)\leq h(x',y')$$$ holds, then $$$2h(x,y)\leq h(x',y')$$$ also holds.
Gold coins are way more valuable than silver coins, and silver coins are way more valuable than bronze coins. Let's say the total gold, silver, and bronze coins of the entire journey are denoted as $$$p$$$, $$$q$$$, and $$$r$$$. Find the lexicographically minimum array $$$[p,q,r]$$$!
The first line contains three integers $$$N_0$$$, $$$N_1$$$, and $$$N_2$$$ ($$$2 \leq N_0 \leq 11$$$; $$$2 \leq N_1 \leq 10$$$; $$$2 \leq N_2 \leq 9$$$) — the number of countries, the number of cities in each country, and the number of locations in each city.
The $$$i$$$-th of the next $$$N_0-1$$$ lines contains $$$N_0-i$$$ integers $$$f(i-1,i),f(i-1,i+1),f(i-1,i+2),\ldots,f(i-1,N_0-1)$$$ ($$$1\leq f(x,y)\leq10^{17}$$$) — the gold coin costs for travelling between different countries.
The $$$i$$$-th of the next $$$N_0N_1-1$$$ lines contains $$$N_0N_1-i$$$ integers $$$g(i-1,i),g(i-1,i+1),g(i-1,i+2),\ldots,g(i-1,N_0N_1-1)$$$ ($$$1\leq g(x,y)\leq10^{16}$$$) — the silver coin costs for travelling between different cities.
The $$$i$$$-th of the next $$$N_0N_1N_2-1$$$ lines contains $$$N_0N_1N_2-i$$$ integers $$$h(i-1,i),h(i-1,i+1),h(i-1,i+2),\ldots,h(i-1,N_0N_1N_2-1)$$$ ($$$1\leq h(x,y)\leq10^{15}$$$) — the bronze coin costs for travelling between different locations.
For any pair of pairs $$$(x,y)$$$ and $$$(x',y')$$$ ($$$x \lt y$$$; $$$x' \lt y'$$$; $$$(x,y)\neq(x',y')$$$), if $$$f(x,y)\leq f(x',y')$$$ holds, then $$$2f(x,y)\leq f(x',y')$$$ also holds.
For any pair of pairs $$$(x,y)$$$ and $$$(x',y')$$$ ($$$x \lt y$$$; $$$x' \lt y'$$$; $$$(x,y)\neq(x',y')$$$), if $$$\lfloor\frac{x}{N_1}\rfloor=\lfloor\frac{y}{N_1}\rfloor=\lfloor\frac{x'}{N_1}\rfloor=\lfloor\frac{y'}{N_1}\rfloor$$$ holds and $$$g(x,y)\leq g(x',y')$$$ holds, then $$$2g(x,y)\leq g(x',y')$$$ also holds.
For any pair of pairs $$$(x,y)$$$ and $$$(x',y')$$$ ($$$x \lt y$$$; $$$x' \lt y'$$$; $$$(x,y)\neq(x',y')$$$), if $$$\lfloor\frac{x}{N_2}\rfloor=\lfloor\frac{y}{N_2}\rfloor=\lfloor\frac{x'}{N_2}\rfloor=\lfloor\frac{y'}{N_2}\rfloor$$$ holds and $$$h(x,y)\leq h(x',y')$$$ holds, then $$$2h(x,y)\leq h(x',y')$$$ also holds.
A single line containing three integers representing the lexicographically minimum array of the number of gold, silver, and bronze coins for the entire journey.
2 3 231 6 9 7 93 3 2 89 8 92 944 1 2 1 3 4 2 2 3 4 24 1 1 4 2 3 1 3 2 42 3 4 1 3 3 1 4 23 4 2 2 4 2 3 21 2 2 4 2 3 33 3 2 4 1 24 2 2 3 11 3 2 21 3 12 43
3 16 21
One possible optimal journey is as follows:
- Start at location $$$10$$$.
- Go to location $$$11$$$. Pay $$$3$$$ bronze coins.
- Go to location $$$8$$$. Pay $$$4$$$ silver coins and $$$1$$$ bronze coin.
- Go to location $$$9$$$. Pay $$$1$$$ bronze coin.
- Go to location $$$8$$$. Pay $$$1$$$ bronze coin.
- Go to location $$$7$$$. Pay $$$2$$$ silver coins and $$$1$$$ bronze coin.
- Go to location $$$6$$$. Pay $$$4$$$ bronze coins.
- Go to location $$$2$$$. Pay $$$3$$$ gold coins, $$$3$$$ silver coins, and $$$1$$$ bronze coin.
- Go to location $$$3$$$. Pay $$$2$$$ bronze coins.
- Go to location $$$1$$$. Pay $$$1$$$ silver coin and $$$1$$$ bronze coin.
- Go to location $$$0$$$. Pay $$$4$$$ bronze coins.
- Go to location $$$4$$$. Pay $$$6$$$ silver coins and $$$1$$$ bronze coin.
- Go to location $$$5$$$. Pay $$$1$$$ bronze coin.
Total gold coins is $$$3$$$. Total silver coins is $$$4+2+3+1+6=16$$$. Total bronze coins is $$$3+1+1+1+1+4+1+2+1+4+1+1=21$$$.
Kantipa has a string $$$S$$$ of $$$N$$$ uppercase English letters. Kantipa wants to write down a new string $$$T$$$. To do so, she first initializes $$$T$$$ as an empty string. Kantipa keeps track of a pointer on $$$S$$$ that's initially on the leftmost character. Each iteration, she does the following steps:
- Append a new character to the end of $$$T$$$ that's the character at the pointer in $$$S$$$.
- If the pointer is at the rightmost character of $$$S$$$, end the process.
- Else, there's a $$$50\%$$$ chance that the pointer moves to the next character to the right in $$$S$$$, or there's a $$$50\%$$$ chance that the pointer moves back to the leftmost character in $$$S$$$.
Once the process ends, Kantipa counts the number of times $$$S$$$ appears as a substring of $$$T$$$. What's the expected value of this count?
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 1\,000\,000$$$) — the length of $$$S$$$.
The second line contains a string $$$S$$$ of length $$$N$$$ consisting of uppercase English letters.
It can be proven that the expected value can be expressed as a simplified fraction $$$\frac{p}{q}$$$ where $$$q$$$ is coprime with $$$998\,244\,353$$$. Print a single integer $$$Z$$$ ($$$0\leq Z \lt 998\,244\,353$$$) such that $$$Z \times q \equiv p \pmod {998\,244\,353}$$$.
10YNOALGOGET
1
9GANGAGANG
935854087
In the first example, one possible string $$$T$$$ that can be generated is $$$\texttt{YNYYNYNOYNYNOALYNYNOALGOGET}$$$. However, no matter what happens, the number of times $$$\texttt{YNOALGOGET}$$$ appears as a substring is always $$$1$$$.
In the second example, the answer is $$$\frac{97}{16}$$$.