Alice has just received $$$a$$$ peony seeds and $$$b$$$ sunflower seeds from Bob! She also has an infinitely large space to plant her flowers, but unfortunately they require more water than she can afford. Each day, Alice can afford $$$c$$$ units of water. Every peony seed that she plants requires $$$x$$$ units of water per day, and every sunflower seed requires $$$y$$$ units of water per day. Alice wants to know that maximum number of flowers that she can plant while using at most $$$c$$$ units of water per day. Please help Alice by finding this value!
The first line of input will contain five integers $$$a$$$, $$$b$$$, $$$c$$$, $$$x$$$, $$$y$$$ ($$$1 \leq a, b, c, x, y \leq 100$$$) — denoting the number of peony seeds, the number of sunflower seeds, the amount of water available per day, the daily water consumption of a single peony seed, and the daily water consumption of a single sunflower seed, respectively.
Output a single integer, denoting the maximum number of flowers that Alice can plant.
2 4 3 1 2
2
3 4 3 1 2
3
7 5 50 3 11
9
In the first sample, it can be shown that Alice cannot plant more than 2 flowers. She can plant two flowers by planting one peony seed and one sunflower seed. The peony seed uses 1 unit of water per day, and the sunflower seed uses 2 units of water per day. In total, 3 units of water are used per day, which is exactly how much Alice has available.
Did you know that today, March 12th, is National Plant a Flower Day?
Lale, a dedicated gardener, just found out and is now ready to plant exactly one flower — after all, it's not "Plant Many Flowers Day!" Her newest garden, a rectangular field, is guaranteed to have space to plant. Additionally, she wants to find the perfect spot to plant the flower and make her garden look its best. Specifically, she's aiming to capture the most powerful photo of her garden.
Lale photographs her garden by either choosing $$$x$$$ consecutive rows or $$$x$$$ consecutive columns. The "power" of this photo will then be $$$x$$$ (i.e. the number of rows or columns selected). However, if the photo contains at least one cell without a flower (i.e. a $$$0$$$ in the sub-grid), the power is automatically reduced to $$$0$$$.
Given a description of her garden, help Lale figure out the most powerful photo she can take if she can plant another flower!
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m$$$ and $$$n \cdot m \leq 10^5$$$)
The next $$$n$$$ lines contain $$$m$$$ integers, where each integer is either $$$0$$$ (an empty cell) or $$$1$$$ (a flower). It is guaranteed at least one empty cell is in the garden.
Output a single integer — the power of the most powerful photo full of flowers Lale can take after planting exactly one flower.
3 30 1 11 1 10 0 0
2
3 40 1 1 10 1 0 01 1 1 0
2
2 20 00 0
0
In the first sample, Lale can plant a flower in the top left, allowing her to take a picture of the first two rows full of flowers.
In the second sample, Lale can plant a flower in the 2nd row and 3rd column, allowing her to take a picture of the middle two columns.
In the third sample, no matter where she plants a flower, Lale cannot guarantee at least one row or column full of flowers.
Kush is at the annual Stardew Valley Flower Dance! As part of the festival, he will perform a dance in which he will jump around on a circular arrangement of $$$n$$$ tiles for $$$m$$$ moves.
Each tile is denoted by a unique identifier $$$i$$$ $$$(2 \leq i \leq n)$$$. On every move, Kush can move to his immediate left and right. Note that because the tile arrangement is circular, the jumps can wrap around (for example, Kush can jump from tile $$$n$$$ to tile 1 and vice versa). Kush is also required to jump on every move, i.e. he cannot stay in the same spot. Kush is also allowed to choose the tile he starts on.
The tile that Kush is on after each move is actually very important. Each tile $$$i$$$ has an associated point value $$$p_{i,j}$$$ for move $$$j$$$ $$$(1 \leq j \leq m)$$$. If Kush is on tile $$$i$$$ after move $$$j$$$, $$$p_{i,j}$$$ points are added to his score ($$$p_{i,j}$$$ can be negative, in which case his score goes down). Kush wants to maximize his score by the end of the dance in order to impress Mayor Lewis!
Help Kush maximize his score.
Note: Since input size may be large, please use fast I/O methods (for example, use BufferedReader instead of Scanner for Java).
The first line contains $$$n,m$$$ $$$(2 \leq n \leq 10^3, 1 \leq m \leq 10^3)$$$ — the number of tiles and the number of moves.
The next $$$n$$$ lines contain $$$m$$$ numbers, where the $$$j^\text{th}$$$ number in the $$$i^\text{th}$$$ column is $$$p_{i,j}$$$ $$$(-10^9 \leq p_{i,j} \leq 10^9)$$$.
Output a single number, the maximum score Kush can achieve.
4 41 2 2 25 5 4 05 1 5 23 0 4 3
18
3 62 0 4 -2 2 -1-2 0 0 5 8 03 7 -2 6 5 3
30
In the first test case, a sequence of tiles Kush can follow to maximize his score is:
$$$3 \rightarrow 2 \rightarrow 3 \rightarrow 4$$$
In this case, Kush's score is $$$18$$$ $$$(5 + 5 + 5 + 3)$$$. It can be shown that there is no sequence of jumps for which Kush's score is greater than $$$18$$$.
While staring at the night sky, Johnny began looking for collections of stars in the sky that have a flower-like appearance. In particular, a group of at least three stars in the sky is called a florescent constellation if there exists a circle such that the following two conditions hold:
- All stars in the constellation lie on the edge of the circle.
- The stars in the constellation are equally spaced around the circle.
Since Johnny wants to find all florescent constellations in the night sky, help him to identify the number of such constellations, so he knows when to stop looking! Two constellations are considered distinct if they differ by at least one star.
The night sky can be modeled as a set of $$$n$$$ stars in a 2D plane numbered from $$$1$$$ to $$$n$$$, with the $$$i$$$-th star located at the integer coordinates $$$(x_i, y_i)$$$. No two stars are located in the same position.
The first line contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of stars in the night sky.
The next $$$n$$$ lines each contain two integers, with the $$$i$$$-th line containing $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — the coordinates of the $$$i$$$-th star in the night sky.
Output a single integer, the number of florescent constellations in the night sky.
50 00 11 02 11 2
1
In the first test case, there is one florescent constellation. In particular, stars $$$2$$$, $$$3$$$, $$$4$$$, and $$$5$$$ form a florescent constellation, as they all lie on a single circle and are equally spaced around that circle.
Many people know Walrus for a lot of things, for grinding math tests to singing Twice lyrics in his room. Speaking of Twice, he decided one day to plant a field of wallflowers in honor of the group. The field consists of an $$$n$$$ by $$$n$$$ grid. With so many flowers, Walrus needs to make sure he has the proper energy for watering them every day in the evening. The energy to water the entire grid is defined below.
- Two cells are part of the same "budding" if both contain flowers, and the cells are adjacent or connected underground.
- The amount of energy for watering a budding is defined as $$$\max(f - \sqrt{c}, 0)$$$, where $$$f$$$ is the number of cells with flowers, and $$$c$$$ is the number of underground connections that have at least one endpoint (flower cell) in the budding.
- The energy to water the entire grid is the sum of the energies to water each budding.
After each day, help Walrus figure out how much energy he needs to use up!
The first line will contain $$$n$$$ and $$$d$$$ ($$$2 \le n \le 100$$$ and $$$1 \le d \le 1000$$$): the size of the grid, and the number of days.
The next $$$n$$$ lines will contain binary strings of length $$$n$$$, where each character $$$s_i \in \{0, 1\}$$$ either means the cell is dirt ($$$0$$$) or has flowers ($$$1$$$).
The next $$$d$$$ lines will contain a query in the following format:
- $$$1$$$ $$$x$$$ $$$y$$$ ($$$0 \le x,y \lt n$$$): Karp puts flowers at cell $$$(x, y)$$$ (row $$$x$$$, column $$$y$$$).
- $$$2$$$ $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ ($$$0 \le x_1, y_1, x_2, y_2 \lt n$$$, $$$x_1 \ne x_2$$$ or $$$y_1 \ne y_2$$$): Karp connects cells $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ underground.
For each of the $$$d$$$ queries, print out the amount of energy required. An absolute or relative error of at most $$$10^{-6}$$$ will be permitted.
3 41011000011 2 02 0 0 0 12 0 2 2 21 0 1
5.00000000 4.00000000 3.00000000 4.58578644
4 510111001001010111 0 02 0 0 0 11 1 12 1 1 2 22 3 3 3 1
9.00000000 8.00000000 9.00000000 8.58578644 8.26794919
The below steps describe the first sample.
On the first day, Karp plants flowers at $$$(3, 1)$$$. The energy of the three buddings are $$$3$$$, $$$1$$$, and $$$1$$$.
On the second day, Karp connects $$$(1, 1)$$$ with $$$(1, 2)$$$. The energy of the three buddings are $$$3 - \sqrt{1}$$$, $$$1$$$, and $$$1$$$.
On the third day, Karp connects $$$(1, 3)$$$ with $$$(3, 3)$$$. The energy of the two buddings are $$$3 - \sqrt{1}$$$ and $$$2 - \sqrt{1}$$$.
On the fourth day, Karp plants flowers at $$$(1, 2$$$). The energy of the only budding is $$$6 - \sqrt{2}$$$.
Bart the Bee loves the nectar from a specific flowerpot, but he does not remember the way from the hive to the flowerpot. So, he has created a master map. This map consists of $$$n$$$ instructions that, when followed in order, will take Bart to his favorite flowerpot. Each instruction can be in one of 2 types:
1. Turn $$$x$$$ degrees counterclockwise.
2. Go $$$y$$$ units forward.
We can model the landscape as a 2D coordinate system with the positive x-axis representing east and the positive y-axis representing north. The hive is located at the origin, $$$(0,0)$$$, and when Bart follows the map, he always starts at the hive facing due north.
To keep his master map safe, Bart has also created $$$q$$$ exact copies of the master map. However, Harry the Hornet broke into the nest, stole the master map, and tried to burn the map copies. Fortunately, only the edges of the map copies were burned, leaving the centers intact. Specifically, for each $$$i$$$ $$$(1\leq i\leq q)$$$, the $$$i$$$th map now only has the instructions from $$$l_i$$$ to $$$r_i$$$, inclusive $$$(1\leq l\leq r\leq n)$$$.
Without the master map, Bart still wants to use the burned maps to reach his favorite flowerpot. So, for each burned map, output the Euclidean distance from Bart's position after following the burned map to the position of his favorite flowerpot (with a maximum relative or absolute error of $$$10^{-4}$$$).
Note that when Bart follows a burned map, he follows it as if it were a normal map, starting from the hive facing due north.
Note: If using Java, consider using BufferedReader + PrintWriter (i.e. Fast I/O methods) to solve.
The first line contains $$$n$$$ and $$$q$$$ $$$(1\leq n,q\leq 2\cdot10^5)$$$ — the number of instructions in the map, and the number of map copies.
The next $$$n$$$ lines start with an integer $$$k_i$$$ $$$(k_i\in[1,2])$$$ — the type of the $$$i$$$th instruction.
If $$$k_i=1$$$, the next integer on the same line will be an integer $$$x_i$$$ $$$(1\leq x_i\leq360)$$$ — the number of degrees to rotate counterclockwise.
If $$$k_i=2$$$, the next integer on the same line will be an integer $$$y_i$$$ $$$(1\leq y_i\leq10^6)$$$ — the number of units to walk forward.
The next $$$q$$$ lines contain 2 integers, $$$l_i$$$ and $$$r_i$$$ $$$(1\leq l\leq r\leq n)$$$ — the left and right endpoints of the unburned section of the $$$i$$$th map.
For each of the $$$q$$$ map copies, print out the Euclidean distance from Bart's position after following the burned map to the position of his favorite flowerpot (with a maximum relative or absolute error of $$$10^{-4}$$$).
6 52 21 902 11 2702 32 11 63 64 44 62 5
0.0000000000 7.0710678119 6.0827625303 7.8102496759 3.0000000000
The above diagram shows Bart's master map. A red arrow indicates a forward move and a black arrow indicates a rotation. He goes 2 units forward from $$$(0,0)$$$ to $$$(0,2)$$$, turns left, goes 1 unit forward to $$$(-1,2)$$$, turns right, goes 3 units forward to $$$(-1,5)$$$, then goes 1 unit forward to $$$(-1,6)$$$, the position of Bart's favorite flowerpot.
The above diagram shows the 2nd map copy. Here, Bart only follows instructions 3 through 6, inclusive. Now, his movements are represented through blue forward moves and black rotations. He moves 1 unit forward from $$$(0,0)$$$ to $$$(0,1)$$$, turns right, moves 3 units forward to $$$(3,1)$$$, then moves 1 unit forward to $$$(4,1)$$$.
Bart ends up at $$$(4,1)$$$, but the flowerpot is at $$$(-1,6)$$$. This means that Bart is $$$5\sqrt{2}\approx 7.0710678119$$$ units away from the flowerpot. (This distance is denoted in orange)
Edwardo the florist is cutting paper flowers.
Each paper flower is created by cutting a circular piece of paper with $$$n$$$ digits written on the outside edge where each digit is a number from $$$1$$$ to $$$9$$$. Since the paper is circular, the $$$n$$$th digit is adjacent to the first. The paper will be cut into $$$m$$$ petals, where each of the original numbers is located in exactly one petal, and each petal is represented by a contiguous region of the paper. However, Edwardo likes symmetrical flowers, so all petals have to have the same number of digits on them.
For example, if the $$$n$$$ digits are $$$1 2 3 4 5 6$$$, Edwardo could cut this up into $$$3$$$ petals with values $$$2 3 4$$$, $$$5 6$$$, and $$$1$$$, as shown in the following image:
The ugliness of the flower is equal to the sum of the numbers written on each petal. The ugliness of the example cut is $$$234 + 56 + 1 = 291$$$. Edwardo wants to minimize the ugliness of his flower, so he asks you to find the minimum possible ugliness of his flower after cutting it into $$$m$$$ petals.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^6$$$, $$$1 \leq m \leq n$$$) — denoting the number of digits on the circular paper, and the number of petals in the resulting flower respectively. It is also guaranteed that $$$\frac{n}{m}$$$ is an integer, and that $$$\frac{n}{m} \leq 10^3$$$.
The second line contains $$$n$$$ space-separated integers $$$d_1, d_2, ..., d_n$$$ ($$$1 \leq d_i \leq 9$$$) — where $$$d_i$$$ denotes the $$$i$$$th digit on the circular paper.
Output a single integer, representing the minimum possible ugliness of a flower that Edwardo can create out of $$$m$$$ petals. Note that the answer may not fit in a 64-bit (or even 128-bit) integer.
6 21 2 3 4 5 6
579
6 23 9 6 3 9 1
778
In the first test case, the optimal cutting is to split $$$123456$$$ into $$$123 + 456$$$.
In the second test case, the optimal cutting is $$$139 + 639 = 778$$$.
Everyone knows that the dandelion is the undisputed champion of the flower world. Not only is it edible by humans (and nutritious!), but it forms a puffy seedhead that is fun to blow. Often, it takes several blows to make all the seeds fall off. Given the proportion of seeds that remains after the $$$i^{\text{th}}$$$ blow as a fraction $$$\frac{a_i}{b_i} \lt 1$$$, where the number of remaining seeds is rounded down, find the minimum number of blows required to blow varying amounts of seeds into the wind.
More formally, given two sequences of numbers $$$a_1, a_2, ..., a_n$$$, and $$$b_1, b_2, ..., b_n$$$ and $$$q$$$ queries giving an initial number of seeds $$$m \gt 0$$$, find $$$k$$$ such that the sequence $$$c_0, c_1, ..., c_k$$$ where $$$c_0 = m$$$ and $$$c_i = \lfloor c_{i-1} \cdot \frac{a_i}{b_i}\rfloor$$$ satisfies $$$c_{k-1} \gt 0$$$ and $$$c_k = 0$$$. If more than $$$n$$$ blows are required to make all the seeds fall off, output $$$-1$$$.
The first line of input contains $$$n$$$ ($$$1 \le n \le 10^3$$$), the number of blows for which the proportion of seeds that remain is known.
The second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \le a_i \lt 10^9$$$), the numerators of the proportion of seeds that remain after each blow.
The third line contains $$$n$$$ integers $$$b_1, b_2, ..., b_n$$$ ($$$a_i \lt b_i \le 10^9$$$), the denominators of the proportion of seeds that remain after each blow.
The fourth line contains $$$q$$$ ($$$1 \le q \le 10^6$$$), the number of queries.
The fifth line contains $$$q$$$ integers $$$m_1, m_2, ..., m_q$$$ ($$$1 \le m_i \le 10^{18}$$$), the initial seed count for each query.
The output should be $$$q$$$ integers, each on a separate line, the minimum number of blows required to blow all seeds into the wind for each query.
31 3 52 4 631 5 10
1 3 -1
For the first query, $$$1 \rightarrow \lfloor 1 \cdot \frac{1}{2} \rfloor = 0$$$ requires one blow.
For the second, $$$5 \rightarrow \lfloor 5 \cdot \frac{1}{2} \rfloor = 2 \rightarrow \lfloor 2 \cdot \frac{3}{4} \rfloor = 1 \rightarrow \lfloor 1 \cdot \frac{5}{6} \rfloor = 0$$$ requires $$$3$$$ blows.
For the third, $$$10 \rightarrow \lfloor 10 \cdot \frac{1}{2} \rfloor = 5 \rightarrow \lfloor 5 \cdot \frac{3}{4} \rfloor = 3 \rightarrow \lfloor 3 \cdot \frac{5}{6} \rfloor = 2$$$ does not reach $$$0$$$ after $$$n$$$ blows, so the output is $$$-1$$$.
You and your Pikmin friends have to plant flowers all across the world. For today's mission, you need to plan flowers in a grid with $$$r$$$ rows and $$$c$$$ columns. At each grid location, you can either choose to plant a flower there or not. However, there are $$$k$$$ forbidden patterns that you aren't allowed to make! Each forbidden pattern has $$$r$$$ rows and $$$2$$$ columns. If this pattern exists anywhere in the $$$r \times c$$$ grid, then the entire pattern is invalid. You are curious as to how many different grids you can create that don't violate any pattern. Because this may be large, output the answer mod $$$998244353$$$.
The first line contains three space-separated integers $$$r$$$, $$$c$$$, and $$$k$$$ ($$$1 \leq r \leq 6, 2 \leq c \leq 10^{18}, 0 \leq k \leq 2^{2r}$$$) — the number of rows and columns of the grid, and the number of forbidden patterns, respectively.
Then, $$$k$$$ sets of $$$r$$$ lines follow. In each group of $$$r$$$ lines, the $$$i$$$th line consists of two characters $$$c_{i, 0}$$$ and $$$c_{i, 1}$$$ ($$$c_{i, j} \in \{\texttt{'#'}, \texttt{'.'}\}$$$). Each of these groups of lines represents a forbidden pattern. If $$$c_{i, j} = \texttt{'#'}$$$, then that grid element in the $$$i$$$th row and the $$$j$$$th column is a flower in the forbidden pattern. Otherwise, that grid element is empty.
It is guaranteed that each forbidden grid pattern is unique.
Output the number of possible grids without forbidden patterns, mod $$$998244353$$$.
2 3 1####
57
4 1000000000000000000 2###..#..##..##..
208293190
Alexa, a $$$d$$$-dimensional being, has recently gotten into gardening! To get her garden started, she has planted her first flower at the origin of a $$$d$$$-dimensional grid. Every second, the flower will grow by 1 unit along one of the coordinate axes in a direction away from the origin. Alexa is very excited for how her flower could turn out, so she wants to know: after $$$t$$$ seconds, how many different possible ways could the flower have grown? Since this number could be large, please output it modulo $$$998244353$$$.
Two ways are different if the flower ever grows in a different direction at some time step.
The first line contains two integers $$$d$$$ and $$$t$$$ ($$$1\leq d,t \leq 2\cdot10^5$$$) — the number of dimensions the flower could grow in and the number of seconds the flower grows for.
Output a single integer, the number of different ways the flower could have grown after $$$t$$$ seconds, modulo $$$998244353$$$.
2 1
4
3 3
126
12345 67890
243978398
In the first sample, the flower grows for one second, and could end up at $$$(0,1), (0,-1), (1,0),$$$ or $$$(-1,0)$$$.
In the second sample, one way the flower could grow is $$$(0,0,0)\rightarrow(0,1,0)\rightarrow(-1,1,0)\rightarrow(-1,2,0)$$$. Note that for the last second, the flower could not grow in a direction like $$$(-1,1,0)\rightarrow(-1,0,0)$$$, since that does not go away from the origin.