To solve this task you should either solve the given equation or listen to your heart.
Find an integer $$$x$$$ such that $$$$$$ \bigg(\sqrt{x-3} - \sqrt[3]{\frac{3x+2}{2}}\bigg)^7 = \bigg(x - \sqrt{\frac{x^2-1984}{5}}\bigg)^3. $$$$$$ It is guaranteed that this equation has only one integer solution $$$x$$$.
Output the integer solution $$$x$$$ of the equation.
Becoming blue on Codeforces is something to be proud of, especially at the age of ten.
The fifth grader Vasya has recently become blue on CF, and to celebrate it he decided to implement a new advanced algorithm that he learnt from cp-algorithms. The algorithm is called "Modular Multiplicative Inverse". This algorithm finds the modular multiplicative inverse given a number and a module.
Vasya decided to use it to solve a problem on a famous platform for young programmers — Codeforces. The problem goes as follows: given two integers $$$n$$$ and $$$M$$$ ($$$1 \le n \lt M \le 10^9 +7$$$), find such a number $$$k$$$ that $$$n \cdot k \equiv 1 (\mod M)$$$; $$$1 \le k \lt M$$$; $$$M$$$ is a prime.
Thanks to the article mentioned above, Vasya knows that it is enough to raise $$$n$$$ to the power of $$$M - 2$$$ modulo $$$M$$$ to obtain the answer, and, of course, he didn't bother to prove this. Vasya quickly implemented the code for that problem. However, he became discouraged as soon as his wonderful solution got WA6. Feeling deeply offended, he deleted his code and decided to rage quit competitive programming. Nevertheless, on the next day he didn't get any homework and decided to recover his code and find the bugs.
Help Vasya recover his incorrect solution!
Two integer numbers, separated by space: $$$n$$$ and $$$M$$$, $$$1 \le n \lt M \le 10^9+7$$$.
Print one integer $$$k$$$ — the output of Vasya's program for the given test.
1 5
1
2 7
4
3 23
8
Little Lesha studies in the sixth grade. Lesha is not the best performing student, and that's why his interests are rather peculiar. In particular, he finds it exciting to watch Chinese cartoons that are commonly known as anime.
Once, Lesha decided to skip school and devote the whole day to his favorite activity — watching anime. However, suddenly, he realized that there is a lot of trash on the shelf where he stores his anime discs.
The shelf contains $$$n$$$ items. The items are arranged in a row, i.e. can be enumerated from $$$1$$$ to $$$n$$$. The $$$i$$$-th item might be either trash or and anime disc. Lesha remembers that he has exactly $$$k$$$ discs, and that the $$$i$$$-th disc is located somewhere between the positions $$$l_i$$$ and $$$r_i$$$, inclusive.
Help Lesha clean the shelf and regain hope for a better future.
The first line contains two integers separated by space: $$$n$$$, $$$k$$$. Each of the following $$$k$$$ lines also contains two integers: $$$l_i$$$, $$$r_i$$$.
$$$1 \le n \le 100228$$$
$$$0 \le k \le n$$$
$$$1 \le l_i \le r_i \le n$$$
Print $$$n$$$ integer numbers, each equal to $$$0$$$ or $$$1$$$. The $$$i$$$-th number should be equal to $$$1$$$ if and only if the $$$i$$$-th item on the shelf is trash. It is guaranteed that one can always find an unambiguous solution.
5 0
1 1 1 1 1
A team contest with a new format is going to be held on BruteForces: all tests are open, and a team may consist of any number of people. The final rating change is, of course, evenly distributed among the team members.
On the very first contest the following non-trivial problem was given:
«A table $$$S$$$ of size $$$m \times n$$$ is given. In the cell $$$S_{i, j}$$$ (where $$$1 \leqslant i \leqslant m, 1 \leqslant j \leqslant n$$$) the sum of all integers from $$$1$$$ to $$$i+j$$$ is written. Find the sum of all numbers in the sub-table with corner cells $$$S_{1, 1}$$$ and $$$S_{a, b}$$$ for the given $$$a, b$$$.»
A total of $$$T$$$ tests were prepared for this problem.
Shortly after reading the problem statement, blue coder Vasya came up with a solution: if only we knew the numbers in all cells, then we could just use the regular Fenwick tree!
It is enough for Vasya to compute the numbers in some of the cells, not necessarily all. In order to do so, he decided to invite some green coders to his team, and ask each of them to calculate the number in a cell $$$S_{i, j}$$$ (one green coder will be assigned to exactly one cell). Since the final rating change is evenly distributed among the team members, Vasya wants to invite as few coders as possible. Thus, he wants to compute the numbers in only those cells that are necessary for answering at least one test (i. e. those cells that lie in at least one sub-table).
What is the minimal number of coders that Vasya has to invite to his team so as to accomplish his goal?
In the first line there are two integers, $$$m$$$ and $$$n$$$, that describe the size of the table.
In the second line there is $$$T$$$, the number of tests.
On each of the following $$$T$$$ lines, there are numbers $$$a, b$$$ — coordinates of one of the corners of the sub-tables.
$$$1 \leqslant m, n \leqslant 5000$$$
$$$1 \leqslant T \leqslant 1000$$$
$$$1 \leqslant a \leqslant m$$$
$$$1 \leqslant b \leqslant n$$$
One integer — the minimal number of green coders that Vasya has to invite to his team.
4 4 3 1 3 2 2 4 1
7
5 5 5 3 2 2 1 4 4 3 5 2 4
19
It is well known that the border for red color on CF is designed to pass right above Adamant's rating. However, recently, due to an internal error in rating recalculation algorithms Adamant finally became red.
When it happened, Mike realized the algorithm should be fixed urgently. To solve this issue once and for all, we want to design a new division system, so that Adamant goes to div 2 and would be far from red color.
An obvious solution would be to simply put a line if rating $$$\leqslant$$$ adamant.rating then div = max (div, 2) into the existing system, but this would look very suspicious. So Mike came up with the following, rather intricate, procedure:
First, Mike selects the integer parameter $$$k \geqslant 0$$$. Then, he calculates the value of the function $$$f = f(r-k, r)$$$, where $$$r$$$ is the user's rating, and $$$$$$ f(n, x) := (1 + x + x^2/2! + x^3/3! + \dots + x^n/n!)/e^x. $$$$$$ Finally, the user's division is defined by the formula div = $$$int(1/f) - 1$$$, where $$$int(x)$$$ returns maximal integer not exceeding $$$x$$$.
Mike is sure that due to the introduction of div 3 and div 4 to the platform, such a function will be more fair not only to Adamant, but also to all users in general.
Based on the given Adamant rating, find the minimum $$$k$$$ so that the described algorithm assigns him a division strictly greater than $$$1$$$.
First line contains $$$T, 1 \leqslant T \leqslant 20$$$ — number of testcases. Each of the following $$$T$$$ lines contains a single integer number $$$r$$$ — Adamant's rating, $$$5 \leqslant r \leqslant 4000$$$.
On each of the $$$T$$$ lines a single integer $$$k \geqslant 0$$$ — minimal parameteer so that the described algorithm would produce a number stricly greater than 1. It is guaranteed that such a nonnegative $$$k$$$ exists.
1 5
2
2 100 200
5 7
3 2500 3000 3500
23 25 27
As usual, $$$e = 2.718281828459045\dots$$$ — Euler constant.
The fraction's numerator contains incomplete Taylor series for the function $$$e^x$$$, where the whole series is $$$$$$ e^x = 1 + x/1! + x^2/2! + \dots + x^n/n! + \dots. $$$$$$
Being a true expert in rhetorics and NLP, Rudolph spends a lot of time on different forums and online discussions. Recently he has heard about some progress in artificial intelligence and decided to develop an algorithm to reply questions for him, keeping quality of the answers best possible.
Rudolph knows in advance that he will need to reply exactly $$$n$$$ questions, and that is why he prepares $$$n$$$ different strings — answers to the upcoming questions. Then, the algorithm takes $$$n$$$ questions as an input and matches them with the answers. Of course, in order for Rudolph's wit not to be doubted, each answer must be used exactly once.
It is a well known fact that Rudolph is a master of words and rhymes, and therefore artificial intelligence must be smart enough to give the most original and appropriate responses. To evaluate the quality of the algorithm, Rudolph came up with the following metric.
The value of the metric equals to the sum of rhyming values for each question-answer pair. The rhyming of one pair is evaluated as follows: all characters except lowercase Latin letters are removed from the question and answer, and the length of their largest common suffix is calculated. This length will be the rhyming value for this pair.
You need to develop such an algorithm to match the questions with answers and calculate the largest possible value of the metric. If there are several possible responses with optimal values of the metric, choose any.
The first line contains a single integer $$$n$$$ – the number of questions and answers ($$$1 \le n \le 800$$$). Each of the following $$$n$$$ lines has one string — a question. Then, each of the following $$$n$$$ lines has one string — an answer.
Each string consists of lowercase Latin letters, spaces and symbols "?" "!" and ")".
Total length of all strings does not exceed $$$200000$$$.
The first line of the output should contain the answer — optimal value of the metric (the sum of rhymings of all pairs question-answer). Then, in the following $$$2n$$$ lines print the pairs question-answer: questions in the same order, as in the input, and each question having the corresponding answer on the next line.
5 zdraste! kak dela? gde byl? a voobshe kak sam? horosho poka poka ne rodila pivo pyl zabor pokraste ne zabud vyrvat dvoiku s dnevnika privet tvoei madam
13 zdraste! zabor pokraste kak dela? poka ne rodila gde byl? pivo pyl a voobshe kak sam? privet tvoei madam horosho poka ne zabud vyrvat dvoiku s dnevnika
5 here comes adamant! i hope he will add anime to contest! is it rated? well, have fun and good luck! when the ratings would update?? you sure will fail iq test when you would have a date)) try not to suck) he does not use deodarant obosrated!
19 here comes adamant! he does not use deodarant i hope he will add anime to contest! you sure will fail iq test is it rated? obosrated! well, have fun and good luck! try not to suck) when the ratings would update?? when you would have a date))
Suppose that we want to calculate rhyming for the pair
"abc d ef!!!" and "lol k e k cd?)ef?"
To do this, we remove all the symbols, except for lowercase Latin letters: "abcdef", "lolkekcdef", and then we find the length of the longest common suffix, which is 4.
Because of the extraordinary academic achievements during his university studies, Rudolph Veniaminovich Gotov was the only one to be assigned to work as a math teacher after graduation.
In the class where Rudolph teaches, there are exactly $$$m$$$ students. The math lesson by Rudolph goes as follows. He creates a list of $$$n$$$ ($$$n \geqslant m$$$) problems and distributes it among the students. Then, he calls students to the blackboard using a random number generator. In the first step, the generator generates a number $$$t_1$$$, and then Rudolph calls the first student to the blackboard to solve a problem with number $$$t_1$$$ in the list. In the second step, the generator generates a number $$$t_2$$$, and Rudolph calls the second student to solve the problem number $$$t_2$$$ in the list, and so on, up to the $$$m$$$-th student. The generator is designed so that sequence $$$t_i$$$ is increasing and never exceeds $$$n$$$, i.e., the following inequalities hold: $$$$$$ 1 \leqslant t_1 \lt t_2 \lt \cdots \lt t_m \leqslant n. $$$$$$ If a student can't solve a problem at the blackboard, Rudolf Veniaminovich gives him a noogie.
Rudolf Veniaminovich is already tired of teaching, so his only goal during the lesson is to give each student a noogie.
To do this, he has selected exactly $$$m$$$ complicated problems (which he cannot solve himself) and wants to redesign the random number generator so that it would generate exactly their numbers in the list.
In order not to arouse suspicion, Rudolph came up with the following algorithm for the generator: it receives the number $$$n$$$ as an input (that is, the number of tasks) and generates exactly those numbers that have at least one common divisor with $$$n$$$. Rudolph is sure that such a sequence would look very random. For example, for $$$n=12$$$, such an algorithm would generate numbers $$$2, 3, 4, 6, 8, 9, 10, 12$$$. Having such a "random" generator, Rudolph knows in advance what numbers will be generated, and can put his complicated problems on the right places in the sheet.
However, Rudolph faced a problem — it is not that easy to come up with such a number $$$n$$$ for which the generator would output exactly $$$m$$$ numbers!
Positive integer $$$2 \leqslant m \leqslant 10^8$$$.
Such positive integer $$$n \leqslant 10^{12}$$$ that the generator would generate exactly $$$m$$$ numbers.
8
12
9
21
200
398
It is guaranteed that for any $$$m$$$ in the test cases the desired $$$n$$$ exists.