Vlad went into his appartment house entrance, now he is on the $$$1$$$-th floor. He was going to call the elevator to go up to his apartment.
There are only two elevators in his house. Vlad knows for sure that:
- the first elevator is currently on the floor $$$a$$$ (it is currently motionless),
- the second elevator is located on floor $$$b$$$ and goes to floor $$$c$$$ ($$$b \ne c$$$). Please note, if $$$b=1$$$, then the elevator is already leaving the floor $$$1$$$ and Vlad does not have time to enter it.
If you call the first elevator, it will immediately start to go to the floor $$$1$$$. If you call the second one, then first it will reach the floor $$$c$$$ and only then it will go to the floor $$$1$$$. It takes $$$|x - y|$$$ seconds for each elevator to move from floor $$$x$$$ to floor $$$y$$$.
Vlad wants to call an elevator that will come to him faster. Help him choose such an elevator.
The first line of the input contains the only $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
This is followed by $$$t$$$ lines, three integers each $$$a$$$, $$$b$$$ and $$$c$$$ ($$$1 \le a, b, c \le 10^8$$$, $$$b \ne c$$$) — floor numbers described in the statement.
Output $$$t$$$ numbers, each of which is the answer to the corresponding test case. As an answer, output:
- $$$1$$$, if it is better to call the first elevator;
- $$$2$$$, if it is better to call the second one;
- $$$3$$$, if it doesn't matter which elevator to call (both elevators will arrive in the same time).
31 2 33 1 23 2 1
1 3 2
In the first test case of the example, the first elevator is already on the floor of $$$1$$$.
In the second test case of the example, when called, the elevators would move as follows:
- At the time of the call, the first elevator is on the floor of $$$3$$$, and the second one is on the floor of $$$1$$$, but is already going to another floor;
- in $$$1$$$ second after the call, the first elevator would be on the floor $$$2$$$, the second one would also reach the floor $$$2$$$ and now can go to the floor $$$1$$$;
- in $$$2$$$ seconds, any elevator would reach the floor $$$1$$$.
In the third test case of the example, the first elevator will arrive in $$$2$$$ seconds, and the second in $$$1$$$.
Polycarp has a string $$$s$$$ consisting of lowercase Latin letters.
He encodes it using the following algorithm.
He goes through the letters of the string $$$s$$$ from left to right and for each letter Polycarp considers its number in the alphabet:
- if the letter number is single-digit number (less than $$$10$$$), then just writes it out;
- if the letter number is a two-digit number (greater than or equal to $$$10$$$), then it writes it out and adds the number 0 after.
For example, if the string $$$s$$$ is code, then Polycarp will encode this string as follows:
- 'c' — is the $$$3$$$-rd letter of the alphabet. Consequently, Polycarp adds 3 to the code (the code becomes equal to 3);
- 'o' — is the $$$15$$$-th letter of the alphabet. Consequently, Polycarp adds 15 to the code and also 0 (the code becomes 3150);
- 'd' — is the $$$4$$$-th letter of the alphabet. Consequently, Polycarp adds 4 to the code (the code becomes 31504);
- 'e' — is the $$$5$$$-th letter of the alphabet. Therefore, Polycarp adds 5 to the code (the code becomes 315045).
Thus, code of string code is 315045.
You are given a string $$$t$$$ resulting from encoding the string $$$s$$$. Your task is to decode it (get the original string $$$s$$$ by $$$t$$$).
The first line of the input contains an integer $$$q$$$ ($$$1 \le q \le 10^4$$$) — the number of test cases in the input.
The descriptions of the test cases follow.
The first line of description of each test case contains one integer $$$n$$$ ($$$1 \le n \le 50$$$) — the length of the given code.
The second line of the description of each test case contains a string $$$t$$$ of length $$$n$$$ — the given code. It is guaranteed that there exists such a string of lowercase Latin letters, as a result of encoding which the string $$$t$$$ is obtained.
For each test case output the required string $$$s$$$ — the string that gives string $$$t$$$ as the result of encoding. It is guaranteed that such a string always exists. It can be shown that such a string is always unique.
963150454110071213121612012018315045615018035190711111107111110051111142606
code aj abacaba ll codeforces aaaak aaaaj aaaaa zf
The first test case is explained above.
In the second test case, the answer is aj. Indeed, the number of the letter a is equal to $$$1$$$, so 1 will be appended to the code. The number of the letter j is $$$10$$$, so 100 will be appended to the code. The resulting code is 1100.
There are no zeros in the third test case, which means that the numbers of all letters are less than $$$10$$$ and are encoded as one digit. The original string is abacaba.
In the fourth test case, the string $$$s$$$ is equal to ll. The letter l has the number $$$12$$$ and is encoded as 120. So ll is indeed 120120.
Polycarp was given a row of tiles. Each tile contains one lowercase letter of the Latin alphabet. The entire sequence of tiles forms the string $$$s$$$.
In other words, you are given a string $$$s$$$ consisting of lowercase Latin letters.
Initially, Polycarp is on the first tile of the row and wants to get to the last tile by jumping on the tiles. Jumping from $$$i$$$-th tile to $$$j$$$-th tile has a cost equal to $$$|index(s_i) - index(s_j)|$$$, where $$$index(c)$$$ is the index of the letter $$$c$$$ in the alphabet (for example, $$$index($$$'a'$$$)=1$$$, $$$index($$$'b'$$$)=2$$$, ..., $$$index($$$'z'$$$)=26$$$) .
Polycarp wants to get to the $$$n$$$-th tile for the minimum total cost, but at the same time make maximum number of jumps.
In other words, among all possible ways to get to the last tile for the minimum total cost, he will choose the one with the maximum number of jumps.
Polycarp can visit each tile at most once.
Polycarp asks you to help — print the sequence of indices of string $$$s$$$ on which he should jump.
The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.
Each test case is given by the string $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$), where $$$|s|$$$ — is the length of string $$$s$$$. The string $$$s$$$ consists of lowercase Latin letters.
It is guaranteed that the sum of string lengths $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
The answer to each test case consists of two lines.
In the first line print two integers $$$cost$$$, $$$m$$$, where $$$cost$$$ is the minimum total cost of the path, and $$$m$$$ is the maximum number of visited tiles Polycarp can make to get to $$$n$$$-th tiles for the minimum total cost $$$cost$$$ (i.e. the number of jumps is $$$m-1$$$).
In the next line print $$$m$$$ different numbers $$$j_1, j_2, \dots, j_m$$$ ($$$1 \le j_i \le |s|$$$) — the sequence of indices of the tiles Polycarp will jump on. The first number in the sequence must be $$$1$$$ (that is, $$$j_1=1$$$) and the last number must be the value of $$$|s|$$$ (that is, $$$j_m=|s|$$$).
If there are multiple answers, print any of them.
6logiccodeforcesbcaaaaaaaaaaaaadbaadabadto
9 4 1 4 3 5 16 10 1 8 3 4 9 5 2 6 7 10 1 2 1 3 0 11 1 8 10 4 3 5 7 2 9 6 11 3 10 1 9 5 4 7 3 8 6 2 10 5 2 1 2
In the first test case, the required path corresponds to the picture:
In this case, the minimum possible total cost of the path is achieved. Since $$$index($$$'l'$$$)=12$$$, $$$index($$$'o'$$$)=15$$$, $$$index($$$'g'$$$)=7$$$, $$$index($$$'i'$$$)=9$$$, $$$index($$$'c'$$$)=3$$$, then the total cost of the path is $$$|12-9|+|9-7|+|7-3|=3+2+4=9$$$.
A group of $$$n$$$ friends decide to go to a restaurant. Each of the friends plans to order meals for $$$x_i$$$ burles and has a total of $$$y_i$$$ burles ($$$1 \le i \le n$$$).
The friends decide to split their visit to the restaurant into several days. Each day, some group of at least two friends goes to the restaurant. Each of the friends visits the restaurant no more than once (that is, these groups do not intersect). These groups must satisfy the condition that the total budget of each group must be not less than the amount of burles that the friends in the group are going to spend at the restaurant. In other words, the sum of all $$$x_i$$$ values in the group must not exceed the sum of $$$y_i$$$ values in the group.
What is the maximum number of days friends can visit the restaurant?
For example, let there be $$$n = 6$$$ friends for whom $$$x$$$ = [$$$8, 3, 9, 2, 4, 5$$$] and $$$y$$$ = [$$$5, 3, 1, 4, 5, 10$$$]. Then:
- first and sixth friends can go to the restaurant on the first day. They will spend $$$8+5=13$$$ burles at the restaurant, and their total budget is $$$5+10=15$$$ burles. Since $$$15 \ge 13$$$, they can actually form a group.
- friends with indices $$$2, 4, 5$$$ can form a second group. They will spend $$$3+2+4=9$$$ burles at the restaurant, and their total budget will be $$$3+4+5=12$$$ burles ($$$12 \ge 9$$$).
It can be shown that they will not be able to form more groups so that each group has at least two friends and each group can pay the bill.
So, the maximum number of groups the friends can split into is $$$2$$$. Friends will visit the restaurant for a maximum of two days. Note that the $$$3$$$-rd friend will not visit the restaurant at all.
Output the maximum number of days the friends can visit the restaurant for given $$$n$$$, $$$x$$$ and $$$y$$$.
The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.
The descriptions of the test cases follow.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of friends.
The second line of each test case contains exactly $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le 10^9$$$). The value of $$$x_i$$$ corresponds to the number of burles that the friend numbered $$$i$$$ plans to spend at the restaurant.
The third line of each test case contains exactly $$$n$$$ integers $$$y_1, y_2, \dots, y_n$$$ ($$$1 \le y_i \le 10^9$$$). The value $$$y_i$$$ corresponds to the number of burles that the friend numbered $$$i$$$ has.
It is guaranteed that the sum of $$$n$$$ values over all test cases does not exceed $$$10^5$$$.
For each test case, print the maximum number of days to visit the restaurant. If friends cannot form even one group to visit the restaurant, print 0.
668 3 9 2 4 55 3 1 4 5 1041 2 3 41 1 2 232 3 71 3 1062 3 6 9 5 73 2 7 10 6 1065 4 2 1 8 1001 1 1 1 1 20061 4 1 2 4 21 3 3 2 3 4
2 0 1 3 1 3
The first test case in explained in the problem statement.
In the second test case, friends cannot form at least one group of two or more people.
In the third test case, one way to visit the restaurant in one day is to go in a group of all three friends ($$$1+3+10 \ge 2+3+7$$$). Note that they do not have the option of splitting into two groups.
This is an interactive problem.
I want to play a game with you...
We hid from you a cyclic graph of $$$n$$$ vertices ($$$3 \le n \le 10^{18}$$$). A cyclic graph is an undirected graph of $$$n$$$ vertices that form one cycle. Each vertex belongs to the cycle, i.e. the length of the cycle (the number of edges in it) is exactly $$$n$$$. The order of the vertices in the cycle is arbitrary.
You can make queries in the following way:
- "? a b" where $$$1 \le a, b \le 10^{18}$$$ and $$$a \neq b$$$. In response to the query, the interactor outputs on a separate line the length of random of two paths from vertex $$$a$$$ to vertex $$$b$$$, or -1 if $$$\max(a, b) \gt n$$$. The interactor chooses one of the two paths with equal probability. The length of the path —is the number of edges in it.
You win if you guess the number of vertices in the hidden graph (number $$$n$$$) by making no more than $$$50$$$ queries.
Note that the interactor is implemented in such a way that for any ordered pair $$$(a, b)$$$, it always returns the same value for query "? a b", no matter how many such queries. Note that the "? b a" query may be answered differently by the interactor.
The vertices in the graph are randomly placed, and their positions are fixed in advance.
Hacks are forbidden in this problem. The number of tests the jury has is $$$50$$$.
You can make no more than $$$50$$$ of queries. To make a query, output on a separate line:
- "? a b", where $$$1 \le a, b \le 10^{18}$$$ and $$$a \neq b$$$. In response to the query, the interactor will output on a separate line the length of a random simple path from vertex $$$a$$$ to vertex $$$b$$$ (not to be confused with the path from $$$b$$$ to $$$a$$$), or $$$-1$$$ if $$$\max(a, b) \gt n$$$. The interactor chooses one of the two paths with equal probability.
If your program gets a number 0 as a result of a query, it means that the verdict for your solution is already defined as "wrong answer" (for example, you made more than $$$50$$$ queries or made an invalid query). In this case, your program should terminate immediately. Otherwise, in this scenario you may get a random verdict "Execution error", "Exceeded time limit" or some other verdict instead of "Wrong answer".
The answer, like queries, print on a separate line. The output of the answer is not counted as a query when counting them. To print it, use the following format:
- "! n": the expected size of the hidden graph ($$$3 \le n \le 10^{18}$$$).
After that, your program should terminate.
After the output of the next query, be sure to use stream cleaning functions so that some of your output is not left in some buffer. For example, in C++ you should use function flush(stdout), in Java call System.out.flush(), in Pascal flush(output) and stdout.flush() for Python.
Note that the interactor is implemented in such a way that for any ordered pair $$$(a, b)$$$, it always returns the same value for query "? a b", no matter how many such queries. Note that the "? b a" query may be answered differently by the interactor.
The vertices in the graph are randomly placed, and their positions are fixed in advance.
Hacks are forbidden in this problem. The number of tests the jury has is $$$50$$$.
1 2 -1
? 1 2 ? 1 3 ? 1 4 ! 3
In the first example, the graph could look like this
The lengths of the simple paths between all pairs of vertices in this case are $$$1$$$ or $$$2$$$.
- The first query finds out that one of the simple paths from vertex $$$1$$$ to vertex $$$2$$$ has a length of $$$1$$$.
- With the second query, we find out that one of the simple paths from vertex $$$1$$$ to vertex $$$3$$$ has length $$$2$$$.
- In the third query, we find out that vertex $$$4$$$ is not in the graph. Consequently, the size of the graph is $$$3$$$.
Given the string $$$s$$$ of decimal digits (0-9) of length $$$n$$$.
A substring is a sequence of consecutive characters of a string. The substring of this string is defined by a pair of indexes — with its left and right ends. So, each pair of indexes ($$$l, r$$$), where $$$1 \le l \le r \le n$$$, corresponds to a substring of the string $$$s$$$. We will define as $$$v(l,r)$$$ the numeric value of the corresponding substring (leading zeros are allowed in it).
For example, if $$$n=7$$$, $$$s=$$$"1003004", then $$$v(1,3)=100$$$, $$$v(2,3)=0$$$ and $$$v(2,7)=3004$$$.
You are given $$$n$$$, $$$s$$$ and an integer $$$w$$$ ($$$1 \le w \lt n$$$).
You need to process $$$m$$$ queries, each of which is characterized by $$$3$$$ numbers $$$l_i, r_i, k_i$$$ ($$$1 \le l_i \le r_i \le n; 0 \le k_i \le 8$$$).
The answer to the $$$i$$$th query is such a pair of substrings of length $$$w$$$ that if we denote them as $$$(L_1, L_1+w-1)$$$ and $$$(L_2, L_2+w-1)$$$, then:
- $$$L_1 \ne L_2$$$, that is, the substrings are different;
- the remainder of dividing a number $$$v(L_1, L_1+w-1) \cdot v(l_i, r_i) + v(L_2, L_2 + w - 1)$$$ by $$$9$$$ is equal to $$$k_i$$$.
If there are many matching substring pairs, then find a pair where $$$L_1$$$ is as small as possible. If there are many matching pairs in this case, then minimize $$$L_2$$$.
Note that the answer may not exist.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — number of input test cases.
The first line of each test case contains a string $$$s$$$, which contains only the characters 0-9 and has a length $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).
The second line contains two integers $$$w, m$$$ ($$$1 \le w \lt n, 1 \le m \le 2 \cdot 10^5$$$), where $$$n$$$ — is the length of the given string $$$s$$$. The number $$$w$$$ denotes the lengths of the substrings being searched for, and $$$m$$$ is the number of queries to be processed.
The following $$$m$$$ lines contain integers $$$l_i, r_i, k_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$0 \le k_i \le 8$$$) — $$$i$$$th query parameters.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. It is also guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each request, print in a separate line:
- left borders of the required substrings: $$$L_1$$$ and $$$L_2$$$;
- -1 -1 otherwise, if there is no solution.
If there are several solutions, minimize $$$L_1$$$ first, and minimize $$$L_2$$$ second.
510030044 11 2 11795720074 22 7 32 7 41112 12 2 600001 21 4 01 4 14841 52 2 02 3 71 2 53 3 82 2 6
2 4 1 5 1 2 -1 -1 1 2 -1 -1 1 3 1 3 -1 -1 -1 -1 -1 -1
Consider the first test case of example inputs. In this test case $$$n=7$$$, $$$s=$$$"1003004", $$$w=4$$$ and one query $$$l_1=1$$$, $$$r_1=2$$$, $$$k_1=1$$$. Note that $$$v(1,2)=10$$$. We need to find a pair of substrings of length $$$4$$$ such that $$$v(L_1, L_1+3)\cdot10+v(L_2,L_2+3)$$$ has a remainder of $$$k_1=1$$$ when divided by $$$9$$$. The values $$$L_1=2, L_2=4$$$ actually satisfy all the requirements: $$$v(L_1, L_1+w-1)=v(2,5)=30$$$, $$$v(L_2, L_2+w-1)=v(4,7)=3004$$$. Indeed, $$$30\cdot10+3004=3304$$$, which has a remainder of $$$1$$$ when divided by $$$9$$$. It can be shown that $$$L_1=2$$$ is the minimum possible value, and $$$L_2=4$$$ is the minimum possible with $$$L_1=2$$$.
You are given two non-empty strings $$$s$$$ and $$$t$$$, consisting of Latin letters.
In one move, you can choose an occurrence of the string $$$t$$$ in the string $$$s$$$ and replace it with dots.
Your task is to remove all occurrences of the string $$$t$$$ in the string $$$s$$$ in the minimum number of moves, and also calculate how many different sequences of moves of the minimum length exist.
Two sequences of moves are considered different if the sets of indices at which the removed occurrences of the string $$$t$$$ in $$$s$$$ begin differ. For example, the sets $$$\{1, 2, 3\}$$$ and $$$\{1, 2, 4\}$$$ are considered different, the sets $$$\{2, 4, 6\}$$$ and $$$\{2, 6\}$$$ — too, but sets $$$\{3, 5\}$$$ and $$$\{5, 3\}$$$ — not.
For example, let the string $$$s =$$$ "abababacababa" and the string $$$t =$$$ "aba". We can remove all occurrences of the string $$$t$$$ in $$$2$$$ moves by cutting out the occurrences of the string $$$t$$$ at the $$$3$$$th and $$$9$$$th positions. In this case, the string $$$s$$$ is an example of the form "ab...bac...ba". It is also possible to cut occurrences of the string $$$t$$$ at the $$$3$$$th and $$$11$$$th positions. There are two different sequences of minimum length moves.
Since the answer can be large, output it modulo $$$10^9 + 7$$$.
The first line of the input contains a single integer $$$q$$$ ($$$1 \le q \le 50$$$) — the number of test cases. The descriptions of the sets follow.
The first line of each set contains a non-empty string $$$s$$$ ($$$1 \le |s| \le 500$$$) consisting of lowercase Latin letters.
The second line of each set contains a non-empty string $$$t$$$ ($$$1 \le |t| \le 500$$$) consisting of lowercase Latin letters.
It is guaranteed that the sum of string lengths $$$s$$$ over all test cases does not exceed $$$500$$$. Similarly, it is guaranteed that the sum of string lengths $$$t$$$ over all test cases does not exceed $$$500$$$.
For each test case print two integers — the minimum number of moves and the number of different optimal sequences, modulo $$$10^9 + 7$$$.
8abababacababaabadddddddddddxyzxyzxyzabcabcdabacabaabacaabcdefaaaaaaaaaaaaaaaaaaa
2 2 1 4 2 1 0 1 1 1 0 1 8 1 3 6
The first test case is explained in the statement.
In the second case, it is enough to cut any of the four occurrences.
In the third case, string $$$s$$$ is the concatenation of two strings $$$t =$$$ "xyz", so there is a unique optimal sequence of $$$2$$$ moves.
In the fourth and sixth cases, the string $$$s$$$ initially contains no occurrences of the string $$$t$$$.
In the fifth case, the string $$$s$$$ contains exactly one occurrence of the string $$$t$$$.