Santa needs to deliver gifts to all the inhabitants of Speedway! Unfortunately, as it doesn't snow on Speedway (mostly), his sleigh will damage the nice brickwork!
As we all know, Speedway is built in a line, conveniently segmented into $$$N$$$ locations. Although speedy, Santa's delivery system hasn't been fully optimized, so he travels back-and-forth to deliver these gifts.
Beginning at the first provided location, Santa will travel between all $$$N$$$ of these locations. When Santa travels between a location $$$A$$$ and $$$B$$$, he creates one unit of damage at each location between $$$A$$$ and $$$B$$$ (including $$$A$$$, not including $$$B$$$).
To help the UT Maintenance team, please determine how much total damage is caused by Santa's sleigh.
The first line of input contains a single integer $$$N$$$, where $$$2 \leq N \leq 1000$$$.
Then $$$N$$$ more lines follow, each containing a single integer, representing all the buildings in the order in which he visits them.
A single integer, the total damage that Santa's sleigh creates on Speedway.
2 2 1
1
3 3 1 2
3
Santa has decided he wants to be lazy this year. Instead of delivering his presents himself, he has decided that he wants his elves to do it. Fortunately, Santa has an infinite number of elves at his disposal, and fortunately, $$$k$$$ elves volunteered to deliver presents to the $$$k$$$ houses that need presents to be delivered to.
There are $$$n + 1$$$ total locations in the world that Santa's elves can travel to, with location $$$0$$$ being the North Pole, where Santa and his elves currently reside. There are $$$k$$$ locations such that houses exist, and there are $$$m$$$ bidirectional pathways that connect two locations $$$m_u, m_v$$$ with a travel time of $$$m_c$$$ seconds. If two locations are not connected by any series of pathways, then trying to travel between them is infeasible. There may be multiple pathways between two houses, but it is guaranteed that all houses are reachable from location 0.
Given that each elf is assigned to one house and takes the most optimal route to and from their designated house, Santa is curious about two things. First, Santa wants to know the total travel time for all elves. Second, Santa wants to know the maximum travel time for any elf. Help Santa find the answer to his two questions!
The first line of the input will contain three space separated integers $$$n (1 \le n \le 10^4), k (1 \le k \le n), m (1 \le m \le 10^5)$$$, where $$$n + 1$$$ is the number of locations, $$$k$$$ is the number of houses, and $$$m$$$ is the number of pathways.
The next $$$k$$$ lines of input will each contain a number $$$k_i$$$ ($$$1 \leq k_i \leq n$$$) representing a house at location $$$k_i$$$. It is guaranteed all house locations are unique.
The next $$$m$$$ lines of input after that will each contain 3 space separated integers $$$m_u, m_v, m_c$$$, where $$$0 \le m_u, m_v \le n$$$, $$$m_u \neq m_v$$$, and $$$1 \le m_c \le 10^3$$$.
Output two space separated integers, the first being the total travel time for all the elves, and the second being the longest travel time of any elf.
5 3 6 3 5 4 2 3 5 4 2 2 0 4 2 2 1 6 1 5 9 5 1 4
50 28
The winter season fills Meredith's heart with joy and warmth, and there is no better outlet for her to express her appreciation apart from constructing the most magnificent holiday wreath! In fact, Meredith wants to make as large a wreath as possible, given her materials. She has plucked two branches from a tree and will construct her wreath by attaching the two branches together, using two small and flexible twigs. Help Meredith make the biggest wreath possible!
The first line of input will contain an integer $$$V_1$$$ ($$$1 \leq V_1 \leq 10^6$$$) denoting the number of vertices in Meredith's first branch. $$$V_1 - 1$$$ lines follow, each containing two space-separated integers $$$u$$$ and $$$v$$$ which represent endpoints for an edge in the tree. (Observe that, in general, any tree with $$$n$$$ vertices has exactly $$$n - 1$$$ edges). Then the next line of input contains $$$V_2$$$ ($$$1 \leq V_2 \leq 10^6$$$), the number of the vertices in the second branch. $$$V_2 - 1$$$ lines follow after that, containing the edges for the second tree. You are guaranteed that the depth of either tree (from any root) will not exceed $$$50$$$.
Print the length of the longest simple cycle Meredith could create by connecting her two branches (trees) with two edges.
7 4 6 2 3 1 7 7 2 5 1 4 7 5 3 2 2 4 5 3 3 1
9
Recently, Santa's elves went rogue and commandeered his sleigh! Rather than dropping off presents to where they are supposed to go, the elves are randomly tossing presents off the sleigh random times.
Fortunately, through a double-agent elf, Santa has determined the locations and times where the presents will be dropped. Unfortunately, the presents will be stolen by angry Canadian children (who happened to not get gifts this year) exactly 5 minutes after they are initially dropped, so Santa must be quick to pick up as many presents as he can to be delivered correctly later. The elves also want to spread out their present drops over a longer period of time, so it is guaranteed that any two present drops will be at least 5 minutes apart.
You are given a 2D square grid representing the area where elves are dropping presents and a list of present drop times and coordinate locations. In one minute, Santa can take a single step in one of the four cardinal directions or stay in place. Figure out Santa's optimal path to pick up as many presents as possible before the presents are taken and output the maximum number of presents that Santa can get.
The first line consists of $$$4$$$ integers, $$$N$$$ ($$$1 \leq N \leq 750$$$), $$$P$$$ ($$$1 \leq P \leq 1000$$$), $$$s_x$$$, $$$s_y$$$ ($$$1 \leq s_x, s_y \leq N$$$). This gives the size of the 2D square grid, number of presents that the elves will drop, and Santa's starting $$$x$$$ and $$$y$$$ coordinate, respectively. The next $$$P$$$ lines consist of three integers, $$$t_i, x_i, y_i$$$ ($$$1 \leq t_i \leq 10^6$$$), ($$$1 \leq x_i, y_i \leq N$$$), which give the time (in minutes) and location of a present drop.
Output a single integer giving the maximum number of presents that Santa can successfully collect.
5 3 1 1 1 1 1 6 5 5 11 1 1
2
10 5 1 1 23 10 3 13 10 1 18 9 1 28 10 7 8 1 10
4
In the first sample, Santa can collect the first present at time $$$1$$$, the second present at time $$$9$$$, but does not have time to get back to collect the final gift (which disappears at time $$$16$$$)
Santa is delivering presents and has one last stop tonight at the coordinates $$$(x, y)$$$ - we are representing the world as a 2D plane for simplicity. He takes a quick break at the coordinates $$$(0,0)$$$ where he decides to update the steering software on his sled. Unfortunately, the update has messed up the steering software and Santa finds out that the sled will only follow the directions in the order specified by a string $$$s$$$ which consists of the characters U, L, D, and R.
- The character U means to go up so from position $$$(a, b)$$$ go to $$$(a, b + 1)$$$.
- The character L means to go left so from position $$$(a, b)$$$ go to $$$(a - 1, b)$$$.
- The character D means to go down so from position $$$(a, b)$$$ go to $$$(a, b - 1)$$$.
- The character R means to go right so from position $$$(a, b)$$$ go to $$$(a + 1, b)$$$.
Given that the sled will perform these operations from $$$s$$$ left to right and repeat that an infinite number of times, figure out if Santa will ever end up reaching his destination at $$$(x, y)$$$.
The first line of input contains two space-separated integers $$$x$$$ and $$$y$$$ representing the coordinates that Santa is trying to get to ($$$-10^{18} \leq x, y \leq 10^{18}$$$).
The second and last line of input contains a string $$$s$$$ ($$$1 \leq |s| \leq 10^{5}$$$) representing the series of directions that Santa's sled will go ($$$s$$$ will only contain the characters U, L, D, and R).
Output Yes if the sled will ever reach the coordinates $$$(x, y)$$$ and No otherwise.
2 2 UR
Yes
1 2 RU
No
-1 1000000000000000000 LRRLU
Yes
In example 1, after going through UR once, Santa is at (1,1) and then going through that again gets Santa at (2,2) which is the goal.
The elves are creating an ID label for a toy part but their supervisor has a very weird, specific rule. The supervisor has a favorite number, and the ID label the elves must create must be divisible by this special number. The supervisor also hates the numbers 2 and 5, and his favorite number will not be divisible by either.
However, the label printer was recently used by a nefarious being to try to sabotage Christmas, and is freshly out of ink! The only thing the elves have is a printed label of a GINORMOUS integer. The label printer also does not have a 0 digit.
The elves realize that there might be ways to cut the label such that they can create a label with an ID divisible by the supervisor's favorite number, and would like to know how many ways they can do so. The resulting label must be a contiguous portion of the original, and the elves only need one label.
In other words, find the number of ways to remove some (possibly zero) digits from the front and back such that the resulting (nonempty) label is divisible by the supervisor's favorite number.
First line with $$$N$$$, the ginormous integer printed by the nefarious being $$$1 \leq N \leq 10^{10^6}$$$. No digit in $$$N$$$ is 0.
Second line with K, the supervisor's favorite integer $$$1 \leq K \leq 5000$$$, where $$$K$$$ is not divisible by 2 or 5.
One integer denoting the number of ways to cut the label.
72476 3
3
19987589742315 19
6
61413 4553
0
Santa is tired after a long night delivering presents, and has reached his final stop, Rayville.
As its name suggests, Rayville is built as a ray on the $$$x$$$-axis, from $$$0$$$ to $$$\infty$$$. Each unit length integer interval containts a house (e.g. $$$[0,1),[1,2), [2,3), \dots$$$), and on each integer coordinate there is a light pole (e.g. at points $$$(0,0), (1,0), (2,0), \dots$$$)
Santa moves along the ray from $$$0$$$ to $$$\infty$$$. Each time he reaches a light pole (excluding light pole 0), with probability $$$1/z$$$, he collapses, never to move again.
Initially, all the light poles are off. Each time Santa reaches light pole $$$i \gt 0$$$ (even if he collapses at it), he bumps into it, causing the fragile lighting system of Rayville to flicker, turning light pole $$$i$$$ to turn on with probability $$$\min(1, l/i)$$$. If this causes $$$ \gt l$$$ lightpoles to be on it overloads Rayville's electrical grid, causing one of the prior lights $$$ \lt i$$$ to go out (uniformly, at random).
When Santa collapses, he takes joy from two things: one is the set of light poles that are on. More specifically, if a light pole $$$i$$$ is on, then Santa gets $$$i$$$ units of lights joy, and the total lights joy Santa gets is the sum of all the joys from light poles.
The other is the number of ways he could have delivered exactly $$$m$$$ presents to the houses he has passed, call this Santa's presents joy. (Two ways are considered different iff there is some house that gets a different number of presents in each way).
Santas total joy is the product of the above two sources, that is lights joy * presents joy.
What is Santa's expected total joy? Output your answer $$$\mod 10^9 + 7$$$.
One line containing 3 space separated integers, $$$l$$$, $$$m$$$, $$$z$$$, ($$$1\leq l,m \leq 10^6$$$), ($$$1\leq z \leq 10^9$$$). $$$l$$$ is the max number of lightpoles that can be on, $$$m$$$ is the number of presents Santa must deliver, and $$$1/z$$$ is the probability Santa dies at any light pole.
Santa's expected total joy$$$\mod 10^9 + 7$$$.
1 1 2
4
The winter solstice is fast approaching, and so is the grand ball hosted at the South Pole! You, one of the event planners, have been tasked with selecting a lineup of artists to perform in pairs. The head event planner has given you a list of $$$N-1$$$ pairs of artists who know each other as well as the number of attendees recorded the most recent time a pair duetted together. Coincidentally, every artist that appears at least once on the list knows every other artist on the list either directly or indirectly through a series of acquaintances on the list. The budget allows for up to $$$K$$$ pairs of artists to be invited to the ball, but each performer can only appear in at most one pair and the selected pairs must be a subset of the ones on the list. South Pole management wants to maximize the expected number of people in attendance, which is the sum of the attendees from the previous performances of the each duo. Of course, only a certain programmer can find this expected count to help out with logistical calculations.
The first line of input contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N, K \leq 100000$$$), representing the number of artist pairs that know each other for consideration and the maximum number of pairs that can requested to perform, respectively. Each of the next $$$N-1$$$ lines contains three integers $$$x$$$, $$$y$$$, and $$$p$$$, where $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq N$$$) represent two artists who know each other and $$$p$$$ ($$$1 \leq p \leq 10000$$$) is the number of people that showed up to their last performance.
Output a single integer representing the expected number of people in attendance with an optimal lineup.
8 4 1 2 9 2 3 10 3 4 11 4 5 12 5 6 13 6 7 14 7 8 15
48
8 2 1 2 9 2 3 10 3 4 11 4 5 12 5 6 13 6 7 14 7 8 15
28
4 3 1 2 1 2 3 2 3 4 3
4