It is given a positive integer $$$n$$$. In $$$1$$$ move, one can select any single digit and remove it (i.e. one selects some position in the number and removes the digit located at this position). The operation cannot be performed if only one digit remains. If the resulting number contains leading zeroes, they are automatically removed.
E.g. if one removes from the number $$$32925$$$ the $$$3$$$-rd digit, the resulting number will be $$$3225$$$. If one removes from the number $$$20099050$$$ the first digit, the resulting number will be $$$99050$$$ (the $$$2$$$ zeroes going next to the first digit are automatically removed).
What is the minimum number of steps to get a number such that it is divisible by $$$25$$$ and positive? It is guaranteed that, for each $$$n$$$ occurring in the input, the answer exists. It is guaranteed that the number $$$n$$$ has no leading zeros.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.
Each test case consists of one line containing one integer $$$n$$$ ($$$25 \le n \le 10^{18}$$$). It is guaranteed that, for each $$$n$$$ occurring in the input, the answer exists. It is guaranteed that the number $$$n$$$ has no leading zeros.
For each test case output on a separate line an integer $$$k$$$ ($$$k \ge 0$$$) — the minimum number of steps to get a number such that it is divisible by $$$25$$$ and positive.
5 100 71345 3259 50555 2050047
0 3 1 3 2
In the first test case, it is already given a number divisible by $$$25$$$.
In the second test case, we can remove the digits $$$1$$$, $$$3$$$, and $$$4$$$ to get the number $$$75$$$.
In the third test case, it's enough to remove the last digit to get the number $$$325$$$.
In the fourth test case, we can remove the three last digits to get the number $$$50$$$.
In the fifth test case, it's enough to remove the digits $$$4$$$ and $$$7$$$.
There is a chessboard of size $$$n$$$ by $$$n$$$. The square in the $$$i$$$-th row from top and $$$j$$$-th column from the left is labelled $$$(i,j)$$$.
Currently, Gregor has some pawns in the $$$n$$$-th row. There are also enemy pawns in the $$$1$$$-st row. On one turn, Gregor moves one of his pawns. A pawn can move one square up (from $$$(i,j)$$$ to $$$(i-1,j)$$$) if there is no pawn in the destination square. Additionally, a pawn can move one square diagonally up (from $$$(i,j)$$$ to either $$$(i-1,j-1)$$$ or $$$(i-1,j+1)$$$) if and only if there is an enemy pawn in that square. The enemy pawn is also removed.
Gregor wants to know what is the maximum number of his pawns that can reach row $$$1$$$?
Note that only Gregor takes turns in this game, and the enemy pawns never move. Also, when Gregor's pawn reaches row $$$1$$$, it is stuck and cannot make any further moves.
The first line of the input contains one integer $$$t$$$ ($$$1\le t\le 2\cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.
Each test case consists of three lines. The first line contains a single integer $$$n$$$ ($$$2\le n\le 2\cdot{10}^{5}$$$) — the size of the chessboard.
The second line consists of a string of binary digits of length $$$n$$$, where a $$$1$$$ in the $$$i$$$-th position corresponds to an enemy pawn in the $$$i$$$-th cell from the left, and $$$0$$$ corresponds to an empty cell.
The third line consists of a string of binary digits of length $$$n$$$, where a $$$1$$$ in the $$$i$$$-th position corresponds to a Gregor's pawn in the $$$i$$$-th cell from the left, and $$$0$$$ corresponds to an empty cell.
It is guaranteed that the sum of $$$n$$$ across all test cases is less than $$$2\cdot{10}^{5}$$$.
For each test case, print one integer: the maximum number of Gregor's pawns which can reach the $$$1$$$-st row.
4 3 000 111 4 1111 1111 3 010 010 5 11001 00000
3 4 0 0
In the first example, Gregor can simply advance all $$$3$$$ of his pawns forward. Thus, the answer is $$$3$$$.
In the second example, Gregor can guarantee that all $$$4$$$ of his pawns reach the enemy row, by following the colored paths as demonstrated in the diagram below. Remember, only Gregor takes turns in this "game"!
In the third example, Gregor's only pawn is stuck behind the enemy pawn, and cannot reach the end.
In the fourth example, Gregor has no pawns, so the answer is clearly $$$0$$$.
You are given an $$$n \times m$$$ grid $$$a$$$ of non-negative integers. The value $$$a_{i,j}$$$ represents the depth of water at the $$$i$$$-th row and $$$j$$$-th column.
A lake is a set of cells such that:
- each cell in the set has $$$a_{i,j} \gt 0$$$, and
- there exists a path between any pair of cells in the lake by going up, down, left, or right a number of times and without stepping on a cell with $$$a_{i,j} = 0$$$.
The volume of a lake is the sum of depths of all the cells in the lake.
Find the largest volume of a lake in the grid.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
The first line of each test case contains two integers $$$n, m$$$ ($$$1 \leq n, m \leq 1000$$$) — the number of rows and columns of the grid, respectively.
Then $$$n$$$ lines follow each with $$$m$$$ integers $$$a_{i,j}$$$ ($$$0 \leq a_{i,j} \leq 1000$$$) — the depth of the water at each cell.
It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, output a single integer — the largest volume of a lake in the grid.
53 31 2 03 4 00 0 51 103 30 1 11 0 11 1 15 51 1 1 1 11 0 0 0 11 0 5 0 11 0 0 0 11 1 1 1 15 51 1 1 1 11 0 0 0 11 1 4 0 11 0 0 0 11 1 1 1 1
10 0 7 16 21
Timofey has an apple tree growing in his garden; it is a rooted tree of $$$n$$$ vertices with the root in vertex $$$1$$$ (the vertices are numbered from $$$1$$$ to $$$n$$$). A tree is a connected graph without loops and multiple edges.
This tree is very unusual — it grows with its root upwards. However, it's quite normal for programmer's trees.
The apple tree is quite young, so only two apples will grow on it. Apples will grow in certain vertices (these vertices may be the same). After the apples grow, Timofey starts shaking the apple tree until the apples fall. Each time Timofey shakes the apple tree, the following happens to each of the apples:
Let the apple now be at vertex $$$u$$$.
- If a vertex $$$u$$$ has a child, the apple moves to it (if there are several such vertices, the apple can move to any of them).
- Otherwise, the apple falls from the tree.
It can be shown that after a finite time, both apples will fall from the tree.
Timofey has $$$q$$$ assumptions in which vertices apples can grow. He assumes that apples can grow in vertices $$$x$$$ and $$$y$$$, and wants to know the number of pairs of vertices ($$$a$$$, $$$b$$$) from which apples can fall from the tree, where $$$a$$$ — the vertex from which an apple from vertex $$$x$$$ will fall, $$$b$$$ — the vertex from which an apple from vertex $$$y$$$ will fall. Help him do this.
The first line contains integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
The first line of each test case contains integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of vertices in the tree.
Then there are $$$n - 1$$$ lines describing the tree. In line $$$i$$$ there are two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$) — edge in tree.
The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of Timofey's assumptions.
Each of the next $$$q$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$) — the supposed vertices on which the apples will grow for the assumption $$$i$$$.
It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$. Similarly, It is guaranteed that the sum of $$$q$$$ does not exceed $$$2 \cdot 10^5$$$.
For each Timofey's assumption output the number of ordered pairs of vertices from which apples can fall from the tree if the assumption is true on a separate line.
251 23 45 33 243 45 14 41 331 21 331 12 33 1
2 2 1 4 4 1 2
255 11 22 34 325 55 153 25 32 14 234 32 14 2
1 2 1 4 2
In the first example:
- For the first assumption, there are two possible pairs of vertices from which apples can fall from the tree: $$$(4, 4), (5, 4)$$$.
- For the second assumption there are also two pairs: $$$(5, 4), (5, 5)$$$.
- For the third assumption there is only one pair: $$$(4, 4)$$$.
- For the fourth assumption, there are $$$4$$$ pairs: $$$(4, 4), (4, 5), (5, 4), (5, 5)$$$.
Tree from the first example. For the second example, there are $$$4$$$ of possible pairs of vertices from which apples can fall: $$$(2, 3), (2, 2), (3, 2), (3, 3)$$$. For the second assumption, there is only one possible pair: $$$(2, 3)$$$. For the third assumption, there are two pairs: $$$(3, 2), (3, 3)$$$.
Monocarp is playing a computer game. Now he wants to complete the first level of this game.
A level is a rectangular grid of $$$2$$$ rows and $$$n$$$ columns. Monocarp controls a character, which starts in cell $$$(1, 1)$$$ — at the intersection of the $$$1$$$-st row and the $$$1$$$-st column.
Monocarp's character can move from one cell to another in one step if the cells are adjacent by side and/or corner. Formally, it is possible to move from cell $$$(x_1, y_1)$$$ to cell $$$(x_2, y_2)$$$ in one step if $$$|x_1 - x_2| \le 1$$$ and $$$|y_1 - y_2| \le 1$$$. Obviously, it is prohibited to go outside the grid.
There are traps in some cells. If Monocarp's character finds himself in such a cell, he dies, and the game ends.
To complete a level, Monocarp's character should reach cell $$$(2, n)$$$ — at the intersection of row $$$2$$$ and column $$$n$$$.
Help Monocarp determine if it is possible to complete the level.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then the test cases follow. Each test case consists of three lines.
The first line contains a single integer $$$n$$$ ($$$3 \le n \le 100$$$) — the number of columns.
The next two lines describe the level. The $$$i$$$-th of these lines describes the $$$i$$$-th line of the level — the line consists of the characters '0' and '1'. The character '0' corresponds to a safe cell, the character '1' corresponds to a trap cell.
Additional constraint on the input: cells $$$(1, 1)$$$ and $$$(2, n)$$$ are safe.
For each test case, output YES if it is possible to complete the level, and NO otherwise.
4 3 000 000 4 0011 1100 4 0111 1110 6 010101 101010
YES YES NO YES
Consider the example from the statement.
In the first test case, one of the possible paths is $$$(1, 1) \rightarrow (2, 2) \rightarrow (2, 3)$$$.
In the second test case, one of the possible paths is $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 3) \rightarrow (2, 4)$$$.
In the fourth test case, one of the possible paths is $$$(1, 1) \rightarrow (2, 2) \rightarrow (1, 3) \rightarrow (2, 4) \rightarrow (1, 5) \rightarrow (2, 6)$$$.
Initially you have a single pile with $$$n$$$ gold nuggets. In an operation you can do the following:
- Take any pile and split it into two piles, so that one of the resulting piles has exactly twice as many gold nuggets as the other. (All piles should have an integer number of nuggets.)
One possible move is to take a pile of size $$$6$$$ and split it into piles of sizes $$$2$$$ and $$$4$$$, which is valid since $$$4$$$ is twice as large as $$$2$$$.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.
The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^7$$$) — the starting and target pile sizes, respectively.
For each test case, output "YES" if you can make a pile of size exactly $$$m$$$, and "NO" otherwise.
You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
116 49 44 218 2727 427 227 101 13 15 1746001 2984004
YES YES NO NO YES YES NO YES YES NO NO
The first test case is pictured in the statement. We can make a pile of size $$$4$$$.
In the second test case, we can perform the following operations: $$$\{\color{red}{9}\} \to \{\color{red}{6},3\} \to \{4,2,3\}$$$. The pile that is split apart is colored red before each operation.
In the third test case, we can't perform a single operation.
In the fourth test case, we can't end up with a larger pile than we started with.
You are given a rooted tree consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. The root is vertex $$$1$$$. There is also a string $$$s$$$ denoting the color of each vertex: if $$$s_i = \texttt{B}$$$, then vertex $$$i$$$ is black, and if $$$s_i = \texttt{W}$$$, then vertex $$$i$$$ is white.
A subtree of the tree is called balanced if the number of white vertices equals the number of black vertices. Count the number of balanced subtrees.
A tree is a connected undirected graph without cycles. A rooted tree is a tree with a selected vertex, which is called the root. In this problem, all trees have root $$$1$$$.
The tree is specified by an array of parents $$$a_2, \dots, a_n$$$ containing $$$n-1$$$ numbers: $$$a_i$$$ is the parent of the vertex with the number $$$i$$$ for all $$$i = 2, \dots, n$$$. The parent of a vertex $$$u$$$ is a vertex that is the next vertex on a simple path from $$$u$$$ to the root.
The subtree of a vertex $$$u$$$ is the set of all vertices that pass through $$$u$$$ on a simple path to the root. For example, in the picture below, $$$7$$$ is in the subtree of $$$3$$$ because the simple path $$$7 \to 5 \to 3 \to 1$$$ passes through $$$3$$$. Note that a vertex is included in its subtree, and the subtree of the root is the entire tree.
The picture shows the tree for $$$n=7$$$, $$$a=[1,1,2,3,3,5]$$$, and $$$s=\texttt{WBBWWBW}$$$. The subtree at the vertex $$$3$$$ is balanced. The first line of input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 4000$$$) — the number of vertices in the tree.
The second line of each test case contains $$$n-1$$$ integers $$$a_2, \dots, a_n$$$ ($$$1 \le a_i \lt i$$$) — the parents of the vertices $$$2, \dots, n$$$.
The third line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of the characters $$$\texttt{B}$$$ and $$$\texttt{W}$$$ — the coloring of the tree.
It is guaranteed that the sum of the values $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output a single integer — the number of balanced subtrees.
371 1 2 3 3 5WBBWWBW21BW81 2 3 4 5 6 7BWBWBWBW
2 1 4
The first test case is pictured in the statement. Only the subtrees at vertices $$$2$$$ and $$$3$$$ are balanced.
In the second test case, only the subtree at vertex $$$1$$$ is balanced.
In the third test case, only the subtrees at vertices $$$1$$$, $$$3$$$, $$$5$$$, and $$$7$$$ are balanced.
Alice and Bob play the following game. Alice has a set $$$S$$$ of disjoint ranges of integers, initially containing only one range $$$[1, n]$$$. In one turn, Alice picks a range $$$[l, r]$$$ from the set $$$S$$$ and asks Bob to pick a number in the range. Bob chooses a number $$$d$$$ ($$$l \le d \le r$$$). Then Alice removes $$$[l, r]$$$ from $$$S$$$ and puts into the set $$$S$$$ the range $$$[l, d - 1]$$$ (if $$$l \le d - 1$$$) and the range $$$[d + 1, r]$$$ (if $$$d + 1 \le r$$$). The game ends when the set $$$S$$$ is empty. We can show that the number of turns in each game is exactly $$$n$$$.
After playing the game, Alice remembers all the ranges $$$[l, r]$$$ she picked from the set $$$S$$$, but Bob does not remember any of the numbers that he picked. But Bob is smart, and he knows he can find out his numbers $$$d$$$ from Alice's ranges, and so he asks you for help with your programming skill.
Given the list of ranges that Alice has picked ($$$[l, r]$$$), for each range, help Bob find the number $$$d$$$ that Bob has picked.
We can show that there is always a unique way for Bob to choose his number for a list of valid ranges picked by Alice.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$).
Each of the next $$$n$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$), denoting the range $$$[l, r]$$$ that Alice picked at some point.
Note that the ranges are given in no particular order.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$, and the ranges for each test case are from a valid game.
For each test case print $$$n$$$ lines. Each line should contain three integers $$$l$$$, $$$r$$$, and $$$d$$$, denoting that for Alice's range $$$[l, r]$$$ Bob picked the number $$$d$$$.
You can print the lines in any order. We can show that the answer is unique.
It is not required to print a new line after each test case. The new lines in the output of the example are for readability only.
4 1 1 1 3 1 3 2 3 2 2 6 1 1 3 5 4 4 3 6 4 5 1 6 5 1 5 1 2 4 5 2 2 4 4
1 1 1 1 3 1 2 2 2 2 3 3 1 1 1 3 5 3 4 4 4 3 6 6 4 5 5 1 6 2 1 5 3 1 2 1 4 5 5 2 2 2 4 4 4
In the first test case, there is only 1 range $$$[1, 1]$$$. There was only one range $$$[1, 1]$$$ for Alice to pick, and there was only one number $$$1$$$ for Bob to pick.
In the second test case, $$$n = 3$$$. Initially, the set contains only one range $$$[1, 3]$$$.
- Alice picked the range $$$[1, 3]$$$. Bob picked the number $$$1$$$. Then Alice put the range $$$[2, 3]$$$ back to the set, which after this turn is the only range in the set.
- Alice picked the range $$$[2, 3]$$$. Bob picked the number $$$3$$$. Then Alice put the range $$$[2, 2]$$$ back to the set.
- Alice picked the range $$$[2, 2]$$$. Bob picked the number $$$2$$$. The game ended.
In the fourth test case, the game was played with $$$n = 5$$$. Initially, the set contains only one range $$$[1, 5]$$$. The game's turn is described in the following table.
| Game turn | Alice's picked range | Bob's picked number | The range set after |
| Before the game start | $$$ \{ [1, 5] \} $$$ | ||
| 1 | $$$[1, 5]$$$ | $$$3$$$ | $$$ \{ [1, 2], [4, 5] \}$$$ |
| 2 | $$$[1, 2]$$$ | $$$1$$$ | $$$ \{ [2, 2], [4, 5] \} $$$ |
| 3 | $$$[4, 5]$$$ | $$$5$$$ | $$$ \{ [2, 2], [4, 4] \} $$$ |
| 4 | $$$[2, 2]$$$ | $$$2$$$ | $$$ \{ [4, 4] \} $$$ |
| 5 | $$$[4, 4]$$$ | $$$4$$$ | $$$ \{ \} $$$ (empty set) |
There is a grid with $$$n$$$ rows and $$$m$$$ columns, and three types of cells:
- An empty cell, denoted with '.'.
- A stone, denoted with '*'.
- An obstacle, denoted with the lowercase Latin letter 'o'.
All stones fall down until they meet the floor (the bottom row), an obstacle, or other stone which is already immovable. (In other words, all the stones just fall down as long as they can fall.)
Simulate the process. What does the resulting grid look like?
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 50$$$) — the number of rows and the number of columns in the grid, respectively.
Then $$$n$$$ lines follow, each containing $$$m$$$ characters. Each of these characters is either '.', '*', or 'o' — an empty cell, a stone, or an obstacle, respectively.
For each test case, output a grid with $$$n$$$ rows and $$$m$$$ columns, showing the result of the process.
You don't need to output a new line after each test, it is in the samples just for clarity.
3 6 10 .*.*....*. .*.......* ...o....o. .*.*....*. .......... .o......o* 2 9 ...***ooo .*o.*o.*o 5 5 ***** *.... ***** ....* *****
.......... ...*....*. .*.o....o. .*........ .*......** .o.*....o* ....**ooo .*o**o.*o ..... *...* ***** ***** *****