Mr. Milky has been playing with dice a lot. Recently, he has played a game where he rolls a standard six sided die an arbitrary number of times, and each time he rolls the die, he writes the number down on a piece of paper. At the end, he takes the product of all his rolls and writes it down as well.
However, he spilled his glass of milk all over the paper and cannot remember his individual rolls, only the final product. Given that the final product of his rolls is $$$N$$$, find the maximum possible sum of the numbers he rolled.
An integer $$$N$$$ ($$$1 ≤ N ≤ 10^5$$$), representing the product of all individual dice rolls.
Print the maximum possible sum of the individual dice rolls. If there is no possible configuration of dice rolls that multiply to $$$N$$$, print $$$-1$$$. If the number exceeds $$$10^9$$$, print $$$10^9 + 7$$$.
7
-1
In the example test case, the output is $$$-1$$$ as you cannot contribute a factor of $$$7$$$ from a standard six sided die.
Mr. Milky has $$$N$$$ friends coming over, numbered from $$$1$$$ to $$$N$$$. Each friend has a strong preference for their favorite type of milk and how much of it. Since Mr. Milky has very simple friends, the $$$i$$$-th friend prefers milk type $$$i$$$ and $$$C_i$$$ buckets of said milk type.
However, after properly preparing the buckets of milk, Mr. Milky knocks them all over and now needs to clean it all up! He uses a special mop that can clean up one bucket spill in one minute.
Given that all $$$N$$$ friends will arrive at time $$$T$$$ and that the $$$i$$$-th friend will immediately leave if their $$$C_i$$$ buckets of milk are all over the floor, find the maximum number of friends that can stay.
The first line contains integers $$$N$$$ ($$$1 ≤ N ≤ 10^5$$$) and $$$T$$$ ($$$1 ≤ T ≤ 10^5$$$), representing the number of friends coming over and the time they will all arrive.
The second line contains integers $$$C_1, C_2, \ldots, C_N$$$, describing the number of buckets of milk each friend would like ($$$1 ≤ Ci ≤ 10^3$$$).
A single integer stating the maximum number of friends that can stay.
3 95 1 3
3
In the example test case, Mr. Milky can clean up all of the buckets of milk in $$$5 + 1 + 3 = 9$$$ minutes, which is within the time constraint.
Given an $$$n$$$ by $$$m$$$ rectangle print the maximum $$$mex$$$ over all subrectanges. The $$$mex$$$ of a subrectange is defined by the mex of all elements in the subrectangle. The $$$mex$$$ of a set of elements in the minimum excluded non-negative integer. (For example, the $$$mex$$$ of an array $$$[0,1,3,5]$$$ is $$$2$$$.)
The first line of the input contains a single integer $$$t$$$ ($$$1≤t≤50$$$) — the number of test cases. Then the descriptions of the test cases follow.
The first line of each test case contains 2 integers $$$N$$$ and $$$M$$$ ($$$1 \lt = N, M \lt = 500$$$), the size of the grid. The following $$$N$$$ lines contain $$$M$$$ integers each, the $$$j$$$-th element in the $$$i$$$-th line $$$a_{i,j}$$$ is the number written in the $$$j$$$-th cell of the $$$i$$$-th row $$$(0≤a_{i,j}≤250000)$$$
Print out $$$1$$$ integer, the maximum $$$mex$$$ over all subrectanges.
3 3 3 1 2 0 5 2 3 0 5 6 2 2 1 2 0 3 1 1 1
4 4 0
Oh no! The students have gotten themselves out of order in line. Can you get them back into order?
They are conveniently named $$$1$$$, $$$2$$$, $$$3$$$, ... and $$$N$$$. District policy ensures $$$N\le 1,000$$$. However, the students want to be cool, so you can only swap two students if there is exactly 1 student between them. For example, if the line was $$$2$$$, $$$1$$$, $$$3$$$, you could swap students $$$2$$$ and $$$3$$$.
You want to get them into sorted order, meaning $$$1$$$, $$$2$$$, $$$3$$$, ... $$$N$$$. Is it possible to sort the students while making sure they all look like cool kids? If so, print the minimum number of swaps needed to sort them. If not, print $$$-1$$$.
On the first line, you are provided an integer $$$1\le N\le 1,000$$$. On the next line, there are $$$N$$$ space-separated integers describing the current arrangement of students. The number $$$i$$$ at the $$$j^\text{th}$$$ position means that student $$$i$$$ is currently standing at position $$$j$$$.
Print a single integer, $$$-1$$$ if it is impossible to sort the students and the number of swaps necessary otherwise.
55 4 1 2 3
3
Swap students $$$5$$$ and $$$1$$$ first, then students $$$5$$$ and $$$3$$$, and lastly students $$$2$$$ and $$$4$$$. They all end up in sorted order in $$$3$$$ swaps, and it can be shown that this is optimal.
Tortles recently learned about segment tree beats, which is a segment tree modification that supports range ckmin and ckmax operations in amortized$$$O(\log{n^2})$$$. Tortles decided to play with this funny data structure.
He started with an array $$$a$$$ of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ where ($$$1 \le a_i \le 10$$$). He then performed a series of operations over the entire array. In each operation, he chose a number $$$x$$$ between $$$1$$$ and $$$10$$$ and either the operation $$$min$$$ or $$$max$$$. He then set each element $$$a_i$$$ to $$$op(a_i, x)$$$ where $$$op$$$ is the operation he chose.
Unfortunately, after he played around with the array, his computer crashed and he lost his edit history. Given the final array after all operations he performed, how many distinct possibilities are there for the original array $$$a$$$?
The first line will have an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 9$$$) — the length of the array.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10$$$) — the values of the final array after all modifications are performed.
For each test case, print the number of possible starting arrays.
1 4 1 4 3 4
49
One night, Keys accidentally left the stove on when he went to bed! He woke up at 3:00 AM to find his house on fire. As Keys tries to escape, he sees his collection of N manga books on a shelf ($$$1 \lt = N \lt = 10^5$$$). Each manga book has a value to Keys of $$$a_i$$$, and Keys wants to save the most value possible. Every second, he can choose an index and take that manga, leaving behind an empty space. However, after every second, the Fire burns the left and right ends (index $$$1$$$ and $$$N$$$) of the bookshelf, burning either the manga there or nothing if Keys already took that manga. In the next second Keys can save another manga, after which the fire will burn the next ends (index $$$2$$$ and $$$N-1$$$). This will happen until the entire bookshelf if burned up. What is the maximum value of manga that Keys can save?
The first line contains an integer $$$N$$$ ($$$1 \lt = N \lt = 10^5$$$), the length of the bookshelf.
The second line contains $$$N$$$ integers $$$a_1,a_2,…,a_n$$$ ($$$1 \le a_i \le 10^5$$$), the value of each manga book at index $$$i$$$.
Print out $$$1$$$ integer, the maximum value of manga that Keys can save.
6 1 2 1000 4 5 100
1105
4 1 1000 1000 1
2000
4 1000 1 1 100
1001
Keys got caught lacking sleeping in English class, and was forcefully shaken awake by the teacher. (This would never have happened if Keys had instead slept in the sleeping bag instead.) As punishment, he was given this task to solve.
He was given an array of integers $$$a$$$ of length $$$n$$$, where each integer has a value $$$\le n$$$. His goal is to find if he can sort the array using only valid swaps. Define a swap as valid if for the $$$j$$$-th swap, elements $$$a_i$$$ and $$$a_{i + 1}$$$ are swapped, and $$$min(a_i, a_{i + 1}) \ge j$$$.
Unfortunately, Keys enjoys sleeping in his sleeping bag too much to solve the problem. Please help solve the problem for him before he gets in trouble!
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, print YES if it is possible to sort the array, otherwise print NO. 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.
242 1 4 332 1 1
YES NO
For the first test case, a valid sequence of swaps is the following: For the $$$1$$$-st swap, swap $$$a_1$$$ and $$$a_2$$$. This is valid since $$$min(a_1, a_2) = 1$$$, and $$$1 \ge 1$$$. For the $$$2$$$-nd swap, swap $$$a_3$$$ and $$$a_4$$$. This is valid since $$$min(a_3, a_4) = 3$$$, and $$$3 \ge 2$$$. After these two swaps, the array is sorted.
For the second test case, it can be seen that it is impossible to sort the array, since the $$$2$$$ is not able to make it to the third position.
Pirates love treasure, especially gold coins.
A band of pirates has $$$N$$$ ships arranged in a line, one after the other. Assume that the ships are numbered from $$$1$$$ to $$$N$$$, from the first to the last. Each ship can store a certain number of crates filled with gold coins, with the $$$i$$$-th ship having a maximum capacity of $$$G_i$$$ such crates.
At first, all of the ships are empty. At different times, the pirates load some number of crates onto various ships. If a ship receives more crates than its maximum capacity can afford, then the remaining crates will be loaded onto the next ship in line. In other words, if the $$$i$$$-th ship has reached its maximum capacity, the remaining crates will be loaded onto the ($$$i+1$$$)-th ship. Any remaining crates from the $$$N$$$-th ship will be thrown into the ocean.
Your task is to simulate loading crates onto the ships and answer queries about the number of crates on specific ships. There are two types of queries:
Assume that when you receive a query of the second type, all of the crates loaded up to that point have been properly distributed across the ships.
The first line contains two integers $$$N$$$ and $$$M$$$, the number of ships and queries, respectively ($$$1 ≤ N, M ≤ 10 ^ 5$$$).
The second line contains $$$N$$$ integers $$$G_1, G_2, \ldots, G_N$$$, each ship's maximum capacity ($$$1 ≤ G_i ≤ 10^5$$$).
Each of the next $$$M$$$ lines contains the description of one query. A query of the first type is inputted as $$$1$$$ $$$K_i$$$ $$$C_i$$$, and a query of the second type is inputted as $$$2$$$ $$$K_i$$$ ($$$1 ≤ K_i ≤ N, 1 ≤ C_i ≤ 10^5$$$).
For each query of the second type, print the number of crates on the corresponding ship.
4 64 8 10 61 1 101 2 62 12 21 4 42 4
4 8 4
Maomao has two integers $$$a$$$ and $$$b$$$. ($$$1 \le a, b \le 10^5$$$).
She computes $$$a \text{ & } b$$$, $$$a \text{ } | \text{ } b$$$, $$$a \oplus b$$$ and $$$a + b$$$ where $$$\text{&}$$$, $$$|$$$, and $$$\oplus$$$ are the bitwise operators and, or, and xor respectively
Unfortunately she loses $$$a$$$ and $$$b$$$ and then one of her computed values but she does not know which one.
Help her recover the lost computed value. If there are multiple values that could be the lost computed value, print any of them.
Note that it is okay if the multiset in your answer is produced by an $$$a$$$, $$$b$$$ pair where one of them is greater than $$$10^5$$$ as long as the multiset is a valid one.
The first line will have an integer $$$t$$$ ($$$1 \le t \le 100$$$) denoting the number of tests.
The first and only line of each tests will have three integers $$$x$$$, $$$y$$$, and $$$z$$$ denoting the three computed values Maomao still has. ($$$1 \le x, y, z \le 2 \cdot 10^5$$$).
For each testcase output a single integer.
2 1 4 9 68554 62260 65407
5 3147
Currently, Coconut and Orange are running to be president of the United Fruits of Fruitmerica! Fruitmerica is made up of a $$$3$$$ by $$$N$$$ cities $$$(1 \le N \le 100)$$$, where each city contains either a $$$0$$$ or $$$1$$$, where $$$0$$$ represents voting for Coconut and $$$1$$$ represents voting for Orange. Additionally, Fruitmerica is divided up into $$$N$$$ districts, where each $$$N$$$ districts contains $$$3$$$ cities that form a connected component. In these districts, if $$$2$$$ or more cities votes for a candidate, that candidate wins that district. Currently, the districts are drawn as straight lines down. However, Coconut wants to redraw the districts in order to gain more votes. Coconut can redraw the districts however she wants, as long as there are $$$N$$$ districts with $$$3$$$ cities in each, and all the districts are connected components. What is the maximum number of districts Coconut can win?
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases. Then the descriptions of the test cases follow.
The first line of each test case contains 1 integer $$$N$$$ ($$$1 \le N \le 100$$$).
The following $$$3$$$ lines contain $$$N$$$ integers each, the $$$j$$$-th element in the $$$i$$$-th line $$$a_{i,j}$$$ is either $$$0$$$ or $$$1$$$.
For each test case, output a single number, the most amount of districts Coconut can win.
3 3 0 1 0 1 0 1 1 1 0 4 1 0 0 1 0 1 1 0 0 1 0 1 2 0 1 1 0 1 1
2 3 1
Keys got caught lacking, sleeping in English class, and was forcefully shaken awake by the teacher. (This would never have happened if Keys had instead slept in the sleeping bag.) As punishment, he was given this task to solve.
He was given an array of integers $$$a$$$ of length $$$n$$$. His goal is to find if he can sort the array using only valid swaps. Define a swap as valid if for the $$$j$$$-th swap, elements $$$a_i$$$ and $$$a_{i + 1}$$$ are swapped, and $$$min(a_i, a_{i + 1}) \ge j$$$.
Unfortunately, Keys enjoys sleeping in his sleeping bag too much to solve the problem. Please help solve the problem for him before he gets in trouble!
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, print YES if it is possible to sort the array; otherwise, print NO. 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.
342 1 4 332 1 157 5 2 4 7
YES NO YES
For the first test case, a valid sequence of swaps is the following: For the $$$1$$$-st swap, swap $$$a_1$$$ and $$$a_2$$$. This is valid since $$$min(a_1, a_2) = 1$$$, and $$$1 \ge 1$$$. For the $$$2$$$-nd swap, swap $$$a_3$$$ and $$$a_4$$$. This is valid since $$$min(a_3, a_4) = 3$$$, and $$$3 \ge 2$$$. After these two swaps, the array is sorted.
For the second test case, it can be seen that it is impossible to sort the array since the $$$2$$$ is not able to make it to the third position.