Enrique and Yan frequently play a game called 1D Scrabble. The game is played on a one-dimensional, infinite board using a fixed dictionary of unique words. On the first turn ($$$i = 1$$$), any word $$$w_1$$$ from the dictionary may be played. On every subsequent turn ($$$i \gt 1$$$), the played word $$$w_i$$$ must contain the previous word $$$w_{i-1}$$$ as a contiguous substring. The game concludes as soon as no valid moves remain.
Recently, Yan did not have time to play, so Enrique started playing with GePeTo. However, GePeTo started hallucinating! It consistently states that this game is trivial, arguing that there are very few combinations. Help Enrique convince GePeTo by calculating the total number of distinct possible games. Two games are distinct if their sequences of played words $$$(w_1, \ldots, w_k)$$$ are different.
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), the number of words.
Each of the next $$$N$$$ lines contains a word $$$w$$$ consisting of lowercase English letters. It is guaranteed that all words are unique and the sum of lengths of all words does not exceed $$$10^5$$$.
Print a single integer: the number of distinct possible games modulo $$$10^9+7$$$.
3maramaratonatona
3
3aaaaaa
4
5aababcbcc
7
In order to teach people empathy, GePeTo demands that people often change houses, so that they learn to "live in another's shoes". There are $$$N$$$ houses in the city, each housing one person, and on the $$$i$$$-th house GePeTo placed the label $$$\pi(i)$$$ meaning that, every day at midnight, the person living in house $$$i$$$ has to move to house $$$\pi(i)$$$. All people move at the same time, and it is guaranteed that after a move no house is left empty, and no house has two people.
We say $$$\pi$$$ has a cycle of size $$$k$$$ if, after $$$k$$$ days, some person returns to the house where they initially lived, that is, if $$$\pi^k(x) = x$$$ for some $$$1 \leq x \leq N$$$.
GePeTo asks you to swap the labels of two houses in order to maximize the size of the smallest cycle, that is, choose a single pair $$$(i, j)$$$ and swap $$$\pi(i)$$$ with $$$\pi(j)$$$ to maximize the minimum $$$k$$$ such that $$$\pi^k(x) = x$$$ for some $$$1 \leq x \leq N$$$. You are allowed to choose $$$j = i$$$, in which case $$$\pi$$$ remains unchanged.
The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$), the number of test cases.
Each test case consists of two lines. The first line contains an integer $$$N$$$ ($$$2 \leq N \leq 2 \cdot 10^5$$$), the number of houses. The second line contains $$$N$$$ distinct integers between $$$1$$$ and $$$N$$$, the $$$i$$$-th being $$$\pi(i)$$$. The sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print a line with three integers $$$k$$$, $$$i$$$, and $$$j$$$ ($$$1 \leq k, i, j \leq N$$$), such that the maximum size of the minimum cycle is $$$k$$$ after swapping positions $$$i$$$ and $$$j$$$. If there are multiple answers, any valid answer will be accepted.
342 3 4 143 4 1 273 5 1 7 2 4 6
4 1 14 1 23 1 2
As GePeTo assimilates all data on the internet, they are looking for a way to compress that data so it occupies less space. For this purpose, they came up with the following compression algorithm.
Given a string $$$s$$$ containing lowercase English letters, each maximal consecutive repetition of a letter $$$c$$$ must be replaced by $$$c$$$ followed by $$$n$$$, where $$$n$$$ is the number of repetitions of that letter. If the letter is repeated just once, then it should not be replaced by $$$c1$$$, as that would increase the size of the string.
As an example, consider the string "zzzabbc". Since the letter 'z' is repeated three times consecutively and 'b' twice, the result of the compression is "z3ab2c".
Your task is to implement this algorithm.
The first line contains a single string $$$s$$$ ($$$1 \leq |s| \leq 1000$$$) consisting of lowercase English letters, from 'a' to 'z'.
Print the result of the compression of $$$s$$$.
abccccaax
abc4a2x
zzzabbc
z3ab2c
aaaaaaaaaa
a10
After learning all competitive programming problems, GePeTo is now studying all board games in the world, and is particularly interested in a copy of Escape it found in your room.
In Escape, you have 5 identical six-sided dice, with the following faces:
- 2 Adventurer faces (A)
- 1 Torch face (T)
- 1 Key face (C)
- 1 Black Mask face (N)
- 1 Golden Mask face (D)
In an important part of the game, you are given an objective, which is a multiset of up to 5 symbols selected from ATC. Your goal is to roll the dice and finish with their top faces showing at least the symbols required by the objective.
Starting from an initial roll of the 5 dice, you have a maximum of $$$K$$$ turns (rerolls) to achieve the objective. In each turn, you select a subset of the current dice and reroll them, subject to the following rules:
- A die showing the Black Mask face (N) becomes locked and cannot be selected for rerolling.
- For each rerolled die that is currently showing the Golden Mask face (D), you gain the right to simultaneously unlock and reroll up to 2 locked dice.
Assuming you play optimally, that is, making decisions each turn that maximize the probability of achieving the objective within $$$K$$$ turns, answer the following: What is the maximum probability of success, and what is an optimal first reroll?
The first line contains a single string $$$O$$$ consisting of characters from ATC, representing the objective. ($$$1 \leq |O| \leq 5$$$)
The second line contains an integer $$$T$$$, the number of test cases. ($$$1 \leq T \leq 10^4$$$)
Each of the next $$$T$$$ lines contains a string $$$S$$$ of exactly five characters from ATCND, representing your initial roll, and an integer $$$K$$$, the maximum number of rerolls you can perform. ($$$1 \leq K \leq 5$$$)
For each test case, print a string $$$R$$$ and a number $$$P$$$.
$$$R$$$ should be nonempty and contain up to five characters from ATCND, representing the dice that should be rerolled. It is guaranteed that the objective is not met initially, at least one reroll is possible, and the probability of winning is strictly positive (i.e., $$$P \gt 0$$$). The characters may be printed in any order.
The number $$$P$$$ should be the maximum probability of achieving the objective when playing optimally. The answer is considered correct if the absolute error does not exceed $$$10^{-4}$$$.
T4NNNNA 1NNNAA 1NNNNA 2AAAAA 1
A 0.1666666667 AA 0.3055555556 A 0.3202160494 AAAAA 0.5981224280
ATC4NTNAN 2TNCNT 1NTADD 1AATDT 5
AT 0.0543981481 T 0.3333333333 NDD 0.4212962963 AAT 0.9121533206
Here is an example of the game:
- Suppose the objective is $$$O = \texttt{ATT}$$$ (meaning we need at least 1 Adventurer and 2 Torches).
- Your initial roll is $$$S = \texttt{ANNCC}$$$ (1 Adventurer, 2 locked Black Masks and 2 Keys).
- On your first reroll, you decide to reroll both Keys (CC), since you can't reroll any Black Masks. Suppose the rerolled dice land on AD, meaning you now have AANND.
- Now, on your second reroll, you decide to reroll an Adventurer and the Golden Mask, and since you are rerolling the Golden Mask, you gain the right to reroll up to two locked Black Masks. In total, you reroll 4 dice (ADNN).
- Suppose the rerolled dice land on TTNC, meaning the final dice configuration becomes ATTNC (which contains at least 1 A and 2 T's), successfully meeting the objective with two rerolls.
Renzo has a top-secret plan for finally overthrowing the evil reign of GePeTo. In order to execute his plan, Renzo needs you to distract the overlord.
As you may already know, there are some tasks that AIs struggle to accomplish, and GePeTo is no exception. It is well known that AIs are not good at counting letters, for instance. Also, some specific prompts, such as asking for the seahorse emoji, drive AIs crazy. But there is one task GePeTo struggles with the most: computing Grundy numbers.
Let $$$A$$$ be a sequence of $$$2^n$$$ numbers. For each $$$i$$$ ($$$0 \leq i \leq 2^n - 1$$$), define the Grundy number $$$$$$ g_A(i) = \operatorname{mex}(\{g_A(j) : j \lt i \text{ and } A_i \oplus A_j \text{ is a power of two}\}), $$$$$$ where $$$\oplus$$$ denotes the bitwise XOR operation, and $$$\operatorname{mex}(S)$$$ is the minimum non-negative integer that is not contained in $$$S$$$.
As an example, consider the sequence $$$$$$ A = (0, 3, 1, 2) $$$$$$ and its corresponding Grundy numbers $$$$$$ g_A = (0, 0, 1, 1). $$$$$$
Your task is to find a permutation $$$P$$$ of the numbers from $$$0$$$ to $$$2^n - 1$$$ that maximizes the maximum Grundy number, so that GePeTo will spend a lot of time trying to compute them. Formally, the permutation $$$P$$$ must maximize $$$$$$ \max_{0 \leq i \leq 2^n - 1}\{g_P(i)\} $$$$$$ among all permutations of the numbers from $$$0$$$ to $$$2^n - 1$$$.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 20$$$).
On the first line, print the maximum achievable Grundy number.
On the second line, print $$$2^n$$$ space-separated integers, representing any permutation of the numbers from $$$0$$$ to $$$2^n - 1$$$ that achieves this Grundy number. If there are multiple such permutations, any of them will be accepted.
1
1 0 1
2
1 0 3 1 2
After GePeTo assumed control of the surface, the last members of the resistance were forced to hide underground.
To protect themselves from the robots, they built a network of tunnels connecting $$$N$$$ underground points. The network was designed without redundant paths: between any two points, there is exactly one possible path.
The resistance's shelters are located at the extremities of this network, that is, at the vertices that have only one tunnel connected to them (the leaves of the tree).
To plan communication between the shelters, the resistance needs to answer $$$Q$$$ queries. In each query, given an integer $$$X$$$, determine how many pairs of shelters are separated by exactly $$$X$$$ tunnels.
The first line contains two integers $$$N$$$ ($$$2 \leq N \leq 2 \cdot 10^5$$$) and $$$Q$$$ ($$$1 \leq Q \leq 10$$$), representing the number of points in the network and the number of queries, respectively.
Each of the next $$$N-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq N$$$), indicating that there is a tunnel directly connecting vertices $$$u$$$ and $$$v$$$. It is guaranteed that the given connections form a tree.
Each of the next $$$Q$$$ lines contains a single integer $$$X$$$ ($$$1 \leq X \leq N-1$$$), representing the query distance.
For each query, print a single integer: the number of unordered pairs of distinct shelters $$$(u, v)$$$ whose distance is exactly $$$X$$$.
2 11 21
1
6 51 22 32 44 51 612345
0 0 2 1 0
Lately, GePeTo has developed a fascination with the digit $$$4$$$, declaring it the most elegant digit in existence. To prove your mathematical prowess, GePeTo challenges you to the classic "Four Fours" puzzle.
Given a non-negative integer target $$$X$$$, your goal is to construct a mathematical expression that evaluates to $$$X$$$ using **exactly four** digits 4 and any combination of the following allowed operators and notation:
- Basic arithmetic: +, -, *, /
- Exponentiation: ^{}
- Parentheses: ()
- Decimal point: . (e.g., .4 for $$$0.4$$$, 4.4)
- Square root: sqrt
- Factorial: !
Some examples of valid expressions:
- 5 = (4 * 4 + 4) / 4
- 14 = 4 * (4 - .4) - .4
- 22 = 44 / 4 * sqrt(4)
- 27 = 4 - 4/4 + 4!
- 60 = (4 + 4)^sqrt(4) - 4
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 50$$$), the number of test cases.
Each of the next $$$T$$$ lines contains an integer $$$X$$$ ($$$0 \leq X \leq 70$$$).
For each test case, print a single line containing a valid expression using exactly four 4's that evaluates to $$$X$$$. The expression must have at most 25 characters. If multiple valid expressions exist, any of them will be accepted.
The expression must be well-behaved:
- The factorial operator ! may only be applied to non-negative integers.
- The square root operator sqrt may only be applied to non-negative integers and must yield an integer result.
- Any exponentiation must use an integer exponent.
- The numerator and denominator of any intermediate rational value may never exceed $$$10^9$$$.
65142227600
((44 - 4!) / 4) 4.4 + (.4 * 4!) 4! - (4 + 4) / 4 4 - (4/4 - 4!) (4 + 4)^sqrt(4) - 4 44-44
After the silicon reserves ended on Earth, in order to produce more chips, GePeTo discovered a new mineral, called Teotonium, on Mars. As GePeTo is busy writing some poetry about the meaning of life, they asked you to deal with the technical details of the excavation.
The $$$N$$$ deposits of Teotonium are placed in a line, and the $$$i$$$-th deposit has $$$A_i$$$ tons of Teotonium. The Teotonium miners work in an odd manner: each has a gap number $$$M$$$ and, after mining all Teotonium in deposit $$$i$$$, it can mine either deposit $$$i+M$$$ or $$$i-M$$$, and repeat. That is, it can only mine deposits $$$j$$$ such that $$$j \equiv i \pmod M$$$.
Your task is to answer $$$Q$$$ queries given by $$$L$$$, $$$R$$$, $$$X$$$, and $$$M$$$, in which you must determine the total Teotonium in all deposits with index $$$i$$$ such that $$$L \leq i \leq R$$$ and $$$i \equiv X \pmod M$$$.
The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N, Q \leq 2 \cdot 10^5$$$).
The second line contains $$$N$$$ integers $$$A_1, \ldots, A_N$$$ ($$$0 \leq A_i \leq 10^9$$$).
Each of the next $$$Q$$$ lines contains four integers $$$L$$$, $$$R$$$, $$$X$$$, and $$$M$$$ ($$$1 \leq L \leq R \leq N$$$, $$$0 \leq X \lt M \leq N+1$$$).
Output $$$Q$$$ integers, the answer to each query.
5 41 4 0 10 51 5 0 11 5 1 22 5 1 23 4 0 5
20 6 5 0
GePeTo has assumed control of practically all machines on the planet. During a resistance mission, your team was cornered by an army of robots and the only option to escape is to use an old combat spaceship.
Viewed from above, the spaceship is shaped like a convex polygon. The robots are represented by points in the plane and are all initially outside the spaceship.
The navigation systems have been damaged: before departing, it is possible to choose only one direction, and then the spaceship will follow this direction indefinitely, without making turns or rotations.
A robot is destroyed if the spaceship passes over its position at any point during its movement. Positions on the boundary of the spaceship are also considered hit.
Determine the maximum number of robots that can be destroyed by choosing the spaceship's direction of movement optimally.
The first line contains a single integer $$$N$$$ ($$$3 \leq N \leq 2 \cdot 10^5$$$), the number of vertices of the polygon representing the spaceship.
Each of the next $$$N$$$ lines contains two integers $$$x_u$$$ and $$$y_u$$$ ($$$-2 \cdot 10^9 \leq x_u, y_u \leq 2 \cdot 10^9$$$), representing the coordinates of the $$$u$$$-th vertex of the spaceship. The vertices are given in counter-clockwise order and form a convex polygon.
The next line contains a single integer $$$M$$$ ($$$1 \leq M \leq 2 \cdot 10^5$$$), the number of robots.
Each of the next $$$M$$$ lines contains two integers $$$x_v$$$ and $$$y_v$$$ ($$$-2 \cdot 10^9 \leq x_v, y_v \leq 2 \cdot 10^9$$$), representing the position of the $$$v$$$-th robot.
It is guaranteed that all robots are initially outside the spaceship's polygon.
Print a single integer: the maximum number of robots that can be destroyed by choosing a direction of movement.
40 05 05 50 5615 1520 1520 1220 10-15 00 20
4
The spaceship can choose any non-zero direction in the plane.
Throughout the movement, its shape and orientation remain unchanged: all of its points move by the same distance and in the same direction.
A robot is considered destroyed if, at some instant, its position is inside or on the boundary of the polygon occupied by the spaceship.
In order to obtain more food tokens, you plan to present the GePeTo overlord with an array of numbers $$$A$$$. As they were trained on more even numbers than odd numbers, GePeTo prefers even numbers, so you want to change some numbers in $$$A$$$ to maximize the number of even numbers.
Since you are already the first in line, you only have time to apply a single operation to $$$A$$$: pick a number $$$X$$$ and a range $$$[L,R]$$$ and add $$$X$$$ to elements $$$A_L, \ldots, A_R$$$. After performing this operation exactly once, what is the maximum possible number of even numbers in $$$A$$$?
The first line contains an integer $$$N$$$. ($$$1 \leq N \leq 2 \cdot 10^3$$$)
The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$, where $$$1 \leq A_i \leq 1000$$$.
You may choose any integer $$$X$$$ ($$$1 \leq X \leq 1000$$$) and any range $$$1 \leq L \leq R \leq N$$$. You must perform the operation exactly once.
Print a single integer $$$E$$$, the maximum possible number of even numbers in the array after the operation.
31 2 3
2
141 2 2 1 1 1 2 1 1 2 2 2 1 1
10
11000
1
After the city he lives in was devastated by the overlord GePeTo, Pedro needs to escape to a survivors' shelter, but the only exit available is through the subway.
Unfortunately, he has no money to pay for the fare. However, he notices that there is a special property in the turnstile, which displays a number $$$C$$$ representing the number of times someone has passed through it: the turnstile allows free passage if all digits of $$$C$$$ are distinct!
Each person passing through the turnstile increases the counter $$$C$$$ by $$$1$$$. Given the number $$$C$$$ currently displayed by the turnstile, determine the minimum number of people that need to pass through it so that Pedro can finally pass for free and escape the city.
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$), the number of test cases.
Each of the next $$$T$$$ lines contains a single integer $$$C$$$ ($$$1 \leq C \leq 10^{10}$$$), representing the current number displayed by the turnstile.
For each test case, print a single line containing the integer $$$P$$$. If it is impossible to reach a state where all digits are distinct, print $$$-1$$$.
319910000000000
03-1
After studying all competitive programming problems ever created, GePeTo became a superpowerful artificial intelligence. Now, to begin its plan for world domination, it is creating thousands of copies of its agents.
Each agent has an identification code. However, due to a flaw in the production system, different agents can receive the same code.
The agents are organized in a sequence $$$A$$$ of $$$N$$$ positions, where $$$A_i$$$ represents the code of the agent at position $$$i$$$.
Your mission is to find how many pairs of agents have the same code. In other words, determine the number of index pairs $$$(i, j)$$$ such that: $$$$$$ 1 \leq i \lt j \leq N \quad \text{and} \quad A_i = A_j $$$$$$
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$), the number of agents.
The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \leq A_i \leq 10^9$$$) separated by spaces, representing the codes of the agents.
Print a single integer: the number of index pairs $$$(i, j)$$$ that have the same code.
31 2 3
0
61 2 3 1 2 1
4