Explorer Little A discovered $$$N$$$ ancient supply boxes arranged in a row in the outer corridor of the Astra ruins. After being scanned by the detector, Little A learned that the $$$i$$$-th supply box contained $$$A_i$$$ points of starlight energy.
However, the energy in some of the supply boxes has become extremely weak, and they might even have been contaminated by dark matter. The portable energy absorber of Little A has a safety threshold of $$$X$$$. To ensure safety, Little A only activates those supply boxes whose energy values are strictly greater than $$$X$$$, and absorbs all the energy within them; for supply boxes with energy values less than or equal to $$$X$$$, he simply skips them.
Could you please calculate for Little A how many starlight energy points he can collect in total?
The first line contains two integers, $$$N$$$ and $$$X$$$ ($$$1 \le N \le 10^5$$$, $$$0 \le X \le 10^9$$$), representing the number of supply boxes and the safety threshold of the detector respectively.
The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ ($$$0 \le A_i \le 10^9$$$), representing the energy values in each supply box.
Output an integer to represent the total energy that Little A has collected in the end.
5 105 12 10 20 1
32
The threshold $$$X = 10$$$.
The energy levels of the supply boxes are $$$5, 12, 10, 20, 1$$$.
Only $$$12$$$ and $$$20$$$ are strictly greater than $$$10$$$. Therefore, the total energy collected is $$$12 + 20 = 32$$$.
Explorer Little A has finally arrived at the main structure of the Astra ruins—the "Gate of Astra". The heavy doors are tightly shut, and an ancient inscription consisting of uppercase English letters is carved on them.
According to the first rule of the $$$\textit{China West Normal University (CWNU) Explorer's Survival Guide}$$$: If the inscription on a door contains the contiguous substring $$$\mathtt{CWNU}$$$, then behind the door is a safe supply room; otherwise, there is a deadly dark matter trap!
Now, Little A has transcribed the inscription from the door. Since he is too nervous and his palms are sweating, please help him write a program to determine whether this door is safe or not.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.
For each test case:
There is a single line containing a string $$$S$$$ ($$$1 \le |S| \le 100$$$) consisting only of uppercase English letters, representing the inscription on the door.
For each test case:
If it is safe behind the door (i.e., the string contains the contiguous substring $$$\mathtt{CWNU})$$$, output $$$\mathtt{SAFE}$$$ on a new line.
Otherwise, output $$$\mathtt{TRAP}$$$.
4CWNUCPCHELLOCWNUASTRARUINSCWNUC
SAFESAFETRAPSAFE
In a vast strategic buffer zone, there are $$$n$$$ frontline outposts, indexed from $$$1$$$ to $$$n$$$. Due to the intensity of the battle, the headquarters commands that every single outpost must receive supplies.
As the logistics commander, you have two methods to provide supplies to the outposts:
Your goal is to formulate a plan with the minimum total cost such that all $$$n$$$ outposts are supplied.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \times 10^5$$$, $$$0 \le m \le 2 \times 10^5$$$), representing the number of outposts and the number of potential roads.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ denotes the cost of directly airdropping supplies to the $$$i$$$-th outpost.
The following $$$m$$$ lines each contain three integers $$$u, v, w$$$ ($$$1 \le u, v \le n$$$, $$$1 \le w \le 10^9$$$), representing a potential bidirectional road between outpost $$$u$$$ and outpost $$$v$$$ with a cost of $$$w$$$.
Note: The input may contain self-loops or multiple edges between the same pair of outposts.
Output a single integer representing the minimum total cost required to supply all outposts.
3 25 10 31 2 12 3 2
6
In the sample case, the optimal strategy is:
Alice is playing a card game called Bullfighting.
The game is played with a standard deck of cards, but only ranks A through 10 are kept. The point value of each card is defined as follows:
In each round, Alice is dealt $$$5$$$ cards. She must arrange these $$$5$$$ cards into two groups to determine her hand's power:
The rank of the hand is determined by the following rules:
The ranks are ordered as follows: $$$$$$ \text{No Bull} \lt \text{Bull } 1 \lt \text{Bull } 2 \lt \dots \lt \text{Bull } 9 \lt \text{Bull Bull} $$$$$$
Given 5 cards, please help Alice find the highest rank she can achieve by arranging them optimally.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$), representing the number of test cases.
Each test case consists of a single line containing $$$5$$$ integers $$$c_1, c_2, c_3, c_4, c_5$$$ ($$$1 \le c_i \le 10$$$), representing the point values of the $$$5$$$ cards Alice holds.
It is guaranteed that the cards are drawn from a single standard deck, meaning that for any rank $$$k \in [1, 10]$$$, it appears at most $$$4$$$ times in a hand.
For each test case, output the highest rank Alice can obtain in a single line. The output must be one of the following strings:
31 2 3 4 510 10 10 5 51 2 3 4 8
Bull 5Bull BullNo Bull
For the first case (1 2 3 4 5):
For the second case (10 10 10 5 5):
Explorer Little A has collected too many crystals in the Astra ruins, accidentally triggering the ancient self-destruct mechanism! The dark matter containers deep within the ruins have ruptured, and terrifying dark matter is beginning to spread outward.
The ruins can be viewed as an $$$N \times M$$$ 2D grid. The grid contains the following elements:
Every $$$1$$$ second that passes, Little A can move to one adjacent cell in the four cardinal directions (up, down, left, right); simultaneously, each dark matter source will also spread to an adjacent cell in the four directions.
Extremely dangerous: Dark matter has the characteristic of instantaneous devouring. Little A must guarantee that at the exact moment he arrives at a certain cell, the dark matter has not yet spread to that cell. In other words, the time Little A takes to reach a cell must be strictly less than the time it takes for the dark matter to reach that cell. If the dark matter and Little A arrive at a cell at the exact same time, Little A will also be devoured!
Please help Little A calculate whether he can make it out alive to the exit door $$$\mathtt{E}$$$. If so, what is the minimum time (in seconds) required.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.
For each test case: The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 1000$$$) — the number of rows and columns of the ruins grid.
The next $$$N$$$ lines each contain a string of length $$$M$$$, representing the map of the ruins. The characters in the string will only be $$$\mathtt{A}$$$, $$$\mathtt{E}$$$, $$$\mathtt{*}$$$, $$$\mathtt{\#}$$$, or $$$\mathtt{.}$$$.
It is guaranteed that the map contains exactly one $$$\mathtt{A}$$$ and exactly one $$$\mathtt{E}$$$.
It is guaranteed that the sum of $$$N \times M$$$ over all test cases does not exceed $$$2 \times 10^6$$$.
For each test case, output a single integer on a new line.
If Little A can safely reach the exit, output the minimum time (in seconds) required.
If Little A will inevitably be devoured by dark matter, or if it is impossible to reach the exit at all, output $$$\mathtt{-1}$$$.
34 5A......#....#..*.#.E4 4A..*...........E3 3A#.#.#.*E
7-1-1
In the first example:
Little A is located at the top-left corner $$$(1, 1)$$$, the exit is at the bottom-right corner $$$(4, 5)$$$, and the dark matter source is at the bottom-left corner $$$(4, 1)$$$.
Little A's optimal route is to move right first and bypass the walls in the middle to reach the exit. Although the dark matter is spreading, Little A is fast enough to safely reach the exit at the $$$7$$$-th second.
In the second example:
The grid size is $$$4 \times 4$$$. Little A starts from the top-left corner, and the dark matter spreads from the top-right corner. Since the exit is at the bottom-right corner, no matter how Little A moves, the dark matter will arrive at the inevitable path near the exit before or at the same time as him. Little A is bound to be devoured, so the output is $$$-1$$$.
In the third example:
Little A is completely sealed in the top-left corner by walls. There is absolutely no path to the exit, so the output is directly $$$-1$$$.
Deep within the ancient ruins of Astra, young explorer A discovered a core matrix severely eroded by dark matter. This matrix can be regarded as a row of $$$n$$$ energy nodes, numbered from 1 to $$$n$$$.
The defense system of the ruins is attempting to purify these nodes. Due to the damage to the system, it can only perform random purification operations. Specifically, in every second, the defense system will randomly select one interval (with equal probability) from all possible consecutive subintervals $$$[L, R]$$$ ($$$1 \le L \le R \le n$$$) and release a beam of purification light, purifying all the nodes within that interval once. There are a total of $$$\frac{n(n+1)}{2}$$$ possible choices.
Please note that it is permitted and harmless for the same node to be purified multiple times.
Little A wants to know: starting from the moment the defense system is activated, until all $$$n$$$ nodes have been purified at least once, what is the average number of seconds required?
Since the expected value might be a fraction, please output the result of this fraction modulo $$$10^9 + 7$$$. Specifically, if the simplest fraction for the expected value is $$$\frac{P}{Q}$$$, you need to output an integer $$$X$$$ such that $$$X \cdot Q \equiv P \pmod{10^9 + 7}$$$ and $$$0 \le X \lt 10^9 + 7$$$.
The input consists of only one line with a single integer $$$n$$$ ($$$1 \le n \le 100$$$), representing the number of energy nodes.
Output an integer representing the result of the expected seconds modulo $$$10^9 + 7$$$.
1
1
2
2
3
300000005
For the case where $$$n=2$$$, all possible intervals are $$$[1, 1], [2, 2], [1, 2]$$$, totaling $$$3$$$ types. Each type has a probability of $$$\frac{1}{3}$$$ of being selected.
Overall, the total expected time is $$$\frac{1}{3} \times 1 + \frac{1}{3} \times 2.5 + \frac{1}{3} \times 2.5 = 2$$$ seconds.
For the case where $$$n=3$$$, the actual expected number of seconds for purifying all nodes is $$$\frac{29}{10}$$$, which is equivalent to $$$300000005$$$ modulo $$$10^9 + 7$$$.
Explorer Little A arrived at the prayer hall of the Astra ruins. The hall was built at a high location, and Little A needed to climb an ancient stone staircase consisting of $$$N$$$ steps. The step numbers ranged from $$$1$$$ to $$$N$$$. Little A started from the ground (which could be regarded as the $$$0$$$th step).
Little A has excellent physical fitness. Each time, he can choose to jump up across either one or two steps. However, due to the passage of time, some $$$M$$$-level steps have completely broken apart. Little A must not step on these broken steps.
Could you please calculate for Little A how many different ways there are for him to safely reach the $$$N$$$th step?
The first line contains two integers, $$$N$$$ and $$$M$$$ ($$$1 \le N \le 50$$$, $$$0 \le M \le N$$$), representing the total number of steps and the number of broken steps respectively. The second line contains $$$M$$$ integers $$$b_1, b_2, \dots, b_M$$$ ($$$1 \le b_i \le N$$$), representing the numbers of the broken steps. It is guaranteed that these $$$M$$$ numbers are all distinct and are given in ascending order.
Output a single integer, representing the number of different ways to reach the $$$N$$$-th step.
4 12
1
5 0
8
3 31 2 3
0
If $$$N=4$$$ and $$$M=1$$$, the broken step is the second step.
Little A cannot step on the second level. The only legal way to proceed is: $$$0 \rightarrow 1 \rightarrow 3 \rightarrow 4$$$.
Deep within the Astra ruins, Little A has discovered the core energy sources of $$$K$$$ ancient mechas. The energy value of the $$$j$$$-th core is $$$E_j$$$. Meanwhile, there are $$$N$$$ candidate pilots in Little A's expedition team. Each pilot has the following four attributes:
Since there are only $$$K$$$ mechas, Little A must strictly select $$$K$$$ elites from the $$$N$$$ candidate pilots. The selection sorting rules are as follows:
After selecting these $$$K$$$ elites, Little A needs to pair them one-to-one with the $$$K$$$ energy cores. When a pilot with Combat Power $$$C_i$$$ is assigned an energy core with energy value $$$E_j$$$, the combat effectiveness generated is $$$C_i \times E_j$$$.
Little A can freely decide the assignment of energy cores among the $$$K$$$ selected pilots. Please calculate the maximum total combat effectiveness the entire vanguard team can generate.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases.
For each test case: The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \le K \le N \le 10^5$$$) — the number of candidate pilots and the number of mecha cores.
The next $$$N$$$ lines describe the pilots. The $$$i$$$-th line contains a string $$$Name_i$$$ ($$$1 \le |Name_i| \le 10$$$) and three integers $$$S_i, A_i, C_i$$$ ($$$1 \le S_i, A_i, C_i \le 10^5$$$). It is guaranteed that the names consist only of English letters and are pairwise distinct within the same test case.
The following line contains $$$K$$$ integers $$$E_1, E_2, \dots, E_K$$$ ($$$1 \le E_j \le 10^5$$$) — the energy values of the cores.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2 \times 10^5$$$.
For each test case, output a single integer on a new line, representing the maximum total combat effectiveness.
23 2Alice 10 20 50Bob 10 20 40Charlie 15 10 3010 204 3David 100 100 10Eve 100 100 100Frank 100 90 500Grace 90 200 10005 2 10
13005520
Deep within the ruins, you need to reconstruct a square energy matrix of size $$$n \times n$$$.
You have exactly $$$n^2$$$ energy crystals, with energy levels ranging from 1 to $$$n^2$$$. You must place all $$$n^2$$$ crystals into the matrix, such that each cell contains exactly one crystal.
To prevent dangerous resonance explosions between the crystals, an ancient rule states: The absolute difference in energy levels between any two adjacent crystals (sharing an edge, either horizontally or vertically) must be strictly greater than 1.
Formally, for any two adjacent elements $$$x$$$ and $$$y$$$ in the matrix, $$$|x - y| \gt 1$$$ must hold.
Please construct a valid placement for the matrix. If no such placement exists, output -1.
The first line contains a single integer $$$t$$$ (1 $$$\le t \le$$$ 100) — the number of test cases.
For each test case, the only line contains a single integer $$$n$$$ (1 $$$\le n \le$$$ 100) — the size of the matrix.
For each test case:
3123
1 -1 1 8 6 4 2 9 7 5 3
Figure 1: An example of 2048 game grid You are given an $$$N \times N$$$ grid. Each cell in the grid contains either a positive integer of the form $$$2^k\ (k \ge 1)$$$ or $$$0$$$ (representing an empty space).
You need to process an operation string $$$S$$$ of length $$$M$$$, consisting of characters L (Left), R (Right), U (Up), and D (Down). For each character in $$$S$$$, you must slide the numbers in the grid according to the rules of the game 2048.
The rules for sliding and merging are as follows:
Note: Unlike the original game, new tiles are not generated in empty spots after a move.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 20, 1 \le M \le 100$$$), representing the size of the grid and the length of the operation string.
The next $$$N$$$ lines each contain $$$N$$$ integers $$$A_{i,j}$$$ ($$$0 \le A_{i,j} \le 1024$$$), representing the initial state of the grid. It is guaranteed that all non-zero integers are powers of 2.
The last line contains a string $$$S$$$ of length $$$M$$$, consisting only of the characters L, R, U, and D.
Output $$$N$$$ lines, each containing $$$N$$$ integers, representing the final state of the grid after all operations.
4 42 2 2 24 2 2 00 4 2 28 0 0 8LRLU
16 0 0 0 8 0 0 0 16 0 0 0 0 0 0 0
Visual explanation of the sample case:
Let the state of the grid be denoted by matrices. The transitions are as follows:
$$$$$$ \underbrace{ \begin{pmatrix} 2 & 2 & 2 & 2 \\ 4 & 2 & 2 & 0 \\ 0 & 4 & 2 & 2 \\ 8 & 0 & 0 & 8 \end{pmatrix} }_{\text{Initial State}} \xrightarrow{(1)\ \textbf{L}} \underbrace{ \begin{pmatrix} 4 & 4 & 0 & 0 \\ 4 & 4 & 0 & 0 \\ 4 & 4 & 0 & 0 \\ 16 & 0 & 0 & 0 \end{pmatrix} }_{\text{After L}} \xrightarrow{(2)\ \textbf{R}} \underbrace{ \begin{pmatrix} 0 & 0 & 0 & 8 \\ 0 & 0 & 0 & 8 \\ 0 & 0 & 0 & 8 \\ 0 & 0 & 0 & 16 \end{pmatrix} }_{\text{After R}} $$$$$$
$$$$$$ \xrightarrow{(3)\ \textbf{L}} \underbrace{ \begin{pmatrix} 8 & 0 & 0 & 0 \\ 8 & 0 & 0 & 0 \\ 8 & 0 & 0 & 0 \\ 16 & 0 & 0 & 0 \end{pmatrix} }_{\text{After L}} \xrightarrow{(4)\ \textbf{U}} \underbrace{ \begin{pmatrix} 16 & 0 & 0 & 0 \\ 8 & 0 & 0 & 0 \\ 16 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} }_{\text{Final State}} $$$$$$
Transition Details:
In the alchemy chamber of the Astra ruins, Little A found $$$N$$$ starlight crystal stones. The energy value of the $$$i$$$-th crystal stone is $$$A_i$$$.
According to the ancient alchemy rule, only by combining a crystal with an odd energy value and a crystal with an even energy value can a perfect and stable 'Starlight Core' be synthesized.
Each crystal stone can only be fused once (meaning it is consumed once it is used).
Little A hopes to synthesize as many 'Starlight Core' as possible. Please help him calculate how many Starlight Cores can be synthesized with these $$$N$$$ gemstones?
The first line contains an integer $$$N$$$ ($$$1 \le N \le 5 \times 10^5$$$), representing the number of gemstones.
The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ ($$$1 \le A_i \le 10^9$$$), representing the energy values of each crystal stone
Output a single integer, indicating the maximum number of starlight cores that can be synthesized.
51 2 3 4 5
2
42 4 6 8
0
For example 1
If you have 5 crystals at hand, their energies are 1, 2, 3, 4, and 5.
The odd numbers are $$$1, 3, 5$$$, and the even numbers are $$$2, 4$$$.
The points $$$(1, 2)$$$ and $$$(3, 4)$$$ can be combined. The remaining 5 cannot be paired with even crystal stones. At most, 2 cores can be synthesized.
After enduring countless hardships, explorer Little A has finally stepped into the ultimate region of the Astra ruins—the Vault of Stars.
Suspended in the center of the vault are $$$S$$$ pure starlight crystals, surrounded by $$$N$$$ ancient array pillars of various shapes. To completely stabilize the energy field of the ruins, Little A must distribute all $$$S$$$ crystals into these $$$N$$$ pillars.
Every pillar has a limit to the energy it can withstand. Specifically, the $$$i$$$-th pillar can hold at most $$$L_i$$$ crystals. Of course, Little A can also choose not to place any crystals in certain pillars (i.e., the allocated amount is 0).
Little A wants to know: how many different distribution plans can successfully allocate all $$$S$$$ crystals while satisfying the capacity limits of all pillars?
Since the number of valid plans might be extremely large, you only need to output the answer modulo $$$10^9+7$$$.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases.
For each test case: The first line contains two integers $$$N$$$ and $$$S$$$ ($$$1 \le N \le 15$$$, $$$1 \le S \le 10^9$$$) — the number of pillars and the total number of starlight crystals.
The second line contains $$$N$$$ integers $$$L_1, L_2, \dots, L_N$$$ ($$$0 \le L_i \le 10^9$$$) — the maximum capacity of each pillar.
For each test case, output a single integer on a new line, representing the number of valid distribution plans modulo $$$10^9+7$$$.
32 53 33 41 2 315 10000000001 1 1 1 1 1 1 1 1 1 1 1 1 1 1
250
In the first example, there are 2 pillars and 5 crystals to distribute. Both pillars have a capacity limit of 3. There are only two valid distribution plans:
In the second example, there are 3 pillars and 4 crystals to distribute. The capacity limits are 1, 2, and 3, respectively.
There are three valid distribution plans:
Output 5.
In the third example, the 15 pillars can hold at most 1 crystal each, meaning they can hold a maximum of 15 crystals in total. It is impossible to distribute 1000000000 crystals. The number of valid plans is 0.
Deep within the ruins of Astra, explorer Little A has discovered an energy array consisting of $$$n$$$ energy crystals connected in a line. The base energy value of the $$$i$$$-th crystal is $$$a_i$$$. Due to the erosion by dark matter in the ruins, the energy values of some crystals might be negative.
Initially, the total energy of this energy array is equal to the sum of the base energy values of all the crystals.
Little A holds an ancient device called the "Resonator". He can use the Resonator to perform a soul resonance between two adjacent crystals.
When the $$$i$$$-th and $$$(i+1)$$$-th crystals resonate, they merge into an extremely unstable high-energy crystal. Their energy contribution changes from the original addition $$$(a_i + a_{i+1})$$$ to multiplication $$$(a_i \times a_{i+1})$$$.
Regarding the Resonator, there are ancient rules:
Although negative energy is dangerous, the resonance of two negative energy crystals might produce massive positive energy! Please help Little A calculate the maximum total energy the entire array can achieve after clever operations.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases.
For each test case:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 1000$$$, $$$0 \le k \le 1000$$$) — the number of crystals and the maximum number of resonance operations allowed.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^5 \le a_i \le 10^5$$$) — the base energy value of each crystal.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.
For each test case, output a single integer on a new line, representing the maximum total energy the entire array can achieve.
35 12 3 -1 -5 45 22 3 -1 -5 43 1-2 -2 -2
14152
In the first example, at most $$$1$$$ resonance can be performed.
If no resonance is used, the total energy is $$$2 + 3 + (-1) + (-5) + 4 = 3$$$.
If the $$$-1$$$ and $$$-5$$$ resonate, their merged energy becomes $$$(-1) \times (-5) = 5$$$. The array is now effectively $$$[2, 3, 5, 4]$$$, and the total energy is $$$2 + 3 + 5 + 4 = 14$$$. This is the maximum possible value.
In the second example, at most $$$2$$$ resonances can be performed.
We can let $$$2$$$ and $$$3$$$ resonate (energy becomes $$$6$$$), and at the same time let $$$-1$$$ and $$$-5$$$ resonate (energy becomes $$$5$$$).
The array is now effectively $$$[6, 5, 4]$$$, and the total energy is $$$15$$$.
In the third example, letting the first two $$$-2$$$ resonate gives $$$4$$$, plus the last $$$-2$$$, the total energy is $$$2$$$.