A jellyfish lives on a $$$1$$$-dimensional coordinate system (i.e. a number line). It starts at point $$$0$$$, and wants to swim to point $$$n$$$, where $$$n$$$ is some multiple of $$$12$$$. Unfortunately, jellyfish can't swim in the night. In each day, with $$$12$$$ hours of sunlight, the jellyfish will swim $$$1$$$ point forward each hour. However, when night comes, for another $$$12$$$ hours, it will let itself drift in the current, each hour moving either $$$1$$$ point forward, $$$1$$$ point backward, or not moving at all. All three possibilities occur with equal probability (that is, each possible move occurs with probability $$$\frac{1}{3}$$$). The jellyfish would like to know what the expected number of days are before it reaches its destination. Alas, as it is a jellyfish, it does not know how expected value works. Please help it!
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.
The first and only line of each test case contains a single integer, $$$n$$$ ($$$12 \le n \le 1200$$$). Note that $$$n$$$ is guaranteed to be a multiple of $$$12$$$.
For each test case, print a single integer denoting the expected number of days before the jellyfish reaches its destination.
2 12 24
1 2
Tortles recently learned about FFT, or the Fast Fourier Transform algorithm, which can be used to multiply two polynomials together in $$$O(NlogN)$$$. He decided to play around with the algorithm for fun.
Tortles started with two polynomials $$$a$$$ and $$$b$$$, and then used FFT to multiply them together, forming a new polynomial $$$c$$$. However, his computer soon crashed, and he lost his edit history, meaning Tortles only knows his new polynomial $$$c$$$. Given $$$c$$$, please help Tortles find any possibility for what $$$a$$$ or $$$b$$$ could have been.
The first line will contain an integer $$$l$$$ ($$$0 \le l \le 10^5$$$) denoting the degree of the polynomial.
The second line will contain $$$l + 1$$$ integers, $$$f_0, f_1, f_2, ..., f_{l}$$$ ($$$-10^5 \le f_i \le 10^5$$$), where $$$f_i$$$ is the coefficient of $$$x^i$$$ in the polynomial $$$c$$$.
On the first line, output the degree $$$n$$$ ($$$0 \le n \le 10^5$$$) of $$$a$$$.
On the second line, output $$$n + 1$$$ integers $$$p_0, p_1, \ldots, p_n$$$ where $$$p_i$$$ is the coefficient of $$$x^i$$$ in $$$a$$$.
On the third line, print the degree $$$m$$$ ($$$0 \le m \le 10^5$$$) of $$$b$$$.
On the fourth line, output $$$m + 1$$$ integers $$$q_0, q_1, \ldots, q_m$$$ where $$$q_i$$$ is the coefficient of $$$x^i$$$ in $$$b$$$.
2 6 5 1
1 3 1 1 2 1
In this sample, $$$c$$$ is equal to $$$x^2 + 5x + 6$$$, which can be factored into $$$(x + 2)(x + 3)$$$.
You are playing a video game and trying to beat a boss with your friend! The boss has $$$x$$$ hitpoints. The two of you start off by dealing $$$y$$$ damage per turn. Due to how the game works, you two have special values that you can use to modify the damage you deal each turn. For a given special value $$$s$$$, the modification consists of setting $$$y$$$ to be equal to $$$y \oplus s$$$ where $$$\oplus$$$ denotes the bitwise XOR operation. Your friend has value $$$a$$$, while you have value $$$b$$$. Unfortunately, your friend does not care about optimality, and will perform his modification every turn (that is, set $$$y$$$ to be equal to $$$y \oplus a$$$). You however, want to beat the boss as fast as possible, and will therefore choose on every turn after your friend performs his modification whether or not to perform another modification of your own with your own value (that is, set $$$y$$$ to be equal to $$$y \oplus b$$$) before doing damage to the boss. Assuming you choose an optimal sequence of modifications, what is the minimum number of turns before you beat the boss?
More formally, given $$$x, y, a$$$, and $$$b$$$, you want to find the minimum number of terms in the sequence $$$c_1, c_2, \ldots, c_n$$$ such that $$$\sum_{i = 1}^{n} c_i \ge x$$$. Here, $$$c_0 = y$$$, and $$$c_i = c_{i - 1} \oplus a \oplus (b \cdot k)$$$, where $$$k \in \{0, 1\}$$$, and you choose the value of $$$k$$$ for each term.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$). The description of the test cases follows.
The first and only line of each test case contains four integers $$$x$$$, $$$y$$$, $$$a$$$, and $$$b$$$ ($$$1 \leq x$$$, $$$y$$$, $$$a$$$, $$$b \leq 10^9$$$).
For each test case, output a single integer denoting the minimum number of turns required to beat the boss.
3 7 3 5 1 9 4 5 6 10 1 1 1
1 2 10
For the first testcase, if we choose to perform the modification on the first move, we deal $$$3 \oplus 5 \oplus 1 = 7$$$ damage, so we can defeat the boss in one move.
For the second testcase, if we choose to perform the modification on the first move, we deal $$$4 \oplus 5 \oplus 6 = 7$$$ damage, so the boss has $$$9 - 7 = 2$$$ health remaining after the first move. If we choose not to perform the modification on the second move, we deal $$$7 \oplus 5 = 2$$$ damage, so we can defeat the boss in two moves. It can be shown that this is a lower bound on the minimum number of moves needed to defeat the boss.
After being inspired by a certain anime, Keys decided to get a dog. Unfortunately, the dog enjoys trolling Keys when they go out for walks.
Keys and his dog are going for a walk on an infinite two-dimensional plane with $$$n$$$ trees for $$$t$$$ minutes. Keys starts at position $$$(x_1, y_1)$$$, and the dog starts at position $$$(x_2, y_2)$$$. There is a leash between them that is equal to the Euclidean distance between them. The dog wants to increase the length of the leash as much as possible to annoy Keys.
Every minute the dog can move $$$1$$$ unit horizontally or vertically. If the dog ever moves to some location $$$(x_i, y_i)$$$ where a tree is located, he can choose to wrap the leash around the tree, which leads to the length of the leash becoming the sum of the Euclidean distance from $$$(x_1, y_1)$$$ to $$$(x_i, y_i)$$$ and the Euclidean distance from $$$(x_i, y_i)$$$ to the dog's current position.
The dog can wrap around as many trees as he wishes. For example, wrapping around two trees would make the leash become the distance from Keys to the first tree plus the distance from the first tree to the second tree plus the distance from the second tree to the dog's current location.
After $$$t$$$ minutes elapse, how long can the dog make the leash?
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$t$$$ ($$$1 \le n, t \le 2 \cdot 10^5$$$).
The second line of each test case contains four integers $$$x_1,$$$ $$$y_1,$$$ $$$x_2,$$$ $$$y_2$$$ ($$$-10^9 \le x_1, y_1, x_2, y_2 \le 10^9$$$).
Each of the next $$$n$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$-10^9 \le x, y \le 10^9$$$) denoting a tree at $$$(x, y)$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print a single real number denoting the maximum length the dog can make the leash.
Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.
3 2 1 1 1 2 1 3 3 4 4 1 20 1 1 2 2 3 3 1 100 1 1 2 2 3 3
2.0000000 21.0237960 101.0049504
2 1 10 0 0 2 2 3 3 2 5 -1 0 1 -1 10 90 -1 -1
12.2426407 7.0710678
After solving a lot of competitive programming problems, Tortles and Keys are tired of seeing TLE (or Time Limit Exceeded) verdicts! The two of them were recently sent a string $$$s$$$ by their friends consisting solely of a combination of letters $$$\mathrm{t}$$$, $$$\mathrm{u}$$$, $$$\mathrm{r}$$$, $$$\mathrm{l}$$$, and $$$\mathrm{e}$$$. They were challenged to write a program to see if it is possible to remove all the characters in the string. They are allowed to erase all the characters in a substring with "$$$\mathrm{tle}$$$" as a subsequence if the first and the last characters of the substring are equal to $$$\mathrm{t}$$$ and $$$\mathrm{e}$$$ respectively. That is, the two of them are allowed to erase a substring $$$s_l, s_{l + 1}, \ldots, s_r$$$ if and only if $$$s_l = $$$ $$$\mathrm{t}$$$, $$$s_r = $$$ $$$\mathrm{e}$$$, and there exists an index $$$i$$$ where $$$i \in [l + 1, r - 1]$$$ and $$$s_i = $$$ $$$\mathrm{l}$$$. To make it a bit harder, every time the two of them erase any substring, the entire remaining string reverses itself! Sadly, when attempting to solve this problem, Tortles and Keys' program TLEd. Please help them solve this problem!
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$). The description of the test cases follows.
The first and only line of each test case contains a string $$$s$$$ of length $$$|s|$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$).
It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
Output $$$t$$$ lines, with each line being YES if it's possible to erase the entire string or NO if it is impossible.
4 turtle euttutrlelet eltrut tleelt
YES YES NO YES
For Valentine's Day, Iura was looking forward to getting some chocolates. Unfortunately, all he got was the gcd function, where $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.
Given $$$a$$$, $$$b$$$, $$$d$$$, help Iura find $$$$$$\sum_{i = 0}^{d} \gcd(a + i, b + i)$$$$$$ Since the answer could be large, find it modulo $$$10^9 + 7$$$.
The first line will contain $$$T$$$, $$$1 \le T \le 10$$$, the number of testcases.
Each testcase will have three space separated integers $$$a$$$, $$$b$$$, and $$$d$$$, $$$1 \le a, b \le 10^9$$$, $$$1 \le d \le 10^{18}$$$.
Print a single integer per testcase representing the sum.
2 1 7 5 2 8 8
15 22
Frieren wants to learn a new spell. Unfortunately, the spell is hidden in a grimoire that has an interesting lock on it. To help unlock the lock, help Frieren solve this problem!
The function $$$f(x, y)$$$ is defined below.
int f(int x, int y) {
int ans = 0;
while (x != 0 and y != 0) {
int g = gcd(x, y);
x -= g;
y -= g;
ans++;
}
return ans;
}
Calculate $$$$$$\sum_{i = 0}^{d} f(a + i, a + p^x + i)$$$$$$ where $$$p$$$ is a prime. Since the answer could be large print it modulo $$$10^9 + 7$$$.
The first line will contain four positive integers $$$a$$$, $$$p$$$, $$$x$$$, and $$$d$$$. Note that it is guaranteed that $$$p$$$ will be a prime.
$$$1 \le a \le a + p^x + d \le 10^{18}$$$.
Print a single integer representing the answer.
2 2 3 8
16
10 7 2 100
678
There is a tree with $$$n$$$ nodes rooted at node $$$1$$$; each node has a value $$$a_i$$$. Tortles and Keys both start at the root of the tree. Every second, Keys can choose to either move once to an adjacent node or choose to stay at the current node. On the other hand, Tortles can only move once every two seconds. Keys always makes his move before Tortles. Tortles is chasing Keys, and will always move towards Keys on the direct path between them. Keys' goal is to collect as much money as he can. After Keys either makes a move or chooses to stay, Keys will get $$$x$$$ dollars, where $$$x$$$ is the value of the node he is currently at. However, if Tortles ever is on the same node as Keys outside of their initial intersection at the root, Keys has to leave the tree and can no longer continue getting money. This also means that if Keys decides to make a move onto the same node Tortles is at, Keys has to instantly leave the tree and will not collect any money from that node.
If Keys must make a move away from the root in the first second, what is the maximum amount of money he can obtain?
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 4000$$$).
The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
The next $$$n - 1$$$ lines contain two integers $$$u$$$ and $$$v$$$, denoting an edge from the $$$u$$$-th node to the $$$v$$$-th node ($$$1 \le u, v \le n, u \neq v$$$). It is guaranteed that the given edges form a valid tree.
Output a single integer denoting the maximum amount of money Keys can obtain before he is inevitably caught. It can be shown that Tortles will always eventually catch Keys.
5 1 2 3 4 5 1 2 2 3 3 4 3 5
25
10 1 1 1 1 1 1 1 1000 10 990 1 2 2 3 3 4 4 5 5 6 6 7 7 8 6 9 9 10
8006
In the first sample, an optimal route for Keys looks like the following: Move from node $$$1$$$ to node $$$2$$$ and then collect $$$2$$$ dollars. Then, move from node $$$2$$$ to node $$$3$$$ and collect $$$3$$$ dollars. At this point, Tortles will move from node $$$1$$$ to node $$$2$$$. Then, Keys should move to node $$$5$$$, and stay there for $$$4$$$ seconds to collect $$$4 \cdot 5 = 20$$$ dollars before Tortles eventually catches Keys.