You are given a string $$$S$$$ of length $$$n$$$.
The string $$$S$$$ consists only of the character 'A'.
Your task is to count how many substrings of $$$S$$$ are equal to "AAA".
A substring is a contiguous part of the string.
The first and only line contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the length of the string $$$S$$$.
It is guaranteed that $$$S$$$ consists of exactly $$$n$$$ characters, and all of them are equal to 'A'.
Print a single integer — the number of substrings of $$$S$$$ that are equal to "AAA".
5
3
1
0
For $$$n = 5$$$, the string is "AAAAA".
The substrings equal to "AAA" start at positions $$$1$$$, $$$2$$$, and $$$3$$$, so the answer is $$$3$$$.
You are given an array of $$$n$$$ integers. You want to make all the numbers in this array as odd. In one operation you can select two indices $$$i$$$ and $$$j$$$ $$$(i \neq j)$$$ and replace $$$a_i$$$ with $$$(a_i + a_j)$$$.
Find the minimum number of operations needed to make all the numbers odd. If there is no way to do it, then print $$$-1$$$.
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^{2})$$$ — the number of test cases in the input.
Then $$$t$$$ test cases follow.
The first line of the test case contains one integer $$$n$$$ $$$( 1 \leq n \leq 2\cdot10^{5} )$$$.
The second line of the test case contains $$$n$$$ space-separated integers $$$a_i$$$ $$$( 1 \leq a_i \leq 10^{6} )$$$$$$-$$$$$$a_i$$$ is the $$$i^{th}$$$ number.
It is guaranteed that the sum of $$$n$$$ does not exceed $$$2\cdot10^{5}(\sum n \leq 2\cdot10^{5})$$$.
For each test case, If it is impossible to make all the numbers odd then print $$$-1$$$, otherwise print the minimum number of operation needed to make all the numbers odd.
4 4 1 4 3 2 5 1 4 3 2 5 6 1 2 6 5 3 4 3 4 2 6
2 2 3 -1
In the first test
Operation 1: replace $$$a_2$$$ with $$$(a_1 + a_2)$$$. The new array is $$$a = [1, 5, 3, 2]$$$.
Operation 2: replace $$$a_4$$$ with $$$(a_3 + a_4)$$$. The new array is $$$a = [1, 5, 3, 5]$$$.
In the fourth test, it is impossible to make all the numbers as odd.
Matryoshka Dolls are Russia's most popular souvenirs. They are sets of wooden figurines of decreasing size placed one inside another, though they have the same exact shape.
Our Matryoshka Doll is known to have an integer size $$$S$$$ which is the largest doll size in the collection, and each doll should have size $$$X$$$ times less than the doll that holds it($$$\textrm{size of the doll} \le \frac{\textrm{size of the doll that holds it}}{X}$$$).
Given $$$S$$$ and $$$X$$$, What is the maximum number of dolls that can be nested inside each other.
The first and only line contains $$$2$$$ integers $$$S,X$$$($$$1 \le S \le 10^9$$$ , $$$2 \le X \le 10^9$$$).
Output one integer, the maximum number of dolls.
10 2
4
There is an $$$n \times m$$$ grid of white and black squares. In one operation, you can select any two squares of the same color, and color all squares in the subrectangle between them that color.
Formally, if you select positions $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, both of which are currently the same color $$$c$$$, set the color of all $$$(x, y)$$$ where $$$\min(x_1, x_2) \le x \le \max(x_1, x_2)$$$ and $$$\min(y_1, y_2) \le y \le \max(y_1, y_2)$$$ to $$$c$$$.
This diagram shows a sequence of two possible operations on a grid:
Is it possible for all squares in the grid to be the same color, after performing any number of operations (possibly zero)?
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — 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 \le n, m \le 500$$$) — the number of rows and columns in the grid, respectively.
Each of the next $$$n$$$ lines contains $$$m$$$ characters 'W' and 'B' — the initial colors of the squares of the grid.
It is guaranteed that the sum of $$$n\cdot m$$$ over all test cases does not exceed $$$3\cdot 10^5$$$.
For each test case, print "YES" if it is possible to make all squares in the grid the same color, and "NO" otherwise.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
82 1WB6 6WWWWBWWBWWWWBBBWWWBWWWBBWWBWBBBBBWBW1 1W2 2BBBB3 4BWBWWBWBBWBW4 2BBBBWWWW4 4WWBWBBWBWWBBBBBB1 5WBBWB
NO YES YES YES YES NO YES NO
In the first example, it is impossible to ever change the color of any square with an operation, so we output NO.
The second example is the case pictured above. As shown in that diagram, it is possible for all squares to be white after two operations, so we output YES.
In the third and fourth examples, all squares are already the same color, so we output YES.
In the fifth example we can do everything in two operations. First, select positions $$$(2, 1)$$$ and $$$(1, 4)$$$ and color all squares with $$$1 \le x \le 2$$$ and $$$1 \le y \le 4$$$ to white. Then, select positions $$$(2, 1)$$$ and $$$(3, 4)$$$ and color all squares with $$$2 \le x \le 3$$$ and $$$1 \le y \le 4$$$ to white. After these two operations all squares are white.
Given a string $$$S$$$ of length $$$N$$$, find the length of the longest substring$$$^\dagger$$$ $$$R$$$ such that: $$$$$$\sum_{c=\texttt{'a'}}^{\texttt{'z'}} freq[c] \cdot C \ge |R| \cdot max(R)$$$$$$
Where:
- $$$freq[c]$$$ is the frequency of the character $$$c$$$ in the substring $$$R$$$.
- $$$C$$$ is the value of the character $$$c$$$ (the letter 'a' has a value of $$$1$$$, the letter 'b' has a value of $$$2$$$, and so on).
- $$$|R|$$$ is the length of the substring $$$R$$$.
- $$$max(R)$$$ is the greatest value of a character in the substring $$$R$$$.
$$$\dagger$$$ Substring: obtained by deleting several (possibly zero) characters from the start of the string and several (possibly zero) characters from the end of the string.
The first line of the input contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$) — the length of the string $$$S$$$.
The second line of the input contains a string $$$S$$$ of length $$$N$$$, consisting of lowercase English letters.
Output one line containing a single integer — the length of the longest substring that satisfies the condition.
4abcd
1
3bba
2
Omar helps George prepare tests on polygons.
Now George is thrilled, so he gives Omar an array of size $$$n$$$ as a present, where each element $$$a_i$$$ is equal to $$$i$$$, starting from $$$1$$$ and ending at $$$n$$$.
As Omar is "The Math Guy" he immediately starts doing these operations on the array $$$n$$$ times in order:
- Remove the $$$\dagger$$$Median of the array.
- Add the $$$\ddagger$$$MEX of the array to his score.
Can you tell Omar his final score?
$$$\dagger$$$Median of the array is the element in position $$$\lceil \frac{n}{2} \rceil$$$ of the array. Median of $$$[1,2,3,4]$$$ is $$$2$$$ , Median of $$$[1,2,3]$$$ is $$$2$$$.
$$$\ddagger$$$MEX is the minimum positive number not present in the array. MEX of $$$[]$$$ is $$$1$$$, MEX of $$$[1,3,5]$$$ is $$$2$$$.
The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 10^{5} )$$$. A description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ $$$( 1 \le n \le 10^{9} )$$$ indicating the size of the array.
For each test case print a single integer represents Omar's final score.
212
1 2
You are given an array $$$A$$$ of length $$$N$$$. Count the number of subarrays$$$^\dagger$$$ such that the number of elements divisible by $$$K$$$ is divisible by $$$K$$$.
$$$\dagger$$$ A subarray is obtained by deleting several (possibly zero) elements from the start of the array and several (possibly zero) elements from the end of the array.
The first line of the input consists of two space-separated integers $$$N$$$ and $$$K$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le K \le 10^9$$$) — the number of elements in the array and the integer $$$K$$$ from the problem statement, respectively.
The second line of the input consists of $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ ($$$1 \le A_i \le 10^9$$$).
Output one line containing a single integer — the answer to the problem.
7 31 9 3 4 5 6 6
7
2 10000000001 1000000000
1
In the first sample test, the subarrays are:
- $$$[1]$$$ $$$9$$$ $$$3$$$ $$$4$$$ $$$5$$$ $$$6$$$ $$$6$$$
- $$$[1$$$ $$$9$$$ $$$3$$$ $$$4$$$ $$$5$$$ $$$6]$$$ $$$6$$$
- $$$1$$$ $$$[9$$$ $$$3$$$ $$$4$$$ $$$5$$$ $$$6]$$$ $$$6$$$
- $$$1$$$ $$$9$$$ $$$[3$$$ $$$4$$$ $$$5$$$ $$$6$$$ $$$6]$$$
- $$$1$$$ $$$9$$$ $$$3$$$ $$$[4]$$$ $$$5$$$ $$$6$$$ $$$6$$$
- $$$1$$$ $$$9$$$ $$$3$$$ $$$[4$$$ $$$5]$$$ $$$6$$$ $$$6$$$
- $$$1$$$ $$$9$$$ $$$3$$$ $$$4$$$ $$$[5]$$$ $$$6$$$ $$$6$$$
In the second sample test, there's only one subarray: [$$$1$$$] $$$1000000000$$$. This subarray has $$$0$$$ elements divisible by $$$K = 1000000000$$$, and $$$0$$$ is divisible by $$$1000000000$$$.
Given an array $$$a$$$ of length $$$n$$$. A partition of the array $$$a$$$ is dividing it into subarrays$$$^{[1]}$$$ such that each element of $$$a$$$ belongs to exactly one subarray. Two partitions are considered different if there is a subarray that is present in one of the partitions but not in both of them.
We define the cost of a partition of $$$a$$$ as the following:
- Let's initialize cost to be equal to $$$0$$$.
- For each subarray of $$$a$$$ (i.e. $$$a[l, l + 1, \ldots, r]$$$) that is present in the partition, let $$$s$$$ be equal to the sum of integers in this subarray (i.e. $$$\displaystyle\sum_{i=l}^r a_i$$$).
- Update cost to be equal to cost $$$\oplus$$$ $$$s$$$, where $$$\oplus$$$ is the bitwise XOR$$$^{[8]}$$$ operator.
Find the bitwise XOR of the costs of all possible partitions of $$$a$$$.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.
For each test case, the first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the array $$$a$$$.
The second line consists of $$$n$$$ spaces-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.
Output $$$t$$$ lines, the $$$i$$$-th of which contains a single integer — the answer for the $$$i$$$-th test case.
31121 231 2 3
1 0 2