You are given a single positive integer $$$M$$$. Construct an array of positive integers $$$a_1, \ldots, a_n$$$ such that:
- $$$1 \le a_i \le M$$$ for all $$$1 \le i \le n$$$;
- $$$a_i \bmod a_{i-1} = a_{i-2}$$$ for all $$$3 \le i \le n$$$;
- The size of the array $$$n$$$ is largest possible.
The first line of the input contains a single integer $$$T$$$ — the number of test cases ($$$1 \le T \le 10$$$).
Each test case is given as a line containing a single integer $$$M$$$ ($$$1 \le M \le 10^9$$$).
Output exactly two lines for each test case. The first line should contain a single integer $$$n$$$ — the size of your array.
The second line should contain $$$n$$$ space-separated integers $$$a_1, \ldots, a_n$$$ — the array itself.
2 2 3
3 1 2 1 4 1 2 3 2
Medet loves adding numbers. But...
He does not actually know how to add numbers. Instead, he just glues them together. So, $$$7+12$$$ in Medet's mind is actually $$$712$$$ instead of $$$19$$$. $$$51+20$$$ is $$$5120$$$ for Medet instead of $$$71$$$. We're lucky Medet has this confusion only for addition. He can correctly evaluate all other expressions.
Recently, Medet has stumbled upon this problem:
"You are given a positive integer $$$n$$$. Count the number of pairs $$$(a, b)$$$ satisfying $$$1 \le a, b \le n$$$ such that $$$a + b$$$ is divisible by both $$$a$$$ and $$$b$$$."
To Medet's surprise, the problem was solved by a lot of participants. In fact, Medet was the only one among his friends who did not solve this problem. Do you understand why?
Now you are curious if Medet's interpretation of the problem is solvable.
The input contains a single integer $$$n$$$ ($$$1 \le n \le 10^{16}$$$).
The output should contain a single integer — the number of desired pairs.
5
8
Some examples:
- $$$1 + 1 = 11$$$ is divisible by both $$$1$$$ and $$$1$$$.
- $$$2 + 4 = 24$$$ is divisible by both $$$2$$$ and $$$4$$$.
- $$$3 + 6 = 36$$$ is divisible by both $$$3$$$ and $$$6$$$.
- $$$2 + 8 = 28$$$ is divisible by $$$2$$$ but not divisible by $$$8$$$. Thus, we do not count this pair.
Batyr is studying math. Some serious math. But as we all know, it sometimes becomes very boring. When it happens, Batyr turns on his imagination and starts wandering in the infinite world of math and programming.
This time, he came up with a very cool linear algebra problem. You are given a matrix $$$a$$$ consisting of $$$m \times n$$$ integers. Also you are given two integer arrays $$$b$$$ of length $$$m$$$ and $$$c$$$ of length $$$n$$$. Your task is to construct a new array $$$x$$$ of length $$$n$$$ such that:
- Each element $$$x_i$$$ is an integer which satisfies $$$0 \le x_i \le 1$$$;
- For every $$$i$$$ such that $$$1 \le i \le m$$$ the constraint $$$\sum_{j = 1}^n x_{j} a_{i, j} \equiv b_{i} \pmod{2}$$$ is satisfied;
- $$$\sum_{i = 1}^n x_{i} c_{i}$$$ is as large as possible.
Print the maximum value of $$$\sum_{i = 1}^n x_{i}c_{i}$$$ you can get and the array $$$x_1, \ldots, x_n$$$ itself.
The first line of the input contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n,\ m;\ n + m \le 60)$$$.
Each of the next $$$m$$$ lines contains $$$n + 1$$$ integers $$$a_{i, 1}, \ldots, a_{i, n}$$$ and $$$b_i$$$ ($$$0 \le a_{i, j} \le 1$$$, $$$0 \le b_i \le 1$$$).
Next line contains $$$n$$$ integers $$$c_1, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$).
If it is impossible to construct an array which satisfies the given requirements, print a single integer "-1".
Otherwise, First line of the output should contain a single integer — the maximum value of $$$\sum_{i = 1}^n x_{i}c_{i}$$$.
Second line should contain $$$n$$$ space-separated integers $$$x_1, \ldots, x_n$$$ ($$$0 \le x_i \le 1$$$).
2 2 0 1 1 1 0 1 1 1
2 1 1
2 2 0 0 1 1 1 1 1 1
-1
2 2 0 0 0 1 1 1 1 10
10 0 1
Greetings and welcome... I want to play a game.
The author of the problem has a secret integer $$$d$$$ which you should guess.
You will maintain a set of integers which is initially empty.
There are 2 types of queries you can ask:
- Add an integer $$$x$$$ ($$$0 \leq x \leq 10^9$$$) to the set.
- Remove an integer $$$x$$$ ($$$0 \leq x \leq 10^9$$$) from the set.
You cannot add a number if it is already present in the set and you cannot remove a number if it is not present in the set.
After each query the author will tell you if there are two elements $$$x$$$ and $$$y$$$ in the set, so that $$$x - y = d$$$.
You will play this game $$$T$$$ times. The author guarantees that the secret integer $$$d$$$ for each game will always be in range $$$[1, 500]$$$.
Unfortunately, you don't have much time so you can only ask up to $$$100$$$ queries in each game.
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 25$$$) — number of the games.
After that you should start making queries:
- In case your program is making a query to add an element $$$x$$$, it should print '+ x'.
- In case your program is making a query to remove an element $$$x$$$, it should print '- x'.
- In case your program is ready to guess the secret number $$$d$$$ for this game, it should print '! d'.
For the first two types of queries interactor will respond with:
- 'Incorrect' if you add a number which is already in the set or remove a number which is not in the set.
- 'YES' if there is a pair of elements $$$(x, y)$$$ in the set so that $$$x - y = d$$$
- 'NO' if there is no pair of elements $$$(x, y)$$$ in the set so that $$$x - y = d$$$
After you print the answer for the game, the interactor will respond with 'Correct' if you guessed author's number and 'Incorrect' otherwise.
Please note that if you get the 'Incorrect' response you should immediately stop the program. Otherwise you may get unpredictable verdicts.
Remember to flush the output every time. Use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
2 NO NO YES YES YES Correct NO YES Correct
+ 2 + 3 + 8 + 7 - 8 ! 5 + 37 + 0 ! 37
Daniyar is known to be a very friendly and organized boy and of course he did not forget about Vitya's birthday!
Last year his present for Vitya was a beautiful directed graph with $$$1000$$$ vertices and $$$10000$$$ edges. However, little did he know that Vitya hates graphs with more than $$$5000$$$ edges! He was very frustrated to find his present in a trash bin near Vitya's home.
This year, however, Daniyar is well-prepared. He has researched a lot of scientific papers and after a thorough investigation he has come to the conclusion that Vitya loves arrays consisting of two or more positive integers.
He has already bought a very pretty array and he is eager to go to Vitya's home and see his reaction after receiving such a nice present. His research, though, apparently was not deep enough, as his friend Batyr told him today that Vitya actually hates all arrays not satisfying $$$a_1 \oplus \ldots \oplus a_n = 0$$$!
Only several hours remain for Daniyar to solve this problem. He is a simple student so he cannot afford a new present array. What he can do instead is to increase any number in the array by $$$1$$$ and pay $$$1$$$ dollar for it. How much extra money does Daniyar need to spend to make Vitya finally enjoy his present?
The first line of the input contains a single integer $$$T$$$ — number of test cases ($$$1 \le T \le 50$$$). Each test case contains two lines of input.
First line of each test case contains a single integer $$$n$$$ — size of Daniyar's present array ($$$2 \le n \le 12$$$).
Second line of each test case contains $$$n$$$ space-separated integers $$$a_1, \ldots, a_n$$$ — the present array itself ($$$1 \le a_i \le 10^9$$$).
For each test case output a single integer on a separate line — the minimum amount of money Daniyar needs to spend to make Vitya finally enjoy his present.
3 2 3 8 3 15 16 1 4 1 4 10 11
5 2 2
$$$a \oplus b$$$ is a well-known bitwise operation called 'XOR'. It is denoted as '^' in C and C++. Some examples: $$$5 \oplus 7 = 2$$$, $$$1 \oplus 2 = 3$$$, $$$6 \oplus 3 = 5$$$.
In the first test case, Daniyar can fix his present by increasing the first number $$$a_1$$$ to $$$8$$$.
In the second test case, Daniyar can fix his present by increasing the first number $$$a_1$$$ to $$$17$$$.
There are $$$n$$$ cities in Tima's country. Some of them (usually cities located in Southern areas) are considered warm, while others (usually cities located in Northern areas) are very cold.
Tima is a real nomad and he feels himself obliged to switch places during different seasons. He will switch his living place exactly $$$4$$$ times during the year — one time in spring, summer, fall and winter.
Since springs and summers are very hot in warm cities, Tima wants to live in a cold place during these seasons. Similarly, since falls and winters are very freezing in cold cities, Tima wants to live in a warm place during these seasons.
He can only afford flights between $$$m$$$ pairs of cities though. He does not have much money to afford living in $$$5$$$ or more cities, so he wants to choose exactly $$$4$$$ cities $$$(a, b, c, d)$$$ that will satisfy his needs for the upcoming $$$5$$$ years. Since Tima is a nomad, all those cities should be distinct. How many different choices does he have?
Please note that a choice $$$(a, b, c, d)$$$ is not the same as $$$(b, a, d, c)$$$ or other its permutations.
First line of the input contains two integers $$$n$$$ and $$$m$$$ — the number of cities in Tima's country and the number of flights Tima can afford ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$).
Second line contains a binary string $$$s$$$ of length $$$n$$$. $$$s_i = 1$$$ indicates that $$$i$$$-th city is warm. Respectively, $$$s_i = 0$$$ indicates that $$$i$$$-th city is cold.
Next $$$m$$$ lines each contain a pair of integers $$$a_i$$$ and $$$b_i$$$ which indicates that Tima can afford a flight between cities $$$a_i$$$ and $$$b_i$$$ in both directions ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$). It is guaranteed that no pair of cities appears twice in the input.
Output a single integer — the number of different choices Tima has.
5 7 11100 1 2 1 3 2 4 3 5 4 5 1 5 5 2
2
There are exactly two choices for Tima in the sample:
- $$$(4, 5, 1, 2)$$$. Both cities $$$4$$$ and $$$5$$$ are cold, both cities $$$1$$$ and $$$2$$$ are warm. Tima can afford all seasonal flights $$$4 - 5$$$, $$$5 - 1$$$, $$$1 - 2$$$, $$$2 - 4$$$.
- $$$(5, 4, 2, 1)$$$. Both cities $$$5$$$ and $$$4$$$ are cold, both cities $$$2$$$ and $$$1$$$ are warm. Tima can afford all seasonal flights $$$5 - 4$$$, $$$4 - 2$$$, $$$2 - 1$$$, $$$1 - 5$$$.
Note that $$$(5, 3, 1, 2)$$$ does not count as a valid choice since $$$3$$$ is a warm city thus it is not suitable for summer.
Daniyar has finally graduated from school! Right now he is studying Digit Analysis. In particular, he is learning about various sequences. Professor challenged students to come up with original fast-growing sequences.
Daniyar came up with the sequence $$$(d_n)_{n \in \mathbb{N}}$$$. To calculate the $$$n$$$-th term of the sequence, Daniyar uses the following process. First, he lists all natural numbers, that have the sum of digits equal to $$$n$$$. Then, he replaces each of those numbers with the products of their digits. After that, Daniyar erases duplicates in his list, so that each number occurs exactly once. Finally, he writes down how many numbers are left as $$$d_n$$$.
As you can see, this is a long process and Daniyar forgot how to code years ago. Help him to write a program that calculates $$$d_n$$$ for a given $$$n$$$. Since $$$d_n$$$ might be very large, count it modulo $$$10^9 + 7$$$.
The only line of the input contains a single positive integer $$$n$$$ ($$$1 \le n \le 10^6$$$).
Print a single integer $$$d_n$$$. Since this number might be very large, print it modulo $$$10^9 + 7$$$.
3
4
7
12
Number $$$111$$$ has a sum of digits equal to $$$3$$$. Daniyar replaces the number by its digit product and obtains $$$1$$$.
Number $$$21$$$ has a sum of digits equal to $$$3$$$. Daniyar replaces the number by its digit product and obtains $$$2$$$.
Number $$$3$$$ also has a sum of digits equal to $$$3$$$. Daniyar replaces the number by its digit product and obtains $$$3$$$.
Number $$$201$$$ also has a sum of digits equal to $$$3$$$. Daniyar replaces the number by its digit product and obtains $$$0$$$.
It can be shown that there are no more distinct values we can get, thus the answer is $$$4$$$.
Marco is an expert in data structures. He is so good in those kind of problems that he is able to tell the solution to the problem before even reading it to the end. The other day he was the only one to solve a '3D persistent segment tree' tagged problem.
Vitya, however, doubts Marco's skills. He recently came up with a problem Marco could not solve from the first glance! The problem itself is described below.
You are given a permutation $$$p_1, \ldots, p_n$$$. For each $$$1 \le x \le n$$$ you have to determine if there exists a segment $$$1 \le l \le r \le n$$$ of odd length bigger than $$$1$$$ such that the median of $$$(p_l, \ldots, p_r)$$$ is exactly $$$x$$$.
Marco is very confused. Where are the queries and updates? Why is it asking for a median nonsense instead of a very logical and realistic segment sum? These are the questions Marco will probably never know the answer to. The only question remains — how to solve this problem?
The first line contains a single integer $$$T$$$ — the number of test cases. Each test case contains two lines of input ($$$1 \le T \le 100000$$$).
First line of each test case contains a single integer $$$n$$$ — the size of the permutation $$$p$$$ ($$$3 \le n \le 300000$$$).
Second line of each test case contains exactly $$$n$$$ space-separated integers $$$p_1, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i \neq p_j$$$ if $$$i \neq j$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300000$$$.
For each test case output a string $$$s$$$ of length exactly $$$n$$$. If the answer for $$$x$$$ is true, $$$s_x$$$ should be equal to 'y'. Otherwise, $$$s_x$$$ should be equal to 'n'.
3 5 5 1 3 2 4 3 2 3 1 5 1 2 3 4 5
nyynn nyn nyyyn
Hello! Today we are going to play the game 'Guess the expression'. I have a hidden arithmetic expression of a specific format (a op1 b op2 c). I guarantee you that op1, op2 $$$\in$$$ $$$\{$$$ '+', '-', '*' $$$\}$$$.
Some examples of expressions I could have hidden: a+b*c, a-b-c, a*b-c. Your game objective is to guess my expression by asking queries. You can give me values of the variables ($$$a$$$, $$$b$$$, $$$c$$$) and I will give you back the result of the expression with these variables.
The only two rules are:
- You can ask no more than two queries;
- Your integers have to satisfy $$$0 \le a, b, c \le 1$$$.
Will you play or will you resign?
To ask a query print a single line following the format ? a b c. The integers should satisfy the constraint $$$0 \le a, b, c \le 1$$$. You will then have to read a single integer which will be my answer to your query.
Your program should not ask more than two queries.
To guess an expression print a line in format ! s. Your program has to immediately terminate after printing this line, otherwise you may get unpredictable verdicts.
Remember to flush the output every time. Use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
-1 1
? 0 0 1 ? 1 1 0 ! a*b-c
Tima is known for his perfectionism. If he sees a number, he immediately starts rearranging its digits so that the resulting number is as large as possible. He can place the digits in any order he wants and he can flip some of the digits, as long as the resulting number does not have any leading zeroes and remains an actual number.
For example, Tima can rearrange 214 to be 421, rearrange 2016 to be 9210 (digit 6 can be flipped to 9) and rearrange 1010 to be 1100. But note that 0011 would be invalid because it has leading zeroes.
One day, walking across the street, a big billboard caught Tima's attention and there were in total $$$n$$$ digits written on it at different places. Of course he could not resist the urge to rearrange its digits. What number did he get at the end?
First line of input contains a single integer $$$n$$$ — number of digits on a billboard ($$$1 \le n \le 100$$$).
Second line contains $$$n$$$ space-separated digits $$$a_1, \ldots, a_n$$$ ($$$0 \le a_i \le 9$$$).
It it guaranteed that Tima can construct at least one valid number.
Output the largest number that can be constructed by rearranging the digits on the billboard.
3 2 1 4
421
3 6 0 8
980
3 0 0 1
100