Sophie is trying to determine when the new moon is so that she can figure out the exact date of Lunar New Year. She looks at the moon and determines how much is lit up, but she doesn't know what state this corresponds to. Can you help her?
She has written down the shape of the lit portion of the moon as follows:
- If none of the moon is lit up, she writes down "0".
- If all of the moon is lit up, she writes down "100".
- Otherwise, she writes down the integer percentage of the moon that is lit up, along with 'L' if the left side of the moon is lit or 'R' if the right side of the moon is lit. For example, if 37% of the right side of the moon is lit, then she writes down "37R".
The possible lunar phases, in order, are:
- New moon – the moon is unlit
- Waxing crescent – the lit portion of the moon is growing in size, but it is less than half of the moon
- First quarter – the lit portion of the moon is growing in size, and it is exactly half of the moon
- Waxing gibbous – the lit portion of the moon is growing in size, and it is greater than half of the moon
- Full moon – the moon is fully lit
- Waning gibbous – the lit portion of the moon is shrinking in size, and it is greater than half of the moon
- Third quarter – the lit portion of the moon is shrinking in size, and it is exactly half of the moon
- Waning crescent – the lit portion of the moon is shrinking in size, but it is less than half of the moon
She lives in Austin, TX (in the Northern hemisphere), so the light moves from right to left on the moon. For some images, please view Wikipedia.
The first line contains the description of the Moon. If the moon is completely dim, it contains "0" without quotes. If the moon is completely lit, it contains "100", completely lit. Otherwise, it contains some integer $$$p$$$ following directly by a character $$$s$$$ ($$$1 \leq p \leq 99$$$, $$$s \in \{\mathtt{'L', 'R'}\}$$$) — the portion of the moon lit up and the side of the moon that is lit up, respectively. $$$p$$$ and $$$s$$$ are not separated by a space.
Output the string corresponding to the lunar phase of the moon according to the table above.
0
New moon
100
Full moon
37R
Waxing crescent
Bob loves snakes! In fact, he was delighted to learn that 2025 is the Year of the Snake! The Lunar Calendar follows a 12 year cycle with one of twelve animals representing each year. 2001, 2013, and now, 2025, are Years of the Snake. The next Year of the Snake will be 2037. Bob has a set of numbers, and would like to rearrange them into a Year of the Snake. Help Bob count how many different Years of the Snake he can form by rearranging his set of numbers. Leading zeroes are not allowed.
The first line contains the integer $$$n$$$ $$$(1 \leq n \leq 6)$$$ — the size of Bob's set of numbers.
The next line will contain $$$n$$$ space separated digits $$$d_i$$$. $$$(0 \leq d_i \leq 9)$$$
Output a single integer, the number of different Years of the Snake that Bob can form by rearranging his set of integers.
23 3
1
42 0 2 5
2
31 2 3
2
In the first test case, the only Year of the Snake that can be formed is 33. In the second test case, 2025 and 2205 are both valid Years of the Snake.
For the Lunar New Year festival this year, James was put in charge of coordinating the dragon dancers. He organized his team of $$$n$$$ dancers in a line such that position 1 is the front of the line. While he trained them all well, he forgot to consider one factor: their heights. When controlling the dragon puppet, it looks quite unnatural if two consecutive people in the line have their heights differ by too much. Additionally, they have been training in their current line order for so long that no dancer can dance directly behind a new person; they must either dance behind the same person or be the front of the line. James wants to pick some dancers from this line to perform in the dance tonight. Help him figure out the length of the longest possible line he can form for tonight's dragon dance!
The first line of input contains two integers $$$n$$$ ($$$1\leq n \leq 2\cdot10^5$$$) and $$$k$$$ ($$$1\leq k \leq 10^9$$$) — the number of dancers and the maximum absolute height difference allowed.
The second line contains $$$n$$$ integers $$$h_1,h_2,\dots,h_n$$$ ($$$1\leq h_i\leq 10^9$$$) — the heights of each of the dancers in the line in order.
The output should consist of a single integer indicating the length of the longest possible line James can form to ensure the dragon dance looks natural.
7 41 2 1 2 6 7 1
6
6 37 4 7 4 8 9
4
In the first sample, James picks the first 6 dancers since the gap between 7 and 1 is too large to be included in the line.
It's Lunar New Year, and $$$n$$$ ($$$1 \leq n \leq 100$$$) lion dancers are performing a traditional lion dance through a grid-like corridor. The corridor is divided into $$$m$$$ ($$$1 \leq m \leq 10^5$$$) sections, arranged as columns of platforms. Each section $$$i$$$ consists of $$$k_i$$$ platforms ($$$n \leq k_i \leq 10^5$$$) stacked vertically in a grid-like structure. Each platform can hold exactly one dancer, and no two dancers can share the same platform at any time.
The dancers start their performance in the first column and must move through the grid from left to right. At each step, all $$$n$$$ dancers move as a team to the next column, each landing on one of the available platforms in the new section. This process continues until they reach the final column.
Additionally, the lion dancers are numbered from $$$1$$$ to $$$n$$$, with dancer $$$1$$$ always performing on the lowest platform and dancer $$$n$$$ on the highest platform in any column. This order must be maintained throughout the performance: if dancer A is below dancer B in one column, then dancer A must be below dancer B in every other column.
Your task is to determine the number of distinct ways the lion dancers can perform their routine, moving from the first column to the last. Two routines are considered distinct if, at any step, at least one dancer occupies a different platform compared to the other routine. Please output the answer mod $$$10^9+7$$$.
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 100, 1 \leq m \leq 10^5$$$) — the number of lion dancers and corridor sections respectively.
The second line contains $$$m$$$ integers, $$$k_1, k_2, … k_{m}$$$ ($$$n \leq k_i \leq 10^5$$$) — denoting the number of platforms in each column.
Output a single integer — the number of distinct ways the lion dancers can complete their performance mod $$$10^9+7$$$
2 32 3 2
3
1 53 2 1 4 2
48
10 819 12 10 11 16 19 12 13
823844000
Horse is sitting on the Earth staring in the sky at the moon. However, he doesn't have great vision, so he needs your help to figure out the lunar phase! He is quite perceptive though and knows the location of the moon as well as where the sun's rays are coming from. More specifically, the Earth is located at the origin $$$(0, 0)$$$, and the sun's rays are parallel to the vector $$$(s_x, s_y)$$$. Furthermore, the moon is located at $$$(m_x, m_y)$$$. The sun illuminates half of the moon, and a (potentially different) half of the moon is visible from the Earth. There are four events that Horse really cares about: the new moon, first quarter, full moon, and third quarter. Horse wants to know what is the next event that will occur. Horse has a lot of questions, so please answer them all.
Note that the moon moves counterclockwise around the origin. For more info on the moon phases, please check Wikipedia.
The first line contains a single number $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — the number of queries.
The following $$$q$$$ lines contain 4 integers $$$s_x, s_y, m_x, m_y$$$ ($$$-10^5 \leq s_x, s_y, m_x, m_y \leq 10^5$$$) — where $$$(s_x, s_y)$$$ is the vector the sun's rays are parallel to, and $$$(m_x, m_y)$$$ is the point the moon is located at.
It is guaranteed that $$$(m_x, m_y)$$$ is not the origin and that $$$(s_x, s_y) \neq (0, 0)$$$. Furthermore, the moon's state is more than $$$\frac{1}{360}$$$th of the lunar cycle away from an event.
41 1 1 01 1 0 -11 1 -1 01 1 0 1
Full moon First quarter New moon Third quarter
Xinyu the dragon is excited to attend the Lunar New Year festival to welcome in the new year!
At the festival there are $$$n$$$ lanterns lined up in a row, with the $$$i$$$th lantern being at height $$$a_i$$$. Xinyu the dragon loves hopping around on the lanterns, but he can only hop to adjacent lanterns that are the same height as the lantern he is currently on.
Fortunately, his powers of firebreathing give him the ability to do the following any number of times as he hops about:
- If his energy is above 0, consume 1 unit of energy to breathe fire into the lantern he is currently on, raising the lantern's height by 1.
- Absorb some fire from the lantern he is currently on, gaining 1 unit of energy and lowering the lantern's height by 1.
Xinyu's goal is to pick some lantern to start on and then hop around to visit all of the lanterns. He is curious about how much energy he needs to do so, so he will ask you questions over time of the form $$$1\ p$$$, meaning he wants to know if he starts at lantern $$$p$$$, what is the minimum energy he needs to start with to be able to visit all the lanterns.
Additionally, as the festival progresses, the heights of individual lanterns may fluctuate, and these events will be presented in the form $$$2\ p\ x$$$, meaning that lantern $$$p$$$ now has a new height of $$$x$$$.
Please process each event and help answer Xinyu's questions as the festival progresses!
The first line of input contains two integers $$$n$$$ and $$$q$$$ $$$(1\leq n, q\leq 2\cdot10^5)$$$ — the number of lanterns and the number of events.
The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n\ (0\leq a_i\leq 10^9)$$$ — the starting heights of each lantern in the row.
Each of the following $$$q$$$ lines will describe an event in one of the following formats:
- $$$1\ p\ (1\leq p\leq n)$$$
- $$$2\ p\ x\ (1\leq p\leq n,\ 0\leq x\leq 10^9)$$$
There is guaranteed to be at least one event of the first type.
For each question that Xinyu asks, please print the answer on its own line.
3 23 1 31 11 2
0 2
2 51000000000 01 22 2 101 22 1 101 2
1000000000 999999990 0
In the first test case, if Xinyu starts on lantern 1 with 0 energy, he can absorb fire 2 times to decrease the lantern's height by 2 and increase his energy by 2, then hop to lantern 2, spend 2 energy to raise its height from 1 to 3, then hop to lantern 3.
If he starts on lantern 2 with 2 energy, he can spend 2 energy to raise its height from 1 to 3, then hop freely to lanterns 1 and 3.
Chen lives in a 2D world. To celebrate the end of the Year of the Dragon, $$$n$$$ dragons are flying around in the sky.
We can think of this world as an $$$m$$$ wide grid, labeled horizontally from $$$1$$$ to $$$m$$$ and vertically from $$$0$$$ to $$$\infty$$$. Chen can only move horizontally along the line $$$y=0$$$. All dragons can be treated as perfectly horizontal height 1 rectangles, and they all fly above Chen.
The $$$i$$$th dragon spans horizontally from location $$$l_i$$$ to $$$r_i$$$, inclusive. Furthermore, each dragon is associated with an power value $$$p_i$$$. Let the locations that each dragon takes up be 1-indexed from left to right. Dragons get scalier as they grow, so $$$j$$$th index of the $$$i$$$th dragon has $$$p_i \cdot j$$$ scales on it.
For each position $$$i$$$, or coordinate $$$(i,0)$$$, that Chen can stand on, she wants to know how many scales would directly be above her.
The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$) - the number of dragon's and the total width of the grid.
Each of the following $$$n$$$ lines will contain 3 integers $$$l_i, r_i, p_i$$$ ($$$1 \leq l_i \leq r_i \leq m, 1 \leq p_i \leq 2 \cdot 10^6$$$) — denoting that the $$$i$$$th dragon stretches from index $$$l_i$$$ to $$$r_i$$$ and has power $$$p_i$$$.
Output $$$m$$$ space-separated integers, with the $$$i$$$th integer representing the number of scales above Chen if she is standing at position $$$i$$$.
2 41 3 14 4 5
1 2 3 5
2 61 6 13 4 4
1 2 7 12 5 6
In the first test case, the first dragon contributes 1 scale to position 1, 2 scales to position 2, 3 scales to position 3, and 0 scales to position 4. The second dragon contributes 5 scales to position 4
This is the easy version of the problem. The difference between the versions is that in this version $$$q = 0$$$.
Sally the Snake has found herself in a field of grass and rocks. The field can be represented as a grid with $$$n$$$ rows and $$$m$$$ columns. Every cell in the grid is either '*' (grass) or '@' (rock).
Sally is a fast snake. Interestingly, she moves at a speed $$$k_v$$$ when moving up or down, while she moves at a speed of $$$k_h$$$ when moving left or right.
Sally is a peculiar snake, and every movement she takes must consist of the following steps:
- Sally will choose an orthogonal direction (up, down, left, or right). If she decides to move up or down, she will move $$$k_v$$$ cells in that direction. Otherwise she will move $$$k_h$$$ cells in her desired direction. She can only do this if all the k cells in the path contain grass.
- She will then choose a new direction (her direction can stay the same), and repeat the process from the previous step. Again, the k cells in her path must contain grass. Note that there are exactly two steps in each movement.
Sally is a curious snake. She wants to know how many pairs of grass cells $$$a$$$ and $$$b$$$ there are such that $$$a \neq b$$$ and she can reach cell $$$b$$$ after some number of complete movements from cell $$$a$$$. She calls this quantity the openness of the field.
Sally is a stupid snake. She needs you to find this value for her!
Lastly, Sally is in danger for the next $$$q$$$ minutes. Each minute from $$$1$$$ to $$$q$$$, a rock will fall from the sky and land in some cell of the grid (that contained grass). The cell that the rock falls on will no longer have grass and should be considered a rock cell.
Please help Sally by finding the openness of the field before any rocks fall, as well as after each rock falls onto the grid.
The first line of input will contain four integers $$$n$$$, $$$m$$$, $$$k_v$$$, and $$$k_h$$$ ($$$2 \leq n, m \leq 10^5$$$, $$$n \cdot m \leq 2 \cdot 10^5$$$, $$$1 \leq k_v \lt n$$$, $$$1 \leq k_h \lt m$$$) — denoting the number of rows in the grid, number of columns in the grid, Sally's vertical speed, and Sally's horizontal speed, respectively.
The $$$i$$$th of the next $$$n$$$ lines contains a string of length $$$m$$$, consisting only of characters '*' and '@' — describing the $$$i$$$th row of the grid, where '*' denotes a grass cell and '@' denotes a rock cell.
The next line contains a single integer $$$q$$$ (In this version $$$q = 0$$$) — denoting the number of minutes for which rocks will fall from the sky.
The $$$j$$$th of the next $$$q$$$ lines contains two integers $$$r_j$$$ and $$$c_j$$$ ($$$1 \leq r_j \leq n$$$, $$$1 \leq c_j \leq m$$$) — denoting the row and column of which the $$$j$$$th rock will fall. It is guaranteed that the cell at row $$$r_j$$$ and column $$$c_j$$$ will be grass before the $$$j$$$th rock falls.
Output $$$q + 1$$$ space separated integers, where the $$$j$$$th integer denotes the openness of the field after the first $$$j - 1$$$ rocks have fallen onto the field.
2 2 1 1**@*0
2
3 7 1 2@@@@***@*********@@@@0
26