Arthur the ant lives in a beautiful garden that contains a large pond containing multiple lily pads. The pond can be described as an $$$n \times m$$$ grid containing $$$k$$$ lily pads. The $$$i$$$-th lily pad is located at position $$$(x_i, y_i)$$$ on the pond. There are always lily pads on location $$$(1,1)$$$ and $$$(n,m)$$$.
Arthur is located at position $$$(1,1)$$$ but he wants to walk to position $$$(n,m)$$$. As ants cannot swim he must wait for the lily pads to grow. During each day the lily pads will expand to all neighbouring locations, that is, if at day $$$j$$$ location $$$(a,b)$$$ is covered by a lily pad, then in day $$$j+1$$$ locations $$$(a+1, b), (a-1, b), (a, b+1)$$$ and $$$(a, b-1)$$$ will also be covered by lily pads.
Arthur can walk to neighbouring locations that contain lily pads. If Arthur is located at position $$$(a,b)$$$ then he can walk to locations $$$(a+1, b), (a-1, b), (a, b+1)$$$ and $$$(a, b-1)$$$ if they are covered by a lily pad.
Arthur isn't the smartest ant, so he asks you how many days does he have to wait until there exists a path from $$$(1,1)$$$ to $$$(n,m)$$$ that contains lily pads.
Each test contains multiple test cases. The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 5 \cdot 10^4)$$$, the number of test cases. The description of the $$$t$$$ test cases follow.
The first line of each test case contains three integers $$$n, m, k$$$ ($$$1 \leq n,m \leq 10^9, 2 \leq k \leq 10^5$$$), the dimensions of the pond and the number of lily pads.
The next $$$k$$$ lines of each test case contain two integers $$$x_i, y_i$$$ ($$$1 \leq x_i \leq n, 1 \leq y_i \leq m$$$), corresponding to the location of the $$$i$$$-th lily pad.
It is guaranteed lily pads $$$(1,1)$$$ and $$$(n,m)$$$ are always contained in the input, and that the sum of $$$k$$$ over all test cases does not exceed $$$10^5$$$. It is also guaranteed that $$$n = m = 1$$$ will never happen.
For each test case, output the minimum number of days that Arthur has to wait until there exists a path from $$$(1,1)$$$ to $$$(n,m$$$) that contains lily pads.
15 6 41 12 42 65 6
2
Visualization of test case 1
After 0 days 
After 1 day 
After 2 days : There exists a path now from (1,1) to (5,6)
We have a collection of problems, called a problem set. Each problem $$$P$$$ has its difficulty $$$d(P)$$$ and beauty $$$b(P)$$$.
A contest is an ordered set of problems selected from the problem set. The beauty of a contest is the sum of individual beauties of the problems it consists of.
Let $$$(P_1, P_2, \dots, P_k)$$$ be the problems in the contest. For a contest to be valid, each problem must be roughly twice as difficult as the one immediately preceding it, formally
$$$$$$\forall i \in \{2, \dots, k\}: d(P_{i-1}) = \left\lfloor \frac{d(P_i)}{2} \right\rfloor$$$$$$
Initially, the problem set is empty. You are given $$$n$$$ operations which modify the problem set. Each of these operations is described by a single line consisting of three integers, as follows:
- 1 d b: A problem with difficulty $$$d$$$ and beauty $$$b$$$ is added to the problem set.
- 2 d b: A problem with difficulty $$$d$$$ and beauty $$$b$$$ is removed from the problem set. It is guaranteed that there is at least one such problem.
After each operation, output the beauty of the most beautiful valid contest using some problems (possibly all or none) from the problem set.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of operations.
Each of the following $$$n$$$ lines consists of three space-separated integers $$$t_i$$$, $$$d_i$$$, $$$b_i$$$ ($$$1 \leq t_i \leq 2$$$, $$$1 \leq d_i \leq 10^6$$$, $$$-10^{17} \leq b_i \leq 10^{17}$$$) — the operation to be made, the problem difficulty and the problem beauty, respectively.
For each operation, output a single line with an integer: the beauty of the most beautiful contest given the current problem set.
101 1 101 2 101 3 201 4 201 5 202 3 202 2 102 4 202 5 202 1 10
10 20 30 40 40 40 20 20 10 0
11 10 -50
0
Continued fractions are a powerful mathematical tool. They are however, too complicated, so we have created our own definition.
Let $$$(a, b)$$$ be a pair of positive integers. We call the sequence $$$\left \{\frac{a+n}{b+n} \right\}_{n=0}^{\infty}$$$ the continued fractions of the pair $$$(a, b)$$$. For example, if $$$a = 14$$$ and $$$b = 2$$$, the sequence of continued fractions begins with $$$\frac{14}{2}$$$, $$$\frac{15}{3}$$$, $$$\frac{16}{4}$$$, $$$\frac{17}{5}$$$, $$$\frac{18}{6}$$$, $$$\frac{19}{7}$$$.
Note that if $$$a \neq b$$$ the sequence of continued fractions contains only a finite number of integers. In the above example, the elements that are integers are those with indices $$$n = 0, 1, 2, 4, 10$$$.
We define the integrity of a pair of integers $$$(a, b)$$$ to be the length of the longest prefix of the sequence of continued fractions that contains only integers. For example $$$\textrm{integrity}(14, 2) = 3$$$.
You are given a positive integer $$$p$$$. Your task is to find and report all pairs of integers $$$(a, b)$$$ that satisfy the following two conditions:
- $$$\frac{a}{b} = p$$$
- $$$\textrm{integrity}(a, b) \geq 3$$$
The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 20$$$) — the number of test cases.
$$$t$$$ lines follow (one for each test case), the $$$i$$$-th of which ($$$1 \leq i \leq t$$$) is containing a single integer $$$p_i$$$ ($$$2 \leq p_i \leq 10^{18}$$$) — corresponding to the $$$p$$$ from the description above.
For each test case, first output one line containing a single integer $$$k$$$ – the number of pairs $$$(a, b)$$$ satisfying the two conditions from the problem statement. Then output $$$k$$$ integers $$$b_1, b_2, \dots, b_k$$$ — the values of $$$b$$$ sorted in ascending order.
Note that under the constraints of the problem it can be shown that the sum of all $$$k$$$ is at most $$$100\,000$$$.
17
2 1 2
In the mystical land of District 42, where life, the universe, and everything is just a little bit odd, residents ponder a curious question. They observe the sequence of numbers $$$1, 2, 3, \dots, n$$$ without leading zeros or commas. Their quest is to determine how many times the mystical number $$$42$$$ appears within this sequence.
The only line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the length of the sequence.
Print one integer — number of times $$$42$$$ appears.
24
0
25
1
250
9
In the second example, the sequence is $$$1234567891011\dots2{\bf 42}5$$$, at which point $$$42$$$ appears for the first time.
Let $$$t$$$ be a string of '(' and ')'. The beauty of such a string is the length of its longest subsequence (not necessarily contiguous) that is correctly parenthesised. A string $$$a$$$ is a subsequence of the string $$$t$$$ if $$$a$$$ can be obtained from $$$t$$$ by the deletion of several (possibly, zero or all) characters. A string is considered to be correctly parenthesised if it satisfies the following conditions:
- The string consists solely of the characters '(' and ')'.
- The number of opening parentheses '(' is equal to the number of closing parentheses ')'.
- For every prefix of the string, the number of opening parentheses is greater than or equal to the number of closing parentheses.
You are given a string $$$s$$$ consisting of characters '(', ')' and '?'. Replace each '?' by either '(' or ')' such that the beauty of the resulting string $$$t$$$ is minimized.
The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 4 \cdot 10^6$$$) — the length of the input string.
The second line contains the string $$$s$$$ of length $$$n$$$. $$$s$$$ consists of only characters '(', ')' and '?'.
Output the minimum possible beauty.
10(((??)))))
6
22()??)((?)?)()()?)??)?)
10
In the first example, there are four ways of substituting the '?':
- ((((()))))
- (((())))))
- ((()()))))
- ((()))))))
The beauty of these strings is $$$10$$$, $$$8$$$, $$$8$$$, and $$$6$$$, respectively.
Given an integer $$$x$$$, find the largest integer $$$y \leq x$$$ such that $$$y$$$ is a prime and can be written as a factorial, if such a $$$y$$$ does not exist print $$$-1$$$.
An integer $$$y$$$ can be written as a factorial if there exists an integer $$$z$$$ such that $$$1 \cdot 2 \cdot \ldots \cdot (z-1) \cdot z = y$$$.
The only line of input contains the integer $$$x$$$ $$$(1 \leq x \leq 10^5)$$$.
Print the largest integer $$$y \leq x$$$ such that $$$y$$$ is a prime and can be written as a factorial, if such a $$$y$$$ does not exist print out $$$-1$$$.
1
-1
2
2
Tony and Ben are two classmates who typically get very bored throughout their summer vacation. To cure their boredom, they always try out the silliest games they can come up with. The latest one they played involved choosing a positive integer and calculating the sum of all the terms from $$$1$$$ up to that integer.
Tony calculated the sum of integers from $$$1$$$ to $$$n$$$ ($$$1 + 2 + \dots + n$$$), while Ben computed the sum of integers from $$$1$$$ to $$$m$$$ ($$$1 + 2 + \dots + m$$$).
A few days later, the two boys recalled their game, but they could no longer remember the values of $$$n$$$ and $$$m$$$, only the difference $$$d$$$ between the two sums they had initially obtained. They also recall that $$$m$$$ was larger than $$$n$$$.
For a given value of $$$d$$$, find all pairs $$$(n, m)$$$.
The only line of input contains the integer $$$d$$$ ($$$2 \leq d \leq 10^{12}$$$).
In the first line print integer $$$s$$$ — the number of pairs. In the next $$$s$$$ lines print all pairs $$$(n,m)$$$. You may print the pairs in any order. Each pair must be printed exactly once, and $$$m \gt n$$$ must hold for all pairs.
Under given constraints, it can be proven that $$$ 1 \leq s \leq 10^4$$$.
5
2 4 5 1 3
9
3 8 9 3 5 1 4
In your current experiments for the Imminently Collapsing Physics Congregation, you are studying the 26 Dark Matter elements. You already found a way to organize a group of their particles in a chain, but unfortunately that sometimes results in the collapse of the whole structure.
Your current theory is that your method is shuffling the particles around randomly, and that the collapse happens if any two particles of the same element are next to each other. To test that theory, you would like to know what is the expected probability of such a collapse, if the theory is correct. That is, out of all possible permutations of the set of particles you're using in your experiment, you would like to know the probability of a uniformly randomly picked permutation to have at least one pair of particles of the same element adjacent to each other.
For example, if you have particles aabbbc, there are 720 possible permutations, with 60 distinct ones if you factor out the order of equal particles. Out of those, only 10 don't cause a collapse:
- ababcb
- abcbab
- bababc
- babacb
- babcab
- babcba
- bacbab
- bcabab
- bcbaba
- cbabab
Input contains a single string $$$S$$$ representing the particles involved in the experiment, $$$1 \leq |S| \le 10^5$$$. Each character of the string is a lowercase letter representing the element of a particle. They are organized in alphabetic order.
Print one integer — the probability of collapse, taken modulo $$$998244353$$$. The required expected probability can be represented as an irreducible fraction $$$\frac{p}{q}$$$. You have to print the value $$$p \cdot q^{-1} \mod 998244353$$$.
aabbbc
831870295
aaab
1
abcdefghijklmnopqrstuvwxyz
0
You thought you wouldn't have to hear about AI today? Well, think again! It's 2023 after all! (Don't worry, you don't need any prior AI expertise — we'll explain all you need to know.)
If you've ever been part of any fringe internet community, I'm sure you've encountered some amount of cat pictures. The way those communities work is simple, the more cat pictures you post, the more popular you are. (Though some communities prefer other animals, like shiba inus or frogs, but the general concept is the same.) But the amount of REAL cat pictures you can post is limited; wouldn't it be great if you could generate cat pictures on demand, just from a text prompt?
Generative AI models such as Stable Diffusion do just that. Today we'll look at a custom version of that, let's call it Cat Diffusion, specifically designed for the generation of cute cat memes.
In Cat Diffusion, each prompt is first converted by a so-called text encoder into a $$$k$$$-dimensional embedding vector of integers $$$(v_1, v_2, \ldots, v_k)$$$. Think of this as a compressed vector containing all the necessary information to reconstruct the sentence's meaning. Sentences that are more alike are closer together; those that are different are further apart. This embedding vector is then passed to a so-called diffusion model, transforming this embedding into a picture.
Example of a few different prompts in a two-dimensional embedding space (not Cat Diffusion); similar sentences stick together. 
The diffusion process, which transforms the embedding vector into an image in many small steps. Conveniently for the AI, Yoda's fingers are cropped from the image. Each of the elements in the embedding vector represents, in some sense, a property; it could represent the type of the cat, or its pose, or the picture's brightness. [In practice, the meaning of those properties is much more abstract and doesn't easily map to real-world concepts; understanding embedding spaces is a huge research topic in machine learning.]
A prompt consists of some number of words. Cat Diffusion uses a very simple text encoder: The $$$i$$$-th word is associated with a certain set of property-value pairs $$$\left \{(p_{i,1}, v_{i,1}), (p_{i,2}, v_{i,2}), \ldots, (p_{i,m_i}, v_{i,m_i}) \right\}$$$. The text encoder now starts with the embedding vector where all properties are set to $$$0$$$; then, it goes left-to-right through the entire prompt, and for the $$$i$$$-th word, for every $$$j \in \{1, \ldots, m_i\}$$$, it sets the $$$p_{i,j}$$$-th property in the embedding vector to $$$v_{i,j}$$$.
You already know what cat picture you want to generate, and what properties it should have. Can you find a prompt that encodes into the exact embedding vector $$$t$$$ that you want, if one exists?
The first line contains two integers $$$k$$$ and $$$w$$$, the dimensionality of the embedding vector (number of properties) and the number of words that you are allowed to use, respectively ($$$1 \leq k, w \leq 100$$$). Each word has a maximum length of $$$15$$$.
The second line contains $$$k$$$ integers $$$t_i$$$, the target embedding for which you're trying to find a prompt ($$$-10^5 \leq t_i \leq 10^5$$$). It is guaranteed that the target embedding has at least one entry which is non-zero.
The $$$i$$$-th of the next $$$w$$$ lines contains information about the $$$i$$$-th word: First is a sequence of lowercase alphabetic characters. Separated by a single space each, next is the number $$$m_i$$$ of property-value pairs associated with the word, followed by $$$m_i$$$ pairs $$$(p_{i, j}, v_{i, j})$$$ ($$$1 \leq m_i \leq k$$$, $$$1 \leq p_{i,j} \leq k$$$, $$$-10^5 \leq v_{i,j} \leq 10^5$$$). It is guaranteed that $$$p_{i, j}$$$ are distinct for any fixed $$$i$$$, and that the words themselves are pairwise distinct.
Note that our indices start at $$$1$$$.
A single line of lowercase alphabetic words in the dictionary separated by single spaces so that its text embedding is $$$t$$$ if such a prompt exists; the string "IMPOSSIBLE" (all uppercase, without quotes) otherwise. If there are multiple valid solutions, it's okay to return any one of them.
3 61 2 1cat 1 1 1dog 1 1 2happy 1 2 1sad 1 2 2jumpy 2 2 1 3 1sleeping 1 3 2
jumpy sad cat
1 23dog 1 1 1frog 1 1 2
IMPOSSIBLE
4 9-3 -1 0 2check 1 4 -4fish 1 4 2hot 2 3 3 2 0establish 2 2 -4 3 3different 2 2 -3 1 -4through 1 1 2nature 1 3 0group 3 3 3 2 -1 4 2involve 3 3 4 4 -3 1 -3
involve group nature fish
Your birthday is approaching and you are expecting a gift from your friend. You don't really care about what gift you receive, but it is important to you how much effort was put into it.
Initially, your friend has some item $$$x$$$. He is not the only one looking for a perfect birthday present. Therefore, he can trade his item for another item, but it takes some effort to do so. As one gift exchange might not be enough to find the perfect gift, this can be done multiple times.
On your birthday you receive item $$$y$$$ as a gift. It is important to you that your friend put in total at least $$$k$$$ effort into the gift exchange. Clearly, it would be considered rude to ask him about his initial item or the gift exchanges he made. In good faith you only want to know if it is possible that your friend put at least $$$k$$$ effort into the gift exchanges.
Each test contains multiple test cases. The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$, the number of test cases. The description of the $$$t$$$ test cases follow.
The first line of each test case contains four integers $$$n, m, k, y$$$ $$$(1 \le n \le 10^5, 0 \leq m \leq 10^5, 1 \leq k \leq 10^9, 1 \le y \le n)$$$, the number of different gifts, the number of possible gift exchanges, the minimum effort you expect to be put into the gift exchange and the gift you receive.
The next $$$m$$$ lines of each test case contain two integers $$$u_i, v_i, e_i$$$ $$$(1 \leq u_i, v_i \leq n, 1 \leq e_i \leq 10^9)$$$, meaning that gift $$$u_i$$$ can be exchanged for gift $$$v_i$$$ with effort $$$e_i$$$. It is guaranteed that $$$u_i \not = v_i$$$ and the ordered pair $$$(u_i, v_i)$$$ does not appear more than once. You are allowed to use the same gift exchange multiple times.
It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all test cases does not exceed $$$10^5$$$ respectively.
For each test case, output "YES" if it is possible that your friend put at least $$$k$$$ effort into the gift exchange and output "NO" otherwise.
25 5 9 45 4 64 1 31 3 73 2 12 1 28 7 7 21 2 13 2 35 3 37 5 27 6 46 4 51 4 2
NO YES
Ken lives on the beach in Barbieland and desperately wants to impress Barbie. One day when Barbie comes over, Ken sees $$$n$$$ drowning swimmers in the sea.
Barbieland is an infinite world where every position is denoted by floating point coordinates $$$(x, y)$$$. Any coordinate with $$$y \lt 0$$$ is sea, and anything else is land. Ken is initially at $$$(x_{\text{ken}}, y_{\text{ken}})$$$. There is also an ice cream stand at $$$(x_{\text{icecream}}, y_{\text{icecream}})$$$.
Ken's movement speed per second in units is capped by $$$v_{\text{run}}$$$ on land, and $$$v_{\text{swim}}$$$ on sea ($$$v_{\text{run}} \geq v_{\text{swim}}$$$).
To impress Barbie, Ken wants to save several drowning people. All of their $$$y$$$-coordinates are negative and they don't move, unless carried by Ken. Because there is no death in Barbieland, all he has to do is bring everyone to the ice cream stand to save them.
To carry a drowning person, Ken just has to swim to them. He can only drop them off at the ice cream stand, but thankfully, our hero has been hitting the gym, so he can carry $$$s$$$ ($$$1 \leq s \leq n$$$) swimmers simultaneously.
Can you help Ken save everyone as quickly as possible and bring everyone to the ice cream stand? Make sure to take a look at the comic below, which demonstrates that the most obvious solution may not be the fastest.
"Of course you get an ice cream cone for the swimmer too! You're not a monster." (xkcd 2821) The first line contains two integers, Ken's coordinates $$$(x_{\text{ken}}, y_{\text{ken}})$$$ ($$$-10^6 \leq x_{\text{ken}} \leq 10^6$$$, $$$0 \leq y_{\text{ken}} \leq 10^6$$$).
The second line contains two integers, the coordinates of the ice cream stand $$$(x_{\text{icecream}}, y_{\text{icecream}})$$$ ($$$-10^6 \leq x_{\text{icecream}} \leq 10^6$$$, $$$0 \leq y_{\text{icecream}} \leq 10^6$$$).
The third line contains two integers, Ken's running and swimming speeds $$$v_{\text{run}}$$$ and $$$v_{\text{swim}}$$$, respectively, both in units per second ($$$1 \leq v_{\text{swim}} \leq v_{\text{run}} \leq 100$$$).
The fourth line contains two integers, the number $$$n$$$ of drowning swimmers Ken has to save ($$$1 \leq n \leq 15$$$), and his strength $$$s$$$ ($$$1 \leq s \leq n$$$).
The next $$$n$$$ lines contain two integers each, the coordinates $$$(x_i, y_i)$$$ of the $$$i$$$-th drowning person ($$$-10^6 \leq x_{i} \leq 10^6$$$, $$$-10^6 \leq y_{i} \lt 0$$$).
Output a single floating point number in decimal format, the time in seconds that Ken needs to save everyone. The result will be accepted as long as the absolute or relative error is at most $$$10^{-6}$$$.
-2 23 32 11 12 -1
5.7036530240
0 00 01 14 3-4 -2-2 -42 -44 -2
23.5453980697
7 3100 14100 38 219 -250 -34164 -128000 -613-34 -4-976 -115-10780 -33-10780 -34
940.2817219035
The first example is the set up in the comic above. There is only one swimmer drowning at $$$(2, -1)$$$ that we reach by running to $$$(\sim1.52, 0)$$$ and swimming to $$$(2, -1)$$$. Then, to get back to the ice cream stand, we swim to $$$(\sim2.14, 0)$$$ and run to $$$(3, 3)$$$.
In the second example, Ken starts at the ice cream stand, and swims as fast as he runs.