Lazy Bob really really really loves trucks, so he decides to start designing toys so that kids all over the world can have the joy of playing with toy trucks.
Every toy truck produced by Lazy Bob's toy factory has a positive integer length, $$$L$$$ ($$$1 ≤ L ≤ 100$$$), given in inches. Lazy Bob wants you to help him figure out, for a given toy truck, if it can fit in a toy box or not. A truck can only fit in a toy box if its length is less than or equal to $$$10$$$ inches. Please help Bob accomplish this task. If the toy truck is an appropriate size, print "YES" (without quotes), otherwise print "NO" (without quotes).
Line 1: One integer, $$$L$$$ ($$$1 ≤ L ≤ 100$$$).
Line 1: Either "YES" (without quotes), if the truck's length is ≤ $$$10$$$ inches, otherwise "NO" (without quotes).
43
NO
2
YES
For the first test case, $$$43$$$ inches is too long to fit in the box.
For the second test case, $$$2$$$ inches is a truck short enough to fit in the box.
As he often does, Lazy Bob decides that today of all days is one of the best days to take a chair to the side of the freeway and look at trucks. At one static point in time, he notices that every vehicle he can at least partially see is a truck (due to his poor depth perception, Bob merges lanes in his head into one big lane)!
Bob's view can be represented by a string $$$s$$$ of length $$$N$$$ ($$$1 ≤ N ≤ 100$$$) units, where the character 'T' represents one unit of truck, and the character '.' represents one unit of empty road.
Bob also knows that the mayor is planning to expand the freeway by adding one more lane, and he has $$$Q$$$ ($$$1 ≤ Q ≤ 100$$$) questions: if he added a truck of length $$$l_i$$$ ($$$1 ≤ l_i ≤ N$$$) units to this new lane, what is the maximum number of units of truck that he could see?
Lane 1: TT...TT.TTTT....
Lane 2: .T.T....TTT.....
Lane 3: TT.T.T.T.T.T..T.
Bob's Chair
Bob's view: TT.T.TTTTTTT..T.
1 5 2 3 8 4 7
Because Lazy Bob does not want to answer these questions himself, he asks you to do it for him. Please help Lazy Bob find the answer to each question.
Line 1: Two space-separated integers, $$$N$$$ and $$$Q$$$ ($$$1 ≤ N, Q ≤ 100$$$).
Line 2: The string $$$s$$$ of length $$$N$$$, representing Bob's view of the freeway
Line 3…$$$Q$$$-2: One integer, $$$l_i$$$ ($$$1 ≤ l_i ≤ N$$$)
Line 1…$$$Q$$$: One integer, the maximum number of units of truck Bob could see if he added a truck of length $$$l_i$$$ to the new freeway lane
8 3TT..T.T.138
5 6 8
In the first case, Bob can put the truck in the third position in the new lane, resulting in TTT.T.T., so $$$5$$$ units of truck visibility In the second case, Bob can the put the truck in the $$$3$$$rd, $$$4$$$th, and $$$5$$$th positions, resulting in TTTTT.T., so $$$6$$$ units of truck visibility In the third case, Bob can put the truck in all $$$8$$$ positions, resulting in TTTTTTTT, so $$$8$$$ units of truck visibility. It can be shown that no better answer can be obtained for any of the three cases.
While reading about tree trunks in science class, Lazy Bob accidentally read "tree trunks" as "tree trucks" (since after all, 'n' is nothing but a 90° rotated 'c' with a fancy antenna on top). And because Bob likes to think about the limits of things, he thought to himself "Tree trucks? Wow, that's cool. I wonder how tall a tree made out of a specific set of different-length-trucks could be."
Bob has a simple mind. While most trees have branches that stem off of each other in convoluted ways, Bob has always imagined a tree like the average 2nd grader: one truck at the bottom, then a triangle-ish shape of trucks above it, and one final truck at the top.
Here is a formal definition of a truck tree (see image for clarification): A vertical row of at least one truck trucks in the middle; we can imagine infinitesimally small intersection points between the trucks. Every intersection point except the top and the bottom has two equal sized trucks to the left and the right, representing the branches (red, blue, and green trucks in the picture) The order of the lengths of the trucks in the vertical row does not matter, but for the branches, longer branches have to go below shorter branches (as they do in a picture).
Given a set of $$$N$$$ ($$$1 ≤ N ≤ 200,000$$$) trucks, each with length $$$l_i$$$ ($$$1 ≤ l_i ≤ 10^9$$$), help Lazy Bob figure out the tallest valid truck tree he could make. Note that Bob does not need to use all of the trucks, but rather only a subset of his choice.
Line 1: One integer, $$$N$$$ ($$$1 ≤ N ≤ 200,000$$$). Line 2: $$$N$$$ space-separated integers $$$l_1,l_2,...,l_n$$$ ($$$1 ≤ l_i ≤ 10^9$$$).
Line 1: One integer, the height of the tallest possible valid trunk tree Bob could make out of his given set of trucks
81 1 2 2 2 3 4 5
12
Lazy Bob can use the 7 trucks (everything except for one truck with length 2):
Use trucks with length 3, 4, and 5 as the vertical ones
Use a pair of trucks with length 2 for the first (bottommost) pair of branches
Use a pair of trucks with length 1 for the second (in this case topmost) pair of branches
It can be shown that no taller valid truck tree can be made from the given set of trucks.
There are $$$N$$$ planes scheduled to arrive at the airport. Each plane arrives at its gate at time $$$a_i$$$ and departs from its gate at time $$$d_i$$$.
The airport manager is trying to cut costs, so he wants to operate as few gates as possible. For each of the $$$Q$$$ queries, he wants to know the minimum number of gates needed to avoid delay in any of the flights arriving or departing during the time interval $$$[l_j, r_j]$$$.
Instead of spending money on an airport simulator, the manager wants you to come up with an algorithm to find the minimum number of gates for each query!
Note that departing planes at $$$l_j$$$ and $$$r_j$$$ are not counted towards the total number of planes, but arriving planes at $$$l_j$$$ and $$$r_j$$$ are counted.
Line 1: Two integers, $$$N$$$ and $$$Q$$$ ($$$1 ≤ N ≤ 10^5$$$, $$$1 ≤ Q ≤ 50$$$).
Line 2: $$$N$$$ space-separated integers: $$$a_1, a_2, …, a_N$$$ ($$$1 ≤ a_i ≤ 10^9$$$), each representing the $$$i$$$th plane's arrival time.
Line 3: $$$N$$$ space-separated integers: $$$d_1, d_2, …, d_N$$$ ($$$a_i \lt d_i ≤ 10^9$$$), each representing the $$$i$$$th plane's departure time.
Lines 4…$$$Q$$$+3: Two integers, $$$l_i$$$ and $$$r_i$$$ ($$$1 ≤ l_j \lt r_j ≤ 10^9$$$), representing the starting and ending time of the $$$i$$$th query
Lines $$$1…Q$$$: One integer representing the minimum number of gates needed to avoid delay during the $$$i$$$th time interval.
5 22 7 4 5 98 11 5 8 161 108 14
3 2
For the first query, three gates are needed because the first, second, and fourth planes are at the airport when $$$t$$$=7.
For the second query, two gates are needed because the second and fifth planes are at the airport when $$$t$$$=9 and $$$t$$$=10. Note that the first and fourth planes are not included, as they leave at $$$t$$$=8.
Lazy Bob lives in Bobland, a country with $$$N$$$ ($$$2 ≤ N ≤ 100,000$$$) cities, each labeled with a number from $$$0…N-1$$$. Each city $$$x$$$ has a one way road to exactly one other city: $$$2x$$$ (mod $$$N$$$).
Lazy Bob is standing at city $$$K$$$ ($$$0 ≤ K ≤ N-1$$$). A self-driving car starts at city $$$1$$$ and keeps driving on one way roads, keeping a running sum of the labels of all the cities it goes through (including city $$$1$$$). However, because this running sum can be very big, it displays the remainder when this sum is divided by $$$N+1$$$.
Bob is curious to know if he will, at some point, see every value from $$$0$$$ to $$$N$$$ on the autonomous car's display. Help Bob by printing "YES" if this is the case, and "NO" otherwise (without the quotes). Because Bob is lazy (it is part of his name, after all), he will permanently stay in city $$$K$$$.
Line 1: Two space-separated integers, $$$N$$$ and $$$K$$$ ($$$2 ≤ N ≤ 100,000$$$, $$$0 ≤ K ≤ N-1$$$).
Line 1: "YES" if Bob will at some point see every value from $$$0$$$ to $$$N$$$ on the self-driving car's display, and "NO" otherwise (without the quotation marks)
3 1
YES
Here are the first 8 value-city states that the car will reach, with the value displayed (mod $$$N+1$$$), as it is on the car:
1: value: 1 city: 1
2: value: 3 city: 2
3: value: 0 city: 1
4: value: 2 city: 2
5: value: 3 city: 1
6: value: 1 city: 2
7: value: 2 city: 1
8: value: 0 city: 2
Bob is at city 1, and he will see value 0 at step 3, value 1 at step 1, value 2 at step 7, and value 3 at step 5. These are all of the possible values, (mod $$$N+1$$$), so the answer is "YES".
Lazy Bob has recently discovered how cool trucks are, so one day he decides to stand on the side of the freeway and stare at some. In one given day, he knows that he will see $$$N$$$ ($$$2 ≤ N ≤ 200,000$$$) trucks pass by him.
He notices that each truck has a defining feature: the length between the front and back wheels, given by an integer $$$a_i$$$ ($$$1 ≤ a_i ≤ 1,000,000$$$). All of the trucks he sees have different $$$a_i$$$ values.
Now, Bob wants to take two pictures, each containing a different truck, to show to his friends at school. Because longer trucks are cooler, but he wants to show his friends the variety of lengths in trucks, he assigns a pair of trucks with lengths $$$a_i$$$ and $$$a_j$$$ an arbitrary score of $$$(a_i + a_j)^{|a_i - a_j|}$$$. Please help Bob find the maximum such value for any pair of trucks $$$i ≠ j$$$. Because this value can be very large, give Bob the maximum truck-pair score (mod $$$10^9 + 7$$$). Just to clarify, Bob wants [the maximum truck-pair score] (mod $$$10^9 + 7$$$), not the maximum remainder of a truck-pair score when divided by $$$10^9 + 7$$$.
Line 1: One integer $$$N$$$ ($$$2 ≤ N ≤ 200,000$$$).
Line 2: $$$N$$$ space-separated integers: $$$a_1$$$, $$$a_2$$$, … $$$a_N$$$ ( $$$1 ≤ a_i ≤ 1,000,000$$$, all $$$a_i$$$ distinct), each describing the $$$i$$$th truck's length.
Line 1: One integer representing the remainder when the maximum truck-pair score between any pair of trucks is divided by $$$10^9 + 7$$$.
3 1 5 2
1296
Here are the scores for each pair of trucks:
$$$1$$$ & $$$2$$$: $$$(1+5)^{|1-5|} = 6^4 = 1296$$$
$$$1$$$ & $$$3$$$: $$$(1+2)^{|1-2|} = 3^1 = 3$$$
$$$2$$$ & $$$1$$$: $$$(5+1)^{|5-1|} = 6^4 = 1296$$$
$$$2$$$ & $$$3$$$: $$$(5+2)^{|5-2|} = 7^3 = 343$$$
$$$3$$$ & $$$1$$$: $$$(2+1)^{|2-1|} = 3^1 = 3$$$
$$$3$$$ & $$$2$$$: $$$(2+5)^{|2-5|} = 7^3 = 343$$$
The maximum truck-pair score is between trucks $$$1$$$ & $$$2$$$, and that value, when taken (mod $$$10^9 + 7$$$), is $$$1296$$$.
This time, he wants to determine the number of ordered pairs of prime numbers ($$$p,q$$$) such that when $$$N=p^2+q^3$$$ is written in base $$$T$$$, without leading zeros, each digit from $$$0$$$ to $$$T-1$$$ appears exactly once.
Solve the math problem.
Line 1: One integer, $$$T$$$ ($$$2 ≤ T ≤ 10$$$).
Line 1: One integer, representing the number of ordered pairs of prime numbers ($$$p,q$$$), as described in the problem statement.
3
0
Written in base-$$$3$$$, the only possible $$$N$$$ are $$$012, 021, 102, 120, 201$$$, and $$$210$$$. The maximum is $$$210$$$, which is $$$21$$$ in base $$$10$$$. The smallest possible number that can be written as $$$p^2+q^3$$$ is $$$3^2+2^3=17$$$, and the second smallest is $$$2^2+3^3=31$$$, so none of these possible $$$N$$$ can be written in this form. Thus, the answer is $$$0$$$.
Recently, Sparkle has been interested in vehicles, so she has set up a number line and placed $$$N$$$ ($$$1 \le N \le 5000$$$) trucks with equal mass on it. The $$$i$$$-th truck is initially located at position $$$x_i$$$ ($$$1 \le x_i \le 10^9$$$) with velocity $$$v_i$$$ ($$$-10^9 \le v_i \le 10^9$$$). Since this is all a dream, when two trucks collide, they will not explode, but rather undergo a perfectly elastic collision, ie. if two trucks collide, their velocities will be swapped. Sparkle is now curious about the number of times the trucks will collide, and she wants you to find this number or tell her that there will be infinite collisions. Note that if $$$k$$$ trucks collide at the same time, then this will be counted as $$$\frac{k(k - 1)}{2}$$$ collisions.
The first line contains a single integer $$$N$$$ ($$$1 \le N \le 5000$$$).
Each of the next $$$N$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le 10^9$$$, $$$-10^9 \le v_i \le 10^9$$$). It is guaranteed that all $$$x_i$$$ are distinct.
Output a single integer denoting the total number of collisions or $$$-1$$$ if there will be infinite collisions.
21 12 -1
1
The two trucks will move towards each other and collide once before going into opposite directions and never colliding again.
There is a linear portion of road composed of $$$N$$$ units denoted by either a period (".") for pavement or an asterisk ("*") for a traffic light. The traffic lights do not count in the length of the road. Cobby the construction worker is told that he must remove exactly one traffic light so that there are no more than $$$L$$$ traffic lights every kilometer on the road. However, since he is American, he has no idea how long a kilometer is. Please help Cobby find the maximum length a kilometer could be, in units.
Traffic lights at the end of the boundary of a kilometer are not counted in the traffic light count for that kilometer. It is guaranteed that there is at least one unit of road separating two traffic lights.
Line 1: Two space-separated integers $$$N$$$ and $$$L$$$ ($$$1 ≤ L \lt N ≤ 10^6$$$).
Line 2: A string of length $$$N$$$ representing the road with traffic lights.
Line 1: An integer representing the maximum length a kilometer could be, in units.
15 2*...*.*..*...*.
7
If a kilometer is $$$7$$$ units long, the third traffic light could be removed so that the distance of road after the second traffic light has no more than $$$2$$$ traffic lights. Note that only the road portions (".") count in the distance of the kilometer.
It's common knowledge that Corviknight fly air taxis in Galar. However, since they are always on edge due to the presence of Tinkaton, they think about interesting number theory properties to occupy their minds.
One day, Rowlet proposed a simple and fun game to the Corviknight population. It is known that Galar has $$$N$$$ cities, and each has a unique population $$$a_i$$$. Rowlet wants to find the number of ordered triples of cities $$$(i, j, k)$$$ such that the greatest common divisor of the populations of the first two cities is equal to the least common multiple of the populations of the second two cities.
The first line of input contains a number $$$T$$$ $$$(1 \leq T \leq 5*10^4)$$$, denoting the number of test cases.
Each test case contains on its first line $$$N$$$ $$$(1 \leq N \leq 2*10^5)$$$, the number of cities in Galar. The second line contains $$$N$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq 2*10^5)$$$. All values are pairwise distinct.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2*10^5$$$.
A single number, the number of triples.
431 2 441 6 2 361 3 4 8 6 2451 7 2 5 3
1 2 8 0
In the first test case, the only valid triple is $$$(3, 2, 1)$$$, since $$$gcd(a_3, a_2) = lcm(a_2, a_1)$$$.
In the second test case, the valid triples are $$$(2, 3, 1)$$$ and $$$(2, 4, 1)$$$.
In the last test case, it can be shown that there are no valid triples.
The Interastral Peace Corporation (IPC) owns a permutation $$$a_1, a_2, \ldots, a_N$$$ of length $$$N$$$ ($$$2 \le N \le 10^3$$$).
Infamous hacker Silver Wolf has performed $$$Q$$$ ($$$1 \le Q \le 10^5$$$) operations to mess up the permutation:
- "l r" — Rotate the interval $$$[l, r]$$$, ie. set $$$a_i = a_{i + 1}$$$ and $$$a_r = a_l$$$.
After these operations, the IPC will have to restore their permutation to its sorted form after reaching performing some swaps on it. However, they are not completely sure of the rotation that Silver Wolf will perform these operations in. Thus, they need you to find the sum of the minimum number of swaps the IPC will need to restore their permutation over all rotations of operations. Formally, let $$$o_0, o_1, \ldots, o_{Q - 1}$$$ be the operations. Silver Wolf may choose any non-negative integer $$$x$$$ and set $$$o_i = o_{(i + x)\%Q}$$$. Let $$$f(x)$$$ be the minimum number of swaps the IPC needs to restore their permutation for a given $$$x$$$ that Silver Wolf chooses. You need to find $$$\sum_{x=0}^{Q - 1} f(x)$$$.
The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$2 \le N \le 10^3$$$, $$$1 \le Q \le 10^5$$$).
The next $$$Q$$$ lines contain two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \lt r \le N$$$). The $$$i$$$-th line denotes that Silver Wolf will perform an operation rotating the interval $$$[l, r]$$$.
Output a single integer, $$$\sum_{x=0}^{Q - 1} f(x)$$$.
5 21 42 5
8
For $$$x = 0$$$, the IPC's final permutation will be $$$[2, 4, 1, 5, 3]$$$. This can be sorted by swapping the indices $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(3, 5)$$$, and $$$(4, 5)$$$ in that order.
For $$$x = 1$$$, the IPC's final permutation will be $$$[3, 4, 5, 1, 2]$$$. This can be sorted by swapping the indices $$$(1, 4)$$$, $$$(2, 5)$$$, $$$(3, 4)$$$, and $$$(4, 5)$$$ in that order.
Two thousand years ago, someone took the first step towards defeating the Dark Lord. Now, Yuria and friends are continuing that journey. However, before they can defeat the Dark Lord, they must first defeat their crippling boredom, since as it turns out, riding on a wagon for months on end is not the most fun experience. Thus, Yuria has devised a game that she and her party can play while on the road. Yuria creates an array of $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) $$$1$$$'s and $$$0$$$'s, represented by the array $$$a_1, a_2, \ldots, a_N$$$ ($$$0 \le a_i \le 1$$$). Then, she will perform $$$Q$$$ ($$$1 \le Q \le 2 \cdot 10^5$$$) queries on the array:
- "1 l r" — Flip the values of all values in the subarray $$$a_l, a_{l + 1}, \ldots, a_r$$$. Formally, set $$$a_i = (a_i + 1)\%2$$$ for all $$$l \le i \le r$$$.
- "2 l r" — Play a game using the values in the subarray $$$a_l, a_{l + 1}, \ldots, a_r$$$, where players take turns selecting a maximal subarray containing either all $$$1$$$'s or all $$$0$$$'s and remove it. The player who cannot make a move loses. Note that any subarray a player chooses must be maximal, meaning that it cannot be contained by a larger subarray containing all $$$1$$$'s or all $$$0$$$'s. Since Yuria is not very responsible at cleaning up after herself, after playing the game, all of the values in the subarray will be reset to $$$0$$$, ie. $$$a_i = 0$$$ for all $$$l \le i \le r$$$. Please tell Yuria if she will win as the player who makes the first move.
The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N, Q \le 2 \cdot 10^5$$$).
The second line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$0 \le a_i \le 1$$$).
The next $$$Q$$$ lines each contain three integers $$$t$$$, $$$l$$$, and $$$r$$$ ($$$1 \le t \le 2$$$, $$$1 \le l \le r \le N$$$).
For each query of type $$$t = 2$$$, output "YES" if the player who makes the first move will win, "NO" if the player who makes the second move will win, and "DRAW" if the game will end in a tie.
9 71001110102 7 92 6 72 3 91 6 72 4 81 4 42 6 7
YES NO YES YES YES
The first query uses the subarray $$$010$$$, and it can be shown that Yuria will win as the first player.
After the first query, the subarray is reset to $$$0$$$, so the array will become $$$100111000$$$.
After the third query, the array values are $$$100000000$$$.
The fourth query flips the interval $$$[6, 7]$$$, so the array will become $$$100001100$$$.